Совет 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 К, V>. Ключ относится к типу const К и поэтому не может изменяться. Впрочем, его все же можно изменить с применением const_cast, как показано ниже. Хотите — верьте, хотите — нет, но иногда это даже нужно.

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

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

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 с объектами Emplоуее было бы вполне разумно упорядочить его по кодам работников:

struct IDNumberLess:

public binary_function<Employee.Employee,bool> { // См. совет 40

bool operator() (const Employees Ihs,

const Employees rhs) const

{

return lhs.idNumber() < rhs. IdNumber();

}

}

typedef set<Employee.IDNumberLess> EmplIDSet;

EmplIDSet se;// Контейнер set объектов

// Employee, упорядоченных

// по коду

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

Employee selectedID;// Объект работника с заданным кодом

EmpIDSet::iterator =se.find(selectedlD);

if (i!=se.end()){

i->setTitle("Corporate Dety"); // Изменить должность

}

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

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

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

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

Впрочем, не все так просто. Хотя элементы set/multiset и не являются неизменными, реализации могут предотвратить их возможную модификацию. Например, оператор* для set<T>: iterator может возвращать const Т&, то есть результат разыменования итератора 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: iterator i= se.find(selectedlD);

if (i!=se.end()) { Employee e(*i);

se.erase(i++):

// Этап 1: поиск изменяемого элемента

//Этап 2: копирование элемента

//Этап 3: удаление элемента.

//Увеличение итератора

//сохраняет его

//действительным (см. совет 9)

e.setTitle("Corporate Deity"); // Этап 4: модификация копии

se.insert(i,е):

// Этап 5: вставка нового значения.

//Рекомендуемая позиция совпадает

//с позицией исходного элемента

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