macOS Program hanging on for()

[Aranince]

I have this code:

/*!
 * Returns a list in order by descending priority 
 */
std::map<int, Task*> prioritizeListDesc(std::map<int, Task*> list)
{
    TodoListIterator iter;
    std::map<int, Task*> result;
    int priority = 5;
    
    for(int priority = 5; priority > 0; priority-- )
    {
        for(iter = list.begin(); iter != list.end(); iter++)
        {
            if(iter->second->getPriority() == priority)
            {
                result[iter->first] = iter->second;
                list.erase(iter);
            }
        }
    }
    
    return result;   
    
}

Breaking through the code in gdb yields this result:

for(int...)
for(iter...)
if(iter)
add to result[]
erase
for(iter...)
if(iter) (is not equal)
for(iter)

After that point, the program completely hangs. No errors or anything, just sits there. It should work, I use the same loop in several other methods with the same list.

 

[toddburch]

If I'm not mistaken, the list.erase() invalidates your begin() and end() markers. So, perhaps you can continue without erasing that element from the list, and your existing logic will just pass over it in subsequent iterations. Then, when you're done, kill the whole original list if you need to.

 

[lee1210]

The erase seems to be handled gracefully, but it doesn't seem necessary (that was my first instinct as well).

You didn't quite include enough code for me to be sure about the behavior, so i implemented the supporting functions, but didn't see the behavior you did.

here's my code:

#include <iostream>
#include <map>
#include <string>

class Task {
  private:
    int prio;
    std::string name;
  public:
    int getPriority() { return prio; }
    void setPriority(int p) { prio = p; }
    std::string getName() { return name; }
    void setName(std::string *p) { name = *p; }
};
std::map<int, Task*> prioritizeListDesc(std::map<int, Task*>);

int main(int argc, char *argv[]) {
  Task *one;
  std::map<int, Task*> myList;
  std::map<int, Task*>::iterator it;
  one = new Task();
  one->setPriority(4);
  one->setName(new std::string("Has prio 4, placed first"));
  myList[0] = one;
  one = new Task();
  one->setPriority(1);
  one->setName(new std::string("Has prio 1, placed second"));
  myList[1] = one;
  one = new Task();
  one->setPriority(2);
  one->setName(new std::string("Has prio 2, placed third"));
  myList[2] = one;
  one = new Task();
  one->setPriority(3);
  one->setName(new std::string("Has prio 3, placed fourth"));
  myList[3] = one;
  one = new Task();
  one->setPriority(5);
  one->setName(new std::string("Has prio 5, placed fifth"));
  myList[4] = one;
  std::map<int, Task*> myList2 = prioritizeListDesc(myList);
  for(it = myList2.begin(); it != myList2.end(); it++) {
    std::cout << "Prio: " << it->second->getPriority() << " Name: " << it->second->getName() << std::endl;
  }
}

std::map<int, Task*> prioritizeListDesc(std::map<int, Task*> list) {
    std::map<int, Task*>::iterator iter;
    std::map<int, Task*> *result = new std::map<int, Task*>();
    int priority = 5;
    Task *one = NULL;
    int pos = 0;
    
    for(int priority = 5; priority > 0; priority-- )
    {
        std::cout << "Searching for priority: " << priority << std::endl;
        for(iter = list.begin(); iter != list.end(); iter++)
        {
            std::cout << "Checking element: " << iter->second->getPriority() << " " << iter->second->getName() << std::endl;
            if(iter->second->getPriority() == priority)
            {
                std::cout << "Prio: " << priority << std::endl;
                (*result)[pos++] = iter->second;
                list.erase(iter);
            }
        }
    }
    
    return *result;
}

The debug is still in there. I changed this up a bit because:
1) Using iter->first as the key to the new map means no reordering will occur, you need to have an absolute ordering based on the priority, so i added pos.
2) I don't think it's a good plan to return a local object. I could be totally wrong, and it might happen by value. I'm not familiar enough with C++ to say on that. Your code could be fine in that regard, but I changed it to get an Object on the stack and return that instead. I'm really uncomfortable with C++ having local objects, it seems like they should always be on the heap, so... whatever, I could be wrong on this. It could be just like returning an int.

You may want to post more code if you are still having problems, and we can take a look. I wouldn't do an erase, it's not necessary. I tried it with it in there, and my code was OK, but maybe it won't be in every case. It works equally well with it removed.

-Lee

 

[bbarnhart]

toddburch is correct. There is a fundamental problem with the code...

for(iter = list.begin(); iter != list.end(); iter++)
        {
            if(iter->second->getPriority() == priority)
            {
                result[iter->first] = iter->second;
                list.erase(iter);
      
                // iter is now invalid

            }
        }

After the line, list.erase(iter), iter is invalid. Erasing an element of a map causes iterators to be invalid. One solution would be to begin the entire outer for() loop again to reinitialize iter. It's probably not going to be the fastest, if that's important.

This 'loop' is not working in other methods.

 

[bbarnhart]

I'm incorrect. I've not used std::map for a while, but here is what I've found. The variable iter is invalid, but the solution is to post increment iter.

        for(iter = list.begin(); iter != list.end(); iter++)
        {
            if(iter->second->getPriority() == priority)
            {
                result[iter->first] = iter->second;
                list.erase(iter++);  // iter++ returns the current value of iter
                                     // for use in list.erase(...)
                                     // and increments iter by one before
                                     // list.erase() is called   
             }
        }

 

[toddburch]

I'm incorrect. I've not used std::map for a while, but here is what I've found. The variable iter is invalid, but the solution is to post increment iter.

        for(iter = list.begin(); iter != list.end(); iter++)
        {
            if(iter->second->getPriority() == priority)
            {
                result[iter->first] = iter->second;
                list.erase(iter++);  // iter++ returns the current value of iter
                                     // for use in list.erase(...)
                                     // and increments iter by one before
                                     // list.erase() is called   
             }
        }

And if the last list element gets erased with that technique, what happens? Seems like you would go an extra element past the end, and therefore the for() loop would continue.

 

[bbarnhart]

And if the last list element gets erased with that technique, what happens? Seems like you would go an extra element past the end, and therefore the for() loop would continue.

Then iter would equal list.end() and the for loop would end.

 

[lee1210]

I wanted to chime in again, because, as I said, I don't know the intricacies of C++, and the standard libraries. In my code, I tried it with and without the erase, and both seemed fine. In the debugger, nothing changed with the iterator object itself at the time of the erase, but I don't know if I just got lucky. Then ++ is applied to an iter that was just erased, is this asking for trouble? I'm not as familiar at finding/traversing STL documentation as some others, so if someone could point to something discussing this it would be quite interesting.

 

[lee1210]

I'm incorrect. I've not used std::map for a while, but here is what I've found. The variable iter is invalid, but the solution is to post increment iter.

        for(iter = list.begin(); iter != list.end(); iter++)
        {
            if(iter->second->getPriority() == priority)
            {
                result[iter->first] = iter->second;
                list.erase(iter++);  // iter++ returns the current value of iter
                                     // for use in list.erase(...)
                                     // and increments iter by one before
                                     // list.erase() is called   
             }
        }

Erm, again, I'm not an expert on this, but it seems to me that iter++ will increment the iterator to the next element and return the current element. This seems fine, erase gets the right thing... but then iter++ gets called again before the loop condition is checked. It seems like you skipped an element, right?

-Lee

 

[toddburch]

Then iter would equal list.end() and the for loop would end.

OK, let's take a simple example so I can understand it.

Let's pretend our iter values are 0 through 5. begin() would equal 0, and end() would equal 6.

If list[5] gets deleted, the sequence of events would be
1) iter++ , so iter becomes 6.
2) The increment portion of the for() loop gets control, so iter++ happens again, and now iter equals 7.
3) the for() condition is tested, and since 7 != 6 is true, the loop proceeds to execute again.

What am I missing?

 

[toddburch]

Erm, again, I'm not an expert on this, but it seems to me that iter++ will increment the iterator to the next element and return the current element. This seems fine, erase gets the right thing... but then iter++ gets called again before the loop condition is checked. It seems like you skipped an element, right?

-Lee

In this case, list.erase(iter++), (the postfix operator), if iter==5, then list[5] will be erased, then iter will be come 6. I think you are describing list.erase(++iter) - the prefix operator, in which case iter would be incremented first, then list[6] would be erased.

 

[bbarnhart]

toddburch and lee1210 are corrent. iter is being incremented too many times. I've removed the iter++ from the for loop and put it into the middle.

The correct loop

        for(iter = list.begin(); iter != list.end(); )
        {
            if(iter->second->getPriority() == priority)
            {
                result[iter->first] = iter->second;
                list.erase(iter++);  // iter++ returns the current value of iter
                                     // for use in list.erase(...)
                                     // and increments iter by one before
                                     // list.erase() is called   
             }
             else
             {
                iter++;
             }
        }

 

[bbarnhart]

In this case, list.erase(iter++), (the postfix operator), if iter==5, then list[5] will be erased, then iter will be come 6. I think you are describing list.erase(++iter) - the prefix operator, in which case iter would be incremented first, then list[6] would be erased.

  int i = 5;
  int x = i++;
 
  // x = 5 and now i = 6

 

[Aranince]

toddburch and lee1210 are corrent. iter is being incremented too many times. I've removed the iter++ from the for loop and put it into the middle.

The correct loop

        for(iter = list.begin(); iter != list.end(); )
        {
            if(iter->second->getPriority() == priority)
            {
                result[iter->first] = iter->second;
                list.erase(iter++);  // iter++ returns the current value of iter
                                     // for use in list.erase(...)
                                     // and increments iter by one before
                                     // list.erase() is called   
             }
             else
             {
                iter++;
             }
        }

Ok, I tried this way and it works, the program does not freeze. But the list isn't being sorted by priority. What I'm trying to do, if it is not apparent, is go through the list of tasks, put all the tasks whose priority is 5 at the front, 4 below that, and so on. I erase the instance, so it doesn't get parsed again. Is the std::map automatically sorting by the id?

EDIT: If you would like to see more code, you can get it from the subversion in my sig. I'll commit the latest working version now.

 

[lee1210]

see my original post for the sorting issue. You are rebuilding the same map. Map keeps an internal ordering by key.

Deleting speeds up the algorithm slightly, but isn't required for correctness.

-Lee

 

[toddburch]

The key (in your case, the priority) should be automatically sorted in ascending order. You want descending order. Will there be duplicates? (Can you have, for instance, two tasks @ priority 5?) If so, you'll want to use a multimap instead of a map.

What order are they being sorted in? Ascending?

 

[Aranince]

see my original post for the sorting issue. You are rebuilding the same map. Map keeps an internal ordering by key.

Deleting speeds up the algorithm slightly, but isn't required for correctness.

-Lee

Ok, that makes sense. What if I want to keep track of the task's id(I'm planning on using this so the user can edit and/or change a task)? I'm assuming I'll have to start keeping track of IDs inside the task. The way IDs are given to the tasks are by their position in the txt file.

So I load a std::map the same way I did before, also assigning an id to the task during creation. But having two types of lists, one with ID and one with position seems unintuitive and more possibility for error. I wonder if I should arbitrarily assign IDs instead of relying on the position in the file for the id.

EDIT: Any number of tasks can be the same priority. I was planning on adding the ability for both ascending and descending. This problem was for descending.

 

[lee1210]

a-ha, now we have a design problem instead of an algorithm problem. So I would just use the position in the file, and store the id in the Task class. You can also use it as your initial key in the list, but you'll still have it in your task instances when you sort. I'd just use an increasing number as the key, or use a list instead of map when sorting.

-Lee

 

[Aranince]

I could use a list throughout the whole program, and if I want a specific task I just iterate through the list till I find the one I want. I don't think speed should be a problem unless the user has a very large list of tasks.

Or like you said, when I want the list in a specific order I just return a std::list. Really the only reason I can think of right now that I need to organize a list like that is is so I can display it back to the user.

 

[Aranince]

Ok, the problem has been solved. Thanks lee and everyone for your help. My next task is probably to split the code up better, so its not all jammed into the same file.

The working function:

/*!
 * Returns a list in order by descending priority 
 */
std::list<Task*> prioritizeListDesc(std::map<int, Task*> list)
{
    TodoListIterator iter;
    std::list<Task*> result;
    int priority = 5;
    
    for(int priority = 5; priority > 0; priority-- )
    {
        for(iter = list.begin(); iter != list.end();)
        {
            if(iter->second->getPriority() == priority)
            {
                result.push_back(iter->second);
                list.erase(iter++);
            }
            else
            {
                iter++;
            }
        }
    }
    
    return result;   
    
}

 

[toddburch]

I read "The C++ Standard Template Library" just now, pages 204 and 205, and Lee's solution is indeed correct.

I was right about the iterator being invalidated, but a bit wrong as to why. It's not the begin() and end() markers that are invalidated, it's the actual iterator that is invalidated. Calling list.erase(iter++) essentially sends a copy of iter to the erase function, on the stack, and that temporary copy of iter gets invalidated instead iter itself getting invalidated.