Program hanging on for()

Discussion in 'Mac Programming' started by Aranince, Oct 2, 2008.

  1. Aranince macrumors 65816

    Joined:
    Apr 18, 2007
    Location:
    California
    #1
    I have this code:

    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.
     
  2. toddburch macrumors 6502a

    Joined:
    Dec 4, 2006
    Location:
    Katy, Texas
    #2
    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.
     
  3. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #3
    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:
    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
     
  4. bbarnhart macrumors 6502a

    bbarnhart

    Joined:
    Jan 16, 2002
    Location:
    Stilwell, Kansas
    #4
    toddburch is correct. There is a fundamental problem with the code...

    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.
     
  5. bbarnhart macrumors 6502a

    bbarnhart

    Joined:
    Jan 16, 2002
    Location:
    Stilwell, Kansas
    #5
    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.

    Code:
            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   
                 }
            }
    
     
  6. toddburch macrumors 6502a

    Joined:
    Dec 4, 2006
    Location:
    Katy, Texas
    #6
    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.
     
  7. bbarnhart macrumors 6502a

    bbarnhart

    Joined:
    Jan 16, 2002
    Location:
    Stilwell, Kansas
    #7
    Then iter would equal list.end() and the for loop would end.
     
  8. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #8
    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.
     
  9. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #9
    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
     
  10. toddburch macrumors 6502a

    Joined:
    Dec 4, 2006
    Location:
    Katy, Texas
    #10
    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?
     
  11. toddburch macrumors 6502a

    Joined:
    Dec 4, 2006
    Location:
    Katy, Texas
    #11
    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.
     
  12. bbarnhart macrumors 6502a

    bbarnhart

    Joined:
    Jan 16, 2002
    Location:
    Stilwell, Kansas
    #12
    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

    Code:
            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++;
                 }
            }
    
     
  13. bbarnhart macrumors 6502a

    bbarnhart

    Joined:
    Jan 16, 2002
    Location:
    Stilwell, Kansas
    #13
    Code:
    
      int i = 5;
      int x = i++;
     
      // x = 5 and now i = 6
     
     
  14. Aranince thread starter macrumors 65816

    Joined:
    Apr 18, 2007
    Location:
    California
    #14
    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.
     
  15. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #15
    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
     
  16. toddburch macrumors 6502a

    Joined:
    Dec 4, 2006
    Location:
    Katy, Texas
    #16
    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?
     
  17. Aranince thread starter macrumors 65816

    Joined:
    Apr 18, 2007
    Location:
    California
    #17
    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.
     
  18. lee1210 macrumors 68040

    lee1210

    Joined:
    Jan 10, 2005
    Location:
    Dallas, TX
    #18
    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
     
  19. Aranince thread starter macrumors 65816

    Joined:
    Apr 18, 2007
    Location:
    California
    #19
    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.
     
  20. Aranince thread starter macrumors 65816

    Joined:
    Apr 18, 2007
    Location:
    California
    #20
    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:
    Code:
    /*!
     * 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;   
        
    }
     
  21. toddburch macrumors 6502a

    Joined:
    Dec 4, 2006
    Location:
    Katy, Texas
    #21
    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.
     

Share This Page