Книга: Эффективное использование STL

Совет 22. Избегайте изменения ключа «на месте» в контейнерах set и multiset

Совет 22. Избегайте изменения ключа «на месте» в контейнерах set и multiset

Понять смысл этого совета нетрудно. Контейнеры set/multiset, как и все стандартные ассоциативные контейнеры, хранят свои элементы в отсортированном порядке, и правильное поведение этих контейнеров зависит от сохранения этого порядка. Если изменить значение элемента в ассоциативном контейнере (например заменить 10 на 1000), новое значение окажется в неправильной позиции, что нарушит порядок сортировки элементов в контейнере.

Сказанное прежде всего касается контейнеров map и multimap, поскольку программы, пытающиеся изменить значение ключа в этих контейнерах, не будут компилироваться:

map<int, string> m;
…
m.begin()->first = 10; // Ошибка! Изменение ключей
                       // в контейнере map запрещено
multimap<int, string> mm;
mm.begin()->first = 20; // Ошибка! Изменение ключей
                        // в контейнере multimap запрещено

Дело в том, что элементы объекта типа map<K, V> или multimap<K, V> относятся к типу pair<const K, V>. Ключ относится к типу const K и поэтому не может изменяться. Впрочем, его все же можно изменить с применением const_cast, как показано ниже. Хотите — верьте, хотите — нет, но иногда это даже нужно.

Обратите внимание: в заголовке этого совета ничего не сказано о контейнерах map и multimap. Для этого есть веские причины. Как показывает предыдущий пример, модификация ключа «на месте» невозможна для map и multimap (без применения преобразования const_cast), но может быть допустима для set и multiset. Для объектов типа set<T> и multiset<T> в контейнере хранятся элементы типа T, а не const T. Следовательно, элементы контейнеров set и multiset можно изменять в любое время, и преобразование const_cast для этого не требуется (вообще говоря, дело обстоит не так просто, но не будем забегать вперед).

Сначала выясним, почему элементы set и multiset не имеют атрибута const. Допустим, у нас имеется класс Employee:

class Employee {
public:
 …
 const string& name() const; // Возвращает имя работника
 void setName(const string& name); // Задает имя работника
 const string& title() const; // Возвращает должность
 void setTitle(const string& title); // Задает должность
 int idNumber() const; // Возвращает код работника
 …
}

Объект содержит разнообразные сведения о работнике. Каждому работнику назначается уникальный код, возвращаемый функцией idNumber. При создании контейнера set с объектами Employee было бы вполне разумно упорядочить его по кодам работников:

struct IDNumberLess:
 public binary_function<Employee, Employee, bool> { // См. совет 40
 bool operator() (const Employees lhs, const Employees rhs) const {
  return lhs.idNumber() < rhs. IdNumber();
 }
}
typedef set<Employee, IDNumberLess> EmplIDSet;
EmplIDSet se; // Контейнер set объектов
              // Employee, упорядоченных
              // по коду

С практической точки зрения код работника является ключомдля элементов данного множества, а остальные данные вторичны. Учитывая это обстоятельство, ничто не мешает перевести работника на более интересную должность. Пример:

Employee selectedID; // Объект работника с заданным кодом
…
EmpIDSet::iterator = se.find(selectedID);
if (i!=se.end()) {
 i->setTitle("Corporate Deity"); // Изменить должность
}

Поскольку мы всего лишь изменяем вторичный атрибут данных, не влияющий на порядок сортировки набора, этот фрагмент не приведет к порче данных, и он вполне допустим.

Спрашивается, почему нельзя применить ту же логику к ключам контейнеров map и multimap? Почему бы не создать контейнер map, ассоциирующий работников со страной, в которой они живут; контейнер с функцией сравнения IDNumberLess, как в предыдущем примере? И почему бы в таком контейнере не изменить должность без изменения кода работника, как в предыдущем примере?

Откровенно говоря, мне это кажется вполне логичным, однако мое личное мнение в данном случае несущественно. Важно то, что Комитет по стандартизации решил, что ключи map/multimap должны быть неизменными (const), а значения set/multiset — не должны.

Значения в контейнерах set/multiset не являются неизменными, поэтому попытки их изменения обычно нормально компилируются. Данный совет лишь напоминает вам о том, что при модификации элементов set/multiset не следует изменять ключевую часть (то есть ту часть элемента, которая влияет на порядок сортировки в контейнере). В противном случае целостность данных контейнера будет нарушена, операции с контейнером начнут приводить к непредсказуемым результатам, и все это произойдет по вашей вине. С другой стороны, это ограничение относится только к ключевым атрибутам объектов, содержащихся в контейнере. Остальные атрибуты объектов находятся в вашем полном распоряжении — изменяйте на здоровье!

Впрочем, не все так просто. Хотя элементы set/multiset и не являются неизменными, реализации могут предотвратить их возможную модификацию. Например, оператор * для set<T>::iterator может возвращать const T&, то есть результат разыменования итератора set может быть ссылкой на const-элемент контейнера! При такой реализации изменение элементов set и multiset невозможно, поскольку при любом обращении к элементу автоматически добавляется объявление const.

Законны ли такие реализации? Может, да, а может — нет. По этому вопросу Стандарт высказывается недостаточно четко, и в соответствии с законом Мерфи разные авторы интерпретируют его по-разному. В результате достаточно часто встречаются реализации STL, в которых следующий фрагмент компилироваться не будет (хотя ранее говорилось о том, что он успешно компилируется):

EmplIDSet se; // Контейнер set объектов
              // Employee, упорядоченных
              // по коду
Employee selectedID; // Объект работника с заданным кодом
…
EmpIDSet::iterator = se.find(selectedID);
if (i!=se.end()) {
 i->setTitle("Corporate Deity"); // Некоторые реализации STL
};                               // выдают ошибку в этой строке

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

Что из этого следует? К счастью, ничего особенно сложного:

• если переносимость вас не интересует, если вы хотите изменить значение элемента в контейнере set/multiset и ваша реализация STL это разрешает — действуйте. Помните о том, что ключевая часть элемента (то есть часть элемента, определяющая порядок сортировки элементов в контейнере) должна сохраниться без изменений;

• если программа должна быть переносимой, элементы контейнеров set/multiset модифицироваться не могут (по крайней мере, без преобразования const_cast).

Кстати, о преобразованиях. Вы убедились в том, что изменение вторичных данных элемента set/multiset может быть вполне оправданно, поэтому я склонен показать, как это делается — а точнее, делается правильно и переносимо. Сделать это нетрудно, но при этом приходится учитывать тонкость, о которой забывают многие программисты — преобразование должно приводить к ссылке. В качестве примера рассмотрим вызов setTitle, который, как было показано, не компилируется в некоторых реализациях:

EmpIDSet::iterator i = se.find(selectedID);
if (i != se.end()) {
 i->setTitle("Corporate Deity"); // Некоторые реализации STL
}                                // выдают ошибку в этой строке,
                                 // поскольку *i имеет атрибут const

Чтобы этот фрагмент нормально компилировался и работал, необходимо устранить константность *i. Правильный способ выглядит так:

if (i != se.end()){                                     // Устранить
 const_cast<Empioyee&>(*i).setTitle("Corporate Deity"); // константность *i
}

Мы берем объект, на который ссылается i, и сообщаем компилятору, что результат должен интерпретироваться как ссылка на (неконстантный) объект Employee, после чего вызываем setTitle для полученной ссылки. Я не буду тратить время на долгие объяснения и лучше покажу, почему альтернативное решение работает совсем не так, как можно было бы ожидать.

Многие программисты пытаются воспользоваться следующим кодом:

if (i != se.end()){                                     // Преобразовать *i
 static_cast<Employee>(*i).setTitle("Corporate Deity"); // к Employee
}

Приведенный фрагмент эквивалентен следующему:

if (i != se.end()){                            // То же самое,
 ((Employee)(*i)).setTitle("Corporate Deity"); // но с использованием
}                                              // синтаксиса С

Оба фрагмента компилируются, но вследствие эквивалентности работают неправильно. На стадии выполнения объект *i не модифицируется, поскольку в обоих случаях результатом преобразования является временный анонимный объект — копия*i, и setTitle вызывается для анонимного объекта, а не для *i! Обе синтаксические формы эквивалентны следующему фрагменту:

if (i != se.end()) {
 Employee tempCopy(*i);                // Скопировать *i в tempCopy
 tempCopy.setTitle("Corporate Deity"); // Изменить tempCopy
}

Становится понятно, почему преобразование должно приводить именно к ссылке — тем самым мы избегаем создания нового объекта. Вместо этого результат преобразования представляет собой ссылку на существующийобъект, на который указывает i. При вызове setTitle для объекта, обозначенного ссылкой, функция вызывается для *i, чего мы и добивались.

Все сказанное хорошо подходит для контейнеров set и multiset, но при переходе к map/multimap ситуация усложняется. Вспомните, что map<K, V> и multimap<K, V> содержат элементы типа pair<const K, V>. Объявление const означает, что первый компонент пары определяетсякак константа, а из этого следует, что любые попытки устранить его константность приводят к непредсказуемому результату. Теоретически реализация STL может записывать такие данные в область памяти, доступную только для чтения (например, в страницу виртуальной памяти, которая после исходной записи защищается вызовом системной функции), и попытки устранить их константность в лучшем случае ни к чему не приведут. Я никогда не слышал о реализациях, которые бы поступали подобным образом, но если вы стремитесь придерживаться правил, установленных в Стандарте, — никогдане пытайтесь устранять константность ключей в контейнерах map и multimap.

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

Многие преобразования (включая только что рассмотренные) не являются абсолютно необходимыми. Самый безопасный и универсальный способ модификации элементов контейнера set, multiset, map или multimap состоит из пяти простых шагов.

1. Найдите элемент, который требуется изменить. Если вы не уверены в том, как сделать это оптимальным образом, обратитесь к рекомендациям по поводу поиска в совете 45.

2. Создайте копию изменяемого элемента. Помните, что для контейнеров map/multimap первый компонент копии не должен объявляться константным — ведь именно его мы и собираемся изменить!

3. Удалите элемент из контейнера. Обычно для этого используется функция erase (см. совет 9).

4. Измените копию и присвойте значение, которое должно находиться в контейнере.

5. Вставьте новое значение в контейнер. Если новый элемент в порадке сортировки контейнера находится в позиции удаленного элемента или в соседней позиции, воспользуйтесь «рекомендательной» формой insert, повышающей эффективность вставки от логарифмической до постоянной сложности. В качестве рекомендации обычно используется итератор, полученный на шаге 1.

EmpIDSet se; // Контейнер set объектов Employee, упорядоченных по коду
Employee SelectedID; // Объект работника с заданным кодом
…
EmpIDSet::iterator i = // Этап 1: поиск изменяемого элемента
 se.find(selectedID);
if (i != se.end()) {
 Employee e(*i); //Этап 2: копирование элемента
 se.erase(i++); // Этап 3: удаление элемента.
                // Увеличение итератора
                // сохраняет его
                // действительным (см. совет 9)
 e.setTitle("Corporate Deity"); // Этап 4: модификация копии
 se.insert(i, е); // Этап 5: вставка нового значения.
                  // Рекомендуемая позиция совпадает
                  // с позицией исходного элемента
}

Итак, при изменении «на месте» элементов контейнеров set и multiset следует помнить, что за сохранение порядка сортировки отвечает программист.

Оглавление книги