Possible problem with iterators in STL

[babak]

Hi everyone
I have a problem with Iterators and containers in STL that hopefully
someone can help me with.
This is what I try to do:


I have an associative (map) container and I have a function where I
with the help of iterators want to search through the container and
remove a certain object in the container.
Here is part of the code in that function:


//Move from timers map container to stale list container
Timers::iterator start(_timers.begin());
Timers::iterator last(_timers.end());


while (start != last)
{
if(compObj.Compare(start->second))
{
_stale.push_back(start->second);


start = _timers.erase(start);


}
else
{
++start;
}



}


The function works correctly most of the time (maybe 8 out of 10
times). It then goes through the while loop 3 times. The first time it
goes into the if case and erases the object and the other 2 times it
goes to the else case and then it jumps out of the while loop.
But sometimes it does not behave correctly. In those cases it behaves
like I described above until the third time in the while loop. The
function then goes to the else case but never leaves it (i.e it comes
to the line before ++start but not the line after it when I use
printfs).

I believe that all the initializations are made correctly so the only
thing I can come up with is that something goes wrong with the
iterator. Is there any possibility that I somehow e.g try to increase
the iterator out of bounds or make some other error which could lead to

very strange behaviour? Any other suggestions of what could lead to
this strange behaviour?


Thanks for your help.
Regards.
/Babak

 

[Robbie Hatley]

Hi everyone
I have a problem with Iterators and containers in STL that hopefully
someone can help me with.
This is what I try to do:


I have an associative (map) container and I have a function where I
with the help of iterators want to search through the container and
remove a certain object in the container.
Here is part of the code in that function:


//Move from timers map container to stale list container
Timers::iterator start(_timers.begin());
Timers::iterator last(_timers.end());


while (start != last)
{
if(compObj.Compare(start->second))
{
_stale.push_back(start->second);


start = _timers.erase(start);


}
else
{
++start;
}



}

What is "_timers"?

What is "Timers"?

What is "start"?

What is "last"?

What is "CompObj"?

What is your key type?

What is your value type?

Which is your std::map object? _timers ?

How come your iterators aren't declared like this:???

std::map<KeyType, ValueType>::iterator Current;
Current = _timers.begin();

What is your program supposed to do?

You need to post a compilable program that demonstrates the bug.
Since you don't even tell us the data type of your objects,
or show us the definitions of your classes and/or functions,
how can we help?

I'll guess "_timers" is your map object. In that case,
don't use "start" and "last". "start" is not descriptive
of how you're using this iterator, and "last" might get stale.
Since a map is a b-tree, if it re-balances itself after insertions
or deletions, old pointers may now point to la-la-land.

Instead, put "_timers.end()" directly in your while test, like so:


while (Current != _timers.end())
{
// etc
}


If you give more info, I might be able to help more.


Cheers,
Robbie Hatley
Tustin, CA, USA
email: lonewolfintj at pacbell dot net
web: home dot pacbell dot net slant earnur slant

 

[BigBrian]

What is "start"?
What is "last"?

start and last are defined in the code snippet.

How come your iterators aren't declared like this:???

std::map<KeyType, ValueType>::iterator Current;
Current = _timers.begin();

Because he has a typedef in his Timers class?

What is your program supposed to do?

I think the OP explained this.

I'll guess "_timers" is your map object. In that case,
don't use "start" and "last". "start" is not descriptive
of how you're using this iterator, and "last" might get stale.
Since a map is a b-tree, if it re-balances itself after insertions
or deletions, old pointers may now point to la-la-land.

Yes, STL iterators can be invalidated when operations are called which
change the size of the container. Thus, last may be invalidated, and
start may actually be assigned end() after the call to erase, but since
last may be invalid, the while( start != last ) may succeed eventough
you're really at the end of the map.

email: lonewolfintj at pacbell dot net

LOL, does this really help? ( it seems like a simple substitution of
'at' => '@' and 'dot' => '.' wouldn't be enough to disguise it from a
script. )

 

[Kai-Uwe Bux]

news:[email protected]... [snip]
I'll guess "_timers" is your map object. In that case,
don't use "start" and "last". "start" is not descriptive
of how you're using this iterator, and "last" might get stale.
Since a map is a b-tree, if it re-balances itself after insertions
or deletions, old pointers may now point to la-la-land.

Yes, STL iterators can be invalidated when operations are called which
change the size of the container. Thus, last may be invalidated, and
start may actually be assigned end() after the call to erase, but since
last may be invalid, the while( start != last ) may succeed eventough
you're really at the end of the map.

For associative containers from the standard library, those worries about
invalidating iterators do not apply, see[23.1.2/8] (Associative
containers):

The insert members shall not affect the validity of iterators and
references to the container, and the erase members shall invalidate
only iterators and references to the erased elements.


Best

Kai-Uwe Bux

 

[babak]

Thanks for your help. I will try what you suggested.

The reason I didn't include more of my code is because it is very
complicated and large. I don't think it would help if I included more
of the code. To send an executable program is impossible.
But here is some part of the code that I think is related to the
function that I have problem with. I hope it will make sence to you.
Let me know if you have other suggestions of what could be wrong


timer.cpp
------------
void
TimerManager::Remove(TimerComp compObj)
{
....


//Move from timers map to stale list
Timers::iterator start(_timers.begin());
Timers::iterator last(_timers.end());


while (start != last)
{
if(compObj.Compare(start->second))
{
_stale.push_back(start->second);

start = _timers.erase(start);

}
else
{
++start;
}

}
}


timer.h
----------
class TimerBase
{
...
}

typedef Private::TimerBase* TimerHandle;


typedef std::multimap<uint64, TimerHandle> Timers;

Timers _timers;


//Used in Remove functions
class TimerComp
{
TimerComp& operator=(const TimerComp&);
public:
TimerComp(const TimerHandle v) : _type(HANDLE), _handle(v),
_string(), _object(0) {;}
TimerComp(const std::wstring& v) : _type(STRING), _handle(0),
_string(v), _object(0) {;}
TimerComp(const void* v) : _type(OBJECT), _handle(0), _string(),
_object(v) {;}

bool Compare(TimerHandle& v) const
{
if (_type == HANDLE && v == _handle) {
return TRUE;
}
else if (_type == STRING && v->GetName() == _string) {
return TRUE;
}
else if (_type == OBJECT && v->GetObject() == _object) {
return TRUE;
}

return FALSE;
}


private:
enum TimerCompType{HANDLE,STRING, OBJECT};
TimerCompType _type;
const TimerHandle _handle;
const std::wstring _string;
const void* _object;
};


BigBrian skrev:

 

[Robbie Hatley]

start and last are defined in the code snippet.

No, they are not. Since we don't know what "Timers" are/is,
then what is "start", "last"?

Because he has a typedef in his Timers class?

Maybe? Maybe not? We don't know? Who knows?
I don't believe in God; do you?
(Otherwise I'd say "...God knows...")

I think the OP explained this.

No, hir did not. The only clues we are given are "_timers"
and "Timers", which might hint that the program has something
to do with timing something. But then again, it might not.
Who knows?

Yes, STL iterators can be invalidated when operations are called which
change the size of the container. Thus, last may be invalidated, and
start may actually be assigned end() after the call to erase, but since
last may be invalid, the while( start != last ) may succeed eventough
you're really at the end of the map.

That's true of some containers and situations, not others.

std::list iterators tend to remain valid even when items are
added/removed. (No reallocation.) (I'm talking about
iterators to items that have NOT yet been removed here!)

vectors and dequeues are more iffy. If the size increases,
old iterators are no-longer guaranteed to be valid.

maps and multimaps are MUCH more iffy, because they're based
on b-trees, which tend to contain balancing code that makes
sure the tree doesn't get too "lop-sided"; this involves
frequent reallocation, which invalidates old iterators.

Which is why I told the OP to put "!=_timers.end()" directly
in his while test.

LOL

What's so amusing?

does this really help?
Yes.

it seems like a simple substitution of 'at' => '@'
and 'dot' => '.' wouldn't be enough to disguise it from a
script.

If the script is written by a rather good Perl hacker, maybe.

Do you get the impression that these snotwads that are trying
to push organ lengtheners and viagra are top programmers?
I don't. My guess is, most of them are lusers who can't hack
a line of code and are only interested in a quick buck. Sure,
if they buy a fancy script from someone, they can cause mischief.
But I doubt most of them are even that inventive.


Cheers,
Robbie Hatley
Tustin, CA, USA
email: lonewolfintj at pacbell dot net
web: home dot pacbell dot net slant earnur slant

 

[Kai-Uwe Bux]

Robbie Hatley wrote:

[snip]

maps and multimaps are MUCH more iffy, because they're based
on b-trees, which tend to contain balancing code that makes
sure the tree doesn't get too "lop-sided"; this involves
frequent reallocation, which invalidates old iterators.

a) The standard specifies that iterators remain valid after insertions and
that only iterators to erased elements are invalidated be deletions.

b) Rebalancing a tree can be done without moving nodes. All you need to do
is redirecting pointers. But that is implementation specific anyway.


Best

Kai-Uwe Bux

 

[babak]

Sorry, for clarification: we are using semaphores (that have been
tested before and have a track of working) so no other process should
be able to try to insert or erase from the container while we are using
it.
I also tried what Robbie Hatley suggested (see above) but with the same
result.

Any other suggestions, anyone?

Thanks for your help.
/Babak

 

[Kai-Uwe Bux]

a) Please do not top-post.

Thanks for your help. I will try what you suggested.

The reason I didn't include more of my code is because it is very
complicated and large. I don't think it would help if I included more
of the code. To send an executable program is impossible.
But here is some part of the code that I think is related to the
function that I have problem with. I hope it will make sence to you.
Let me know if you have other suggestions of what could be wrong


timer.cpp
------------
void
TimerManager::Remove(TimerComp compObj)
{
....


//Move from timers map to stale list
Timers::iterator start(_timers.begin());
Timers::iterator last(_timers.end());

The standard reserves names that start with an underscore in global
namespace for the implementation.

while (start != last)
{
if(compObj.Compare(start->second))
{
_stale.push_back(start->second);

start = _timers.erase(start);

}
else
{
++start;
}

}
}

This loop looks fine except for the underscores. This, however, assumes that
compObj.Compare() actually works as expected.

timer.h
----------
class TimerBase
{
...
}

typedef Private::TimerBase* TimerHandle;


typedef std::multimap<uint64, TimerHandle> Timers;

Timers _timers;


//Used in Remove functions
class TimerComp
{
TimerComp& operator=(const TimerComp&);
public:
TimerComp(const TimerHandle v) : _type(HANDLE), _handle(v),
_string(), _object(0) {;}
TimerComp(const std::wstring& v) : _type(STRING), _handle(0),
_string(v), _object(0) {;}
TimerComp(const void* v) : _type(OBJECT), _handle(0), _string(),
_object(v) {;}

bool Compare(TimerHandle& v) const
{
if (_type == HANDLE && v == _handle) {
return TRUE;
}
else if (_type == STRING && v->GetName() == _string) {
return TRUE;
}
else if (_type == OBJECT && v->GetObject() == _object) {
return TRUE;
}

return FALSE;
}

It is *very* hard to tell if this comparison function actually works
correctly. To me it is not clear how v->GetName() is guaranteed to make
sense just because this->_type happens to be STRING.

private:
enum TimerCompType{HANDLE,STRING, OBJECT};
TimerCompType _type;
const TimerHandle _handle;
const std::wstring _string;
const void* _object;
};

Best

Kai-Uwe Bux