if (i!=se.end()){
Employee tempCopy(*i);// Скопировать *i в tempCopy
tempCopy.setTitle("Corporate Deity");// Изменить tempCopy
}
Становится понятно, почему преобразование должно приводить именно к ссылке — тем самым мы избегаем создания нового объекта. Вместо этого результат преобразования представляет собой ссылку на существующий объект, на который указывает i. При вызове setTitle для объекта, обозначенного ссылкой, функция вызывается для *i, чего мы и добивались.
Все сказанное хорошо подходит для контейнеров set и multiset, но при переходе к map/multimap ситуация усложняется. Вспомните, что map и multimap содержат элементы типа pair. Объявление 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 следует помнить, что за сохранение порядка сортировки отвечает программист.
Совет 23. Рассмотрите возможность замены ассоциативных контейнеров сортированными векторами
Многие программисты STL, столкнувшись с необходимостью структуры данных с быстрым поиском, немедленно выбирают стандартные ассоциативные контейнеры set, multiset, map и multimap. В этом выборе нет ничего плохого, но он не исчерпывает всех возможных вариантов. Если скорость поиска действительно важна, подумайте об использовании нестандартных хэшированных контейнеров (см. совет 25). При правильном выборе хэш-функций хэшированные контейнеры могут обеспечить поиск с постоянным временем (а при неправильном выборе хэш-функций или недостаточном размере таблиц быстродействие заметно снижается, но на практике это встречается относительно редко). Во многих случаях предполагаемое постоянное время поиска превосходит гарантированное логарифмическое время, характерное для контейнеров set, map и их multi -аналогов.
Даже если гарантированное логарифмическое время поиска вас устраивает, стандартные ассоциативные контейнеры не всегда являются лучшим выбором. Как ни странно, стандартные ассоциативные контейнеры по быстродействию нередко уступают банальному контейнеру vector. Чтобы эффективно использовать STL, необходимо понимать, в каких случаях vector превосходит стандартные ассоциативные контейнеры по скорости поиска.
Стандартные ассоциативные контейнеры обычно реализуются в виде сбалансированных бинарных деревьев. Сбалансированное бинарное дерево представляет собой структуру данных, оптимизированную для комбинированных операций вставки, удаления и поиска. Другими словами, оно предназначено для приложений, которые вставляют в контейнер несколько элементов, затем производят поиск, потом вставляют еще несколько элементов, затем что-то удаляют, снова возвращаются к удалению или вставке и т. д. Главной особенностью этой последовательности событий является чередование операций вставки, удаления и поиска. В общем случае невозможно предсказать следующую операцию, выполняемую с деревом.
Во многих приложениях структуры данных используются не столь непредсказуемо. Операции со структурами данных делятся на три раздельные фазы.
1.Подготовка. Создание структуры данных и вставка большого количества элементов. В этой фазе со структурой данных выполняются только операции вставки и удаления. Поиск выполняется редко или полностью отсутствует.
2.Поиск. Выборка нужных данных из структуры. В этой фазе выполняются только операции поиска. Вставка и удаление выполняются редко или полностью отсутствуют.
3.Реорганизация. Модификация содержимого структуры данных (возможно, со стиранием всего текущего содержимого и вставкой новых элементов). По составу выполняемых операций данная фаза эквивалентна фазе 1. После ее завершения приложение возвращается к фазе 2.
В приложениях, использующих эту схему работы со структурами данных, контейнер vector может обеспечить лучшие показатели (как по времени, так и по затратам памяти), чем ассоциативный контейнер. С другой стороны, выбор vector не совсем произволен — подходят только сортированные контейнеры vector, поскольку лишь они правильно работают с алгоритмами binary_search, lower_bound, equal_range и т. д. (совет 34). Но почему бинарный поиск через вектор (может быть, отсортированный) обеспечивает лучшее быстродействие, чем бинарный поиск через двоичное дерево? Прежде всего из-за банального принципа «размер имеет значение». Существуют и другие причины, не столь банальные, но не менее истинные, и одна из них — локализованность ссылок.
Начнем с размера. Допустим, нам нужен контейнер для хранения объектов Widget. Скорость поиска является важным фактором, поэтому рассматриваются два основных кандидата: ассоциативный контейнер объектов Widget и сортированный vector. В первом случае почти наверняка будет использоваться сбалансированное бинарное дерево, каждый узел которого содержит не только Widget, но и указатели на левого и правого потомков и (обычно) указатель на родительский узел. Следовательно, при хранении одного объекта Widget в ассоциативном контейнере должны храниться минимум три указателя.
С другой стороны, при сохранении Widget в контейнере vector непроизводительные затраты отсутствуют. Конечно, контейнер vector сам по себе требует определенных затрат памяти, а в конце вектора может находиться зарезервированная память (см. совет 14), но затраты первой категории как правило невелики (обычно это три машинных слова — три указателя или два указателя с одним числом int), а пустое место при необходимости отсекается при помощи «фокуса с перестановкой» (см. совет 17). Но даже если зарезервированная память и не будет освобождена, для нашего анализа ее наличие несущественно, поскольку в процессе поиска ссылки на эту память не используются.
Большие структуры данных разбиваются на несколько страниц памяти, однако для хранения vector требуется меньше страниц, чем для ассоциативного контейнера. Это объясняется тем, что в vector объект Widget хранится без дополнительных затрат памяти, тогда как в ассоциативном контейнере к каждому объекту Widget прилагаются три указателя. Предположим, вы работаете в системе, где объект Widget занимает 12 байт, указатели — 4 байт, а страница памяти содержит 4096 байт. Если не обращать внимания на служебную память контейнера, vector позволяет разместить на одной странице 341 объект Widget, но в ассоциативном контейнере это количество уменьшается до 170. Следовательно, по эффективности расходования памяти vector вдвое превосходит ассоциативный контейнер. В средах с виртуальной памятью это увеличивает количество подгрузок страниц, что значительно замедляет работу с большими объемами данных.