Потеря строгого слабого порядка в наборе

Question

Я думал, что STL-контейнеры set и map предоставляют элементы в строгом слабом порядке.Тем не менее, я обнаружил, что если я получаю итератор с помощью функции поиска и изменения значения элемента с помощью разыменования, он не восстанавливает порядок, что нарушает 23.1.2.2 и 23.3.3.2.Вот код, который выдает

    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;

:

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

Это ошибка в моей версии STL (MS VS 2008)?Или я не прав?

Answer 1

Итератор набора и const_iterator являются постоянными итераторами.Вы не можете изменять значения набора, только удаляя и вставляя.

Answer 2

std::map и std::set выполняют заказ только при вставке. Если вы изменяете ключи / значения существующих предметов, ничего волшебного не происходит, и результат, вероятно, не определен.

Чтобы получить желаемый эффект, необходимо удалить оригинальный элемент и вставить новый.

Answer 3

Похоже, ошибка в этой версии STL.

На моем g ++ я получаю следующую ошибку:
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&]()’

Answer 4

Изменение элемента в std::set может привести к нарушению внутреннего порядка и повреждению вашей структуры данных.Только некоторые реализации STL защищают от этого, не позволяя модифицировать то, на что указывает iterator, поэтому вам придется применять это ограничение самостоятельно.

Это похоже на запись за логический конец std::vector путем вызоваreserve (чтобы освободить место) и используя арифметику указателей - вы можете сделать это, но это повредит ваш std::vector.

Если вы хотите изменить элемент в наборе, это должно работать:

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

Вам нужно только после увеличения itr, если вы хотите продолжать использовать его.

(источник: Действующий STL , "Item 22", СкоттMeyers)

Answer 5

В общем случае вы не можете изменить ключевую часть ассоциативного элемента контейнера через итератор. Код просто не скомпилируется.

Если ваша реализация стандартной библиотеки позволяет присваивать *it = nv, это должно быть причуда этой реализации. AFAIK, это не является строго незаконным, чтобы разрешить это назначение для компиляции. Это больше вопрос качества реализации.

Назначение не будет компилироваться с реализацией Comeau. Реализация MS, по-видимому, менее ограничительна.

Answer 6

std::map и std::set не обеспечивают a строгий слабый порядок , для них требуется один.Вы должны предоставить порядок (по умолчанию std::less, который подходит для int).

Если вы измените способ заказа элемента set или map, то вы нарушаететребование как заказ не является стабильным.