CODEWITHSUNDEEP
c++stliteratorset
flashnik
flashnik

Reputation: 1932

Losing strict weak ordering in set

I thought that STL containers set and map provide elements in a strict weak ordering. However, I've found that if I get an iterator through find and change element's value through dereferencing, it doesn't restore order, which violates 23.1.2.2 and 23.3.3.2. Here is the code

    int nv = 3;
set<int> s = set<int>();
s.insert(5);
s.insert(10);
s.insert(20);
s.insert(30);
for(set<int>::const_iterator cit = s.begin(); cit != s.end(); ++cit)
    cout<<*cit<<" ";
cout <<endl;
set<int>::iterator it = s.find(10);
*it = nv;
for(set<int>::const_iterator cit = s.begin(); cit != s.end(); ++cit)
    cout<<*cit<<" ";
cout <<endl;
s.insert(40);
for(set<int>::const_iterator cit = s.begin(); cit != s.end(); ++cit)
    cout<<*cit<<" ";
cout <<endl;

produces:

5 10 20 30
5 3 20 30
5 3 20 30 40

Is it a bug in my version of STL (MS VS 2008)? Or am I wrong?

Upvotes: 2

Views: 733

Answers (6)

Dawson
Dawson

Reputation: 2771

Changing an element in a std::set can violate the internal ordering and corrupt your data structure. Only some STL implementations protect against this by disallowing modifications to what the iterator points to, so you'll have to enforce that constraint yourself.

It's like writing past the logical end of a std::vector by calling reserve (to make room) and using pointer arithmetic - you can do it, but it'll corrupt your std::vector.

If you want to change an element in a set, this should work:

std::set<int> my_set;

// initialize my_set ...

std::set<int>::iterator itr = my_set.find(10);
if (itr != my_set.end()) {
    my_set.erase(itr++); // ++ avoids invalidating iterator
    my_set.insert(3);
}

You only need to post-increment itr if you want to keep using it.

(source: Effective STL, "Item 22," Scott Meyers)

Upvotes: 1

AnT stands with Russia
AnT stands with Russia

Reputation: 320631

In general case you can't modify the key portion of the associative container element through the iterator. The code simply will not compile.

If your implementation of standard library allows the *it = nv assignment, it must be a quirk of that implementation. AFAIK, it is not strictly illegal to allow this assignment to compile. It is more of a quality-of-implementation issue.

The assignment will not compile with Comeau implementation. MS implementation is apparently less restrictive.

Upvotes: 1

Zan Lynx
Zan Lynx

Reputation: 54345

Looks like a bug in that version of STL.

On my g++ I get the following error:
t2.cpp:18:8: error: assignment of read-only location ‘it.std::_Rb_tree_const_iterator<_Tp>::operator* [with _Tp = int, const _Tp& = const int&]()’

Upvotes: 2

CB Bailey
CB Bailey

Reputation: 792497

std::map and std::set don't provide a strict weak ordering, they require one. You have to provide the ordering (the default is std::less which is appropriate for int).

If you change the way an element of a set or map is ordered then you are breaking the requirement as the ordering is not stable.

Upvotes: 0

Gene Bushuyev
Gene Bushuyev

Reputation: 5538

set's iterator and const_iterator are both constant iterators. You are not allowed to modify set's values, only removing and inserting.

Upvotes: 4

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272657

std::map and std::set only perform ordering on insertion. If you change keys/values of existing items, nothing magic happens, and the result is probably undefined.

To get the desired effect, you must remove the original element, and insert a new one.

Upvotes: 4

Related Questions