iterator missunderstanding.

This is a discussion on iterator missunderstanding. within the C++ Programming forums, part of the General Programming Boards category; Here is some code I half stole from the c++ referance website and filled in a little for my purposes. ...

  1. #1
    Registered User
    Join Date
    Dec 2009
    Posts
    41

    iterator missunderstanding.

    Here is some code I half stole from the c++ referance website and filled in a little for my purposes. Initially I wanted to make sure I understood the equal_range function:

    this is my understanding of the code below.

    calling equal_range returns something that looks like : <<'b',20>, <c,30>>
    it becomes <'b',20>
    when it gets to the loop, it gets set to <'b',20> again
    calling erase should remove the "b" key and its value from the map.
    and my output should look like

    a->10
    b->0
    c->30
    d->40
    e->50
    f->60

    unfortunately it looks like this:
    a->10
    b->0
    c->30
    d->0
    e->0
    f->0

    in fact, a,c and e work as expected, removing the equal_range parameter.
    the rest have odd functionality. F erases the whole map, which sorta makes sense to me, but b, and d have me stumped.

    any thoughts on this? Also, I know this is not the best way to accomplish this, I wrote this to help better understand a much larger project.

    Thanks!


    Code:
    #include <iostream>
    #include <map>
    using namespace std;
    
    int main ()
    {
      map<char,int> * mymap = new map<char,int>();
      map<char,int>::iterator it;
      pair<map<char,int>::iterator,map<char,int>::iterator> ret;
      bool yes = true;
      // insert some values:
      	(*mymap)['a']=10;
      	(*mymap)['b']=20;
      	(*mymap)['c']=30;
      	(*mymap)['d']=40;
      	(*mymap)['e']=50;
      	(*mymap)['f']=60;
      
    	ret = mymap->equal_range('b');
    	it = ret.first;
    	if(it != mymap->end()){
    		cout << "lower bound points to: ";
    	  	cout << ret.first->first << " => " << ret.first->second << endl;
      		
    		cout << "upper bound points to: ";
      		cout << ret.second->first << " => " << ret.second->second << endl;
    
    		for(it=ret.first; it!=ret.second; ++it){
    			if(yes){
    				mymap->erase(it);
    				cout << "erased the iter:"<< it->first << endl;
    			}	
    		}
    		for(int i = 'a'; i<='f'; i++){
    			cout << char(i) << "->" << (*mymap)[i] << endl;
    		}
    
    	}
    	return 0;
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,630
    This is wrong:
    Code:
    mymap->erase(it);
    cout << "erased the iter:"<< it->first << endl;
    Once you use erase with an iterator, the iterator is invalidated. Therefore, you cannot access it->first, nor can you use ++it.

    One way out is to use the range version of erase and then "cheat" by printing out what is to be erased before actually erasing:
    Code:
    if (yes) {
        for (it = ret.first; it != ret.second; ++it) {
            cout << "erased the iter:" << it->first << endl;
        }
        mymap->erase(ret.first, ret.second);
    }
    A probably less efficient way:
    Code:
    if (yes) {
        for (it = ret.first; it != ret.second;) {
            cout << "erased the iter:" << it->first << endl;
            mymap->erase(it++);
        }
    }
    EDIT:
    By the way, why is mymap a pointer? You forgot to match the new with delete, but you did not need to use new in the first place.
    Last edited by laserlight; 01-24-2012 at 10:16 AM.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Dec 2009
    Posts
    41
    Alright makes sense,

    now. If I understand, the first iteration of the loop deletes the iterator. now, at the end of the loop it adds one to an invalid iterator, which im assuming is now invalid memory, so in some cases it gets it correct and goes to the next element in the map when it adds 1. sometimes it keeps hopping around because it never equals ret.second.

  4. #4
    Registered User
    Join Date
    Dec 2009
    Posts
    41
    Quote Originally Posted by laserlight View Post
    EDIT:
    By the way, why is mymap a pointer? You forgot to match the new with delete, but you did not need to use new in the first place.
    Simply because In the main program I'm trying to understand has the map as a pointer.

  5. #5
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Right. The main problem with your original code is that you increment the iterator after you've erased it! That's why the code laserlight has given does a post-increment on the iterator, computing the next iterator before erasing the current one.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  6. #6
    Registered User
    Join Date
    Dec 2009
    Posts
    41
    Another question on this. this comes from the main program which I'm trying to understand. The for loop
    Code:
     for (it = ret.first; it != ret.second; ++it) {
    wouldn't it always simply delete whatever ret.first is and nothing else? because the equal_range('b') will return the param and the param +1. and the for loop will essentially do the same as simply mymap->erase('b');?

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,630
    Quote Originally Posted by somekid413
    wouldn't it always simply delete whatever ret.first is and nothing else? because the equal_range('b') will return the param and the param +1. and the for loop will essentially do the same as simply mymap->erase('b');?
    Yes, unless you are dealing with a multimap (in which case it would still have the same effect as using mymap->erase('b')).
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User
    Join Date
    Dec 2009
    Posts
    41
    Sorry to revisit. But I continued tinkering with this and now I'm a little more confused. I tried to delete the map post incrementing the iterator, as mentioned above. but I get this output:

    created stuff
    Erasing:1
    Erasing:4
    Erasing:1
    Erasing:76
    Erasing:79

    and then just freezes. never returns.

    incrementing the pointer in the for loop, gives me proper functionality:

    created stuff
    Erasing:1
    Erasing:4
    Erasing:76
    Erasing:79
    all gone!

    so that is question 1. the post increment makes perfect sense to me after your explanations. but now in a slightly different context, it doesn't work. and I cant quite figure out the difference.

    question 2:

    I'm trying to erase the map with no memory leaks. so I'm using valgrind to see whats going on. I do clear the leaks properly, but end up with a lot of errors I'm not sure how to deal with, or what they are referring too. I'm assuming it has to do with the empty char[] that I'm lazily creating. But I'm really not sure how to read this info or how to deal with it.

    Code:
    ~/test/mapTest>valgrind --leak-check=full --show-reachable=yes ./a.out
    ==23489== Memcheck, a memory error detector.
    ==23489== Copyright (C) 2002-2006, and GNU GPL'd, by Julian Seward et al.
    ==23489== Using LibVEX rev 1658, a library for dynamic binary translation.
    ==23489== Copyright (C) 2004-2006, and GNU GPL'd, by OpenWorks LLP.
    ==23489== Using valgrind-3.2.1, a dynamic binary instrumentation framework.
    ==23489== Copyright (C) 2000-2006, and GNU GPL'd, by Julian Seward et al.
    ==23489== For more details, rerun with: -v
    ==23489== 
    created stuff
    Erasing:1
    ==23489== Invalid read of size 8
    ==23489==    at 0x30F8264BE0: std::_Rb_tree_increment(std::_Rb_tree_node_base*) (in /usr/lib64/libstdc++.so.6.0.8)
    ==23489==    by 0x402519: std::_Rb_tree_iterator<std::pair<int const, char*> >::operator++(int) (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x400F37: ClassRoom::~ClassRoom() (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x401313: main (in /home/user/test/mapTest/a.out)
    ==23489==  Address 0x4C360F0 is 24 bytes inside a block of size 48 free'd
    ==23489==    at 0x4A05130: operator delete(void*) (vg_replace_malloc.c:244)
    ==23489==    by 0x402264: __gnu_cxx::new_allocator<std::_Rb_tree_node<std::pair<int const, char*> > >::deallocate(std::_Rb_tree_node<std::pair<int const, char*> >*, unsigned long) (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x40228C: std::_Rb_tree<int, std::pair<int const, char*>, std::_Select1st<std::pair<int const, char*> >, std::less<int>, std::allocator<std::pair<int const, char*> > >::_M_put_node(std::_Rb_tree_node<std::pair<int const, char*> >*) (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x4022D7: std::_Rb_tree<int, std::pair<int const, char*>, std::_Select1st<std::pair<int const, char*> >, std::less<int>, std::allocator<std::pair<int const, char*> > >::destroy_node(std::_Rb_tree_node<std::pair<int const, char*> >*) (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x402445: std::_Rb_tree<int, std::pair<int const, char*>, std::_Select1st<std::pair<int const, char*> >, std::less<int>, std::allocator<std::pair<int const, char*> > >::erase(std::_Rb_tree_iterator<std::pair<int const, char*> >) (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x402478: std::map<int, char*, std::less<int>, std::allocator<std::pair<int const, char*> > >::erase(std::_Rb_tree_iterator<std::pair<int const, char*> >) (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x400F29: ClassRoom::~ClassRoom() (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x401313: main (in /home/user/test/mapTest/a.out)
    ==23489== 
    ==23489== Invalid read of size 8
    ==23489==    at 0x30F8264C01: std::_Rb_tree_increment(std::_Rb_tree_node_base*) (in /usr/lib64/libstdc++.so.6.0.8)
    ==23489==    by 0x402519: std::_Rb_tree_iterator<std::pair<int const, char*> >::operator++(int) (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x400F37: ClassRoom::~ClassRoom() (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x401313: main (in /home/user/test/mapTest/a.out)
    ==23489==  Address 0x4C360E0 is 8 bytes inside a block of size 48 free'd
    ==23489==    at 0x4A05130: operator delete(void*) (vg_replace_malloc.c:244)
    ==23489==    by 0x402264: __gnu_cxx::new_allocator<std::_Rb_tree_node<std::pair<int const, char*> > >::deallocate(std::_Rb_tree_node<std::pair<int const, char*> >*, unsigned long) (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x40228C: std::_Rb_tree<int, std::pair<int const, char*>, std::_Select1st<std::pair<int const, char*> >, std::less<int>, std::allocator<std::pair<int const, char*> > >::_M_put_node(std::_Rb_tree_node<std::pair<int const, char*> >*) (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x4022D7: std::_Rb_tree<int, std::pair<int const, char*>, std::_Select1st<std::pair<int const, char*> >, std::less<int>, std::allocator<std::pair<int const, char*> > >::destroy_node(std::_Rb_tree_node<std::pair<int const, char*> >*) (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x402445: std::_Rb_tree<int, std::pair<int const, char*>, std::_Select1st<std::pair<int const, char*> >, std::less<int>, std::allocator<std::pair<int const, char*> > >::erase(std::_Rb_tree_iterator<std::pair<int const, char*> >) (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x402478: std::map<int, char*, std::less<int>, std::allocator<std::pair<int const, char*> > >::erase(std::_Rb_tree_iterator<std::pair<int const, char*> >) (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x400F29: ClassRoom::~ClassRoom() (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x401313: main (in /home/user/test/mapTest/a.out)
    ==23489== 
    ==23489== Invalid read of size 8
    ==23489==    at 0x30F8264C22: std::_Rb_tree_increment(std::_Rb_tree_node_base*) (in /usr/lib64/libstdc++.so.6.0.8)
    ==23489==    by 0x402519: std::_Rb_tree_iterator<std::pair<int const, char*> >::operator++(int) (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x400F37: ClassRoom::~ClassRoom() (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x401313: main (in /home/user/test/mapTest/a.out)
    ==23489==  Address 0x4C360F0 is 24 bytes inside a block of size 48 free'd
    ==23489==    at 0x4A05130: operator delete(void*) (vg_replace_malloc.c:244)
    ==23489==    by 0x402264: __gnu_cxx::new_allocator<std::_Rb_tree_node<std::pair<int const, char*> > >::deallocate(std::_Rb_tree_node<std::pair<int const, char*> >*, unsigned long) (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x40228C: std::_Rb_tree<int, std::pair<int const, char*>, std::_Select1st<std::pair<int const, char*> >, std::less<int>, std::allocator<std::pair<int const, char*> > >::_M_put_node(std::_Rb_tree_node<std::pair<int const, char*> >*) (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x4022D7: std::_Rb_tree<int, std::pair<int const, char*>, std::_Select1st<std::pair<int const, char*> >, std::less<int>, std::allocator<std::pair<int const, char*> > >::destroy_node(std::_Rb_tree_node<std::pair<int const, char*> >*) (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x402445: std::_Rb_tree<int, std::pair<int const, char*>, std::_Select1st<std::pair<int const, char*> >, std::less<int>, std::allocator<std::pair<int const, char*> > >::erase(std::_Rb_tree_iterator<std::pair<int const, char*> >) (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x402478: std::map<int, char*, std::less<int>, std::allocator<std::pair<int const, char*> > >::erase(std::_Rb_tree_iterator<std::pair<int const, char*> >) (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x400F29: ClassRoom::~ClassRoom() (in /home/user/test/mapTest/a.out)
    ==23489==    by 0x401313: main (in /home/user/test/mapTest/a.out)
    Erasing:4
    Erasing:76
    Erasing:79
    all gone!
    ==23489== 
    ==23489== ERROR SUMMARY: 10 errors from 3 contexts (suppressed: 4 from 1)
    ==23489== malloc/free: in use at exit: 0 bytes in 0 blocks.
    ==23489== malloc/free: 9 allocs, 9 frees, 345 bytes allocated.
    ==23489== For counts of detected errors, rerun with: -v
    ==23489== All heap blocks were freed -- no leaks are possible.
    ~/test/mapTest>



    the header:
    Code:
    /*
     * ClassRoom.h
     *
     *  Created on: Jan 20, 2012
     *      Author: user
     */
    #include <string.h>
    #include <vector>
    #include <map>
    using namespace std;
    
    #ifndef CLASSROOM_H_
    #define CLASSROOM_H_
    
    
    
    
    class ClassRoom{
    public:
    	ClassRoom();
    	~ClassRoom();
    private:
    	map<int,char*> * myRoom;
    };
    
    
    #endif /* CLASSROOM_H_ */
    the cpp file:
    Code:
    #include <iostream>
    #include <map>
    #include "MapClass.h"
    using namespace std;
    
    ClassRoom::ClassRoom()
    		{
        myRoom = new map<int, char*>();
        myRoom->insert(pair<int,char*>(1,new char[23]));
        myRoom->insert(pair<int,char*>(4,new char[15]));
        myRoom->insert(pair<int,char*>(76,new char[33]));
        char * somechar = "scoobydoo";
        myRoom->insert(pair<int,char*>(79,new char[34]));
        cout << "created stuff" << endl;
    	}
    
    ClassRoom::~ClassRoom(){
    	  map<int,char*>::iterator it;
        for(it = myRoom->begin(); it != myRoom->end();it++){
          cout << "Erasing:" << it->first << endl;
          delete[] (*it).second;
          myRoom->erase(it);
    
          
      }
      delete myRoom;
            cout << "all gone!" << endl;
        }
    
    int main()
    {
        //ClassRoom classy = new ClassRoom();
      ClassRoom classy;
    
    	return 0;
    
    }

  9. #9
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,666
    To explain the advice again, mymap->erase(it++); works because the post increment will return the correct iterator to be erased, after incrementing it. If you do

    Code:
    for (it = whatever; it != end; it++)
       mymap->erase(it);
    it's not the same. By the time it++ gets to execute the iterator has already been invalidated.

  10. #10
    Registered User
    Join Date
    Dec 2009
    Posts
    41
    No, I understand that whiteflags. but in practice, in the example above, mymap->erase(it++); did not free the map properly at all, where as

    Code:
    for (it = whatever; it != end; it++)
       mymap->erase(it);
    worked fine. Hence my newfound confusion

  11. #11
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,666
    The errors from valgrind are referring to your use of invalidated iterators.
    Last edited by whiteflags; 01-26-2012 at 10:50 AM. Reason: errors -> iterators

  12. #12
    Registered User
    Join Date
    Dec 2009
    Posts
    41
    alright, that makes sense, but then why does it delete everything properly? I'll fight with this and post a solution if I come to it.

  13. #13
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,666
    Because sometimes when you delete a pointer you can still read from it, even though you aren't supposed to. IOW, access to freed memory is not guaranteed to fail spectacularly.

    You can write your destructor like this and it should get rid of all the problems:

    Code:
     
    map<int, char*>::iterator it = myRoom->begin(), end = myRoom->end();
    while ( it != end ) {
       cout << "erasing " << it->first << endl;
       delete[] it->second;
       myRoom->erase( it++ );
    }
    delete myRoom;
    cout << "all gone" << endl;
    Last edited by whiteflags; 01-26-2012 at 11:15 AM.

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,630
    Really, I do not understand why you insist on using a pointer when it is not necessary. Sure, maybe your actual program uses pointers, but there is no need to add to the level of indirection before you understand the code with fewer levels of indirection.

    Your header file can be improved:
    • There is no need to #include <string.h> and <vector>.
    • The using directive is a no-no at namespace scope. Fully qualify std::map instead.
    • Although it may not matter, generally the #ifndef directive should be the very first line of the header to help compilers do their job most efficiently.


    So, I might write:
    Code:
    #ifndef CLASSROOM_H_
    #define CLASSROOM_H_
    
    #include <map>
    
    class ClassRoom {
    public:
        ClassRoom();
        ~ClassRoom();
    private:
        std::map<int, char*> myRoom;
    };
    
    #endif /* CLASSROOM_H_ */
    For your source file, the indentation needs serious work. I am also curious as to why you needed the local variable named somechar in the constructor. Anyway, your repeated use of new[] in this fashion is not exception safe, but I am not inclined to fix it because the proper way to fix it is to change the map to be a std::map<int, std::string> or std::map<int, std::vector<char>> instead, in which case the user defined destructor becomes unnecessary.

    Speaking of the destructor, as whiteflags reiterated, I would expect:
    Code:
    ClassRoom::~ClassRoom() {
        for (map<int, char*>::iterator it = myRoom.begin(); it != myRoom.end(); ) {
            cout << "Erasing:" << it->first << endl;
            delete[] it->second;
            myRoom.erase(it++);
        }
        cout << "all gone!" << endl;
    }
    Note that I assume that myRoom is now a std::map, not a pointer to a std::map.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #15
    Registered User
    Join Date
    Dec 2009
    Posts
    41
    alright, I just redid it with your suggestion, which is exactly how I was doing it before, except using a for loop rather than while. worked great. So I went back and redid it with the for loop(post increment). Worked great.

    I think my confusion was a product of a silly typo somewhere that just killed about 3 hours of my time. welp thanks a ton!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. what is an iterator
    By sigur47 in forum C Programming
    Replies: 1
    Last Post: 11-30-2011, 05:23 AM
  2. Iterator
    By MarkZWEERS in forum C++ Programming
    Replies: 19
    Last Post: 05-19-2008, 11:16 PM
  3. Connecting input iterator to output iterator
    By QuestionC in forum C++ Programming
    Replies: 2
    Last Post: 04-10-2007, 02:18 AM
  4. Do we really need iterator?
    By Antigloss in forum C++ Programming
    Replies: 3
    Last Post: 06-13-2005, 10:59 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21