Совет 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 следует помнить, что за сохранение порядка сортировки отвечает программист.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Контакты для связи на самом видном месте

Из книги автора

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


79. Храните в контейнерах только значения или интеллектуальные указатели

Из книги автора

79. Храните в контейнерах только значения или интеллектуальные указатели РезюмеХраните к контейнерах объекты-значения. Контейнеры полагают, что их содержимое имеет тип значения, включая непосредственно хранящиеся значения, интеллектуальные указатели и


6.9. Хранение контейнеров в контейнерах

Из книги автора

6.9. Хранение контейнеров в контейнерах ПроблемаИмеется несколько экземпляров стандартного контейнера (list, set и т.п.) и требуется сохранить их в еще одном контейнере.РешениеСохраните в главном контейнере указатели на остальные контейнеры. Например, можно использовать map


Совет 18. Избегайте vector

Из книги автора

Совет 18. Избегайте vector<bool> Vector<bool> как контейнер STL обладает лишь двумя недостатками. Во-первых, это вообще не контейнер STL. Во-вторых, он не содержит bool.Объект не становится контейнером STL только потому, что кто-то назвал его таковым — он становится контейнером STL лишь


Совет 47. Избегайте «нечитаемого» кода

Из книги автора

Совет 47. Избегайте «нечитаемого» кода Допустим, имеется вектор vector<int>. Из этого вектора требуется удалить все элементы, значение которых меньше х, но оставить элементы, предшествующие последнему вхождению значения, не меньшего у. В голову мгновенно приходит следующее


Множество с дубликатами (Multiset)

Из книги автора

Множество с дубликатами (Multiset) multiset - это ассоциативный контейнер, который поддерживает равные ключи (возможно, содержит множественные копии того же самого значения ключа) и обеспечивает быстрый поиск ключей.template ‹class Key, class Compare = less‹Key›, template ‹class U› class Allocator = allocator›class


6.15. Контейнеры multimap и multiset

Из книги автора

6.15. Контейнеры multimap и multiset Контейнеры map и set не допускают повторяющихся значений ключей, а multimap (мультиотображение) и multiset (мультимножество) позволяют сохранять ключи с дублирующимися значениями. Например, в телефонном справочнике может понадобиться отдельный


Совет 23 Будь на своем месте

Из книги автора

Совет 23 Будь на своем месте Как руководитель могу рассказать, что больше всего меня раздражает общение с сотрудниками, стремящимися на следующую ступеньку карьерной лестницы. Ты знаешь таких парней: оказавшись во время обеда за твоим столом, он обязательно начнет


Генерация ключа RSA.

Из книги автора

Генерация ключа RSA. Для генерации вашей собственной уникальной пары открытый/секретный ключ заданного размера, наберите:pgp -kgPGP покажет вам меню рекомендуемых размеров ключа (простой уровень, коммерческий уровень или военный уровень) и запросит требуемый размер ключа


Разделение ключа

Из книги автора

Разделение ключа Говорят, что секрет — это уже не секрет, когда его знают двое. Разделение закрытого ключа опровергает такое мнение. Хотя это и не рекомендуемая практика, разделение закрытого ключа в определённых ситуациях бывает необходимо. Например, корпоративные


Посмотрите на ещё один парк, возникший на месте лондонской свалки Николай Маслухин

Из книги автора

Посмотрите на ещё один парк, возникший на месте лондонской свалки Николай Маслухин Опубликовано 06 июня 2013 Около месяца назад «Компьютерра» писала о китайском парке Qiaoyuan, возникшем на месте городской свалки. Похожая история случилась и с


ПИСЬМОНОСЕЦ: Бег на месте

Из книги автора

ПИСЬМОНОСЕЦ: Бег на месте Автор: Тихонов КириллЗдравствуй, "Компьютерра".Во время санации шкафа обнаружил стопку "Терр" за 2006 год. Вроде всего два года прошло, а разница чувствуется: современный Pentium 4 HT… 4-мегапиксельные камеры за смешные 77 долларов… Емкие диски на 320


Вторая жизнь промышленных объектов: отель с водопадом на месте бывшей каменоломни Николай Маслухин

Из книги автора

Вторая жизнь промышленных объектов: отель с водопадом на месте бывшей каменоломни Николай Маслухин Опубликовано 10 июля 2013 Известная архитектурная компания Atkins, участвующая в международном архитектурном конкурсе, представила свой проект