iterator missunderstanding.

**somekid413** · 01-24-2012

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;
}

**laserlight** · 01-24-2012

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.

**somekid413** · 01-24-2012

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.

**somekid413** · 01-24-2012

Originally Posted by laserlight

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.

**oogabooga** · 01-24-2012

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.

**somekid413** · 01-24-2012

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');?

**laserlight** · 01-24-2012

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')).

**somekid413** · 01-26-2012

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;

}

**whiteflags** · 01-26-2012

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.

**somekid413** · 01-26-2012

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

**whiteflags** · 01-26-2012

The errors from valgrind are referring to your use of invalidated iterators.

**somekid413** · 01-26-2012

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.

**whiteflags** · 01-26-2012

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;

**laserlight** · 01-26-2012

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.

**somekid413** · 01-26-2012

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!

Thread: iterator missunderstanding.

Thread Tools

Search Thread

Display

iterator missunderstanding.

Similar Threads

what is an iterator

Iterator

Connecting input iterator to output iterator

Do we really need iterator?