Книги
чёрным по белому
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Книги
Археология Архитектура Бизнес Биология Ветеринария Военная промышленность География Геология Гороскоп Дизайн Журналы Инженерия Информационные ресурсы Искусство История Компьютерная литература Криптология Кулинария Культура Лингвистика Математика Медицина Менеджмент Металлургия Минералогия Музыка Научная литература Нумизматика Образование Охота Педагогика Политика Промышленные производства Психология Путеводители Религия Рыбалка Садоводство Саморазвитие Семиотика Социология Спорт Столярное дело Строительство Техника Туризм Фантастика Физика Футурология Химия Художественная литература Экология Экономика Электроника Энергетика Этика Юриспруденция
Новые книги
Цуканов Б.И. "Время в психике человека" (Медицина)

Суворов С. "Танк Т-64. Первенец танков 2-го поколения " (Военная промышленность)

Нестеров В.А. "Основы проэктирования ракет класса воздух- воздух и авиационных катапульных установок для них" (Военная промышленность)

Фогль Б. "101 вопрос, который задала бы ваша кошка своему ветеринару если бы умела говорить" (Ветеринария)

Яблоков Н.П. "Криминалистика" (Юриспруденция)
Реклама

Эффективное использование STL. Библиотека программиста - Мейерс С.

Мейерс С. Эффективное использование STL. Библиотека программиста — Спб.: Питер , 2002. — 224 c.
ISBN 5-94723-382-7
Скачать (прямая ссылка): effektivnoeispolzovaniestlbibliote2002.djvu
Предыдущая << 1 .. 44 45 46 47 48 49 < 50 > 51 52 53 54 55 56 .. 114 >> Следующая

Все сказанное хорошо подходит для контейнеров set и mul ti set, но при
переходе к map/multimap ситуация усложняется. Вспомните, что map<K,V> и
multimap<K,V> содержат элементы типа pair<const K.V>. Объявление const
означает, что первый компонент пары определяется как константа, а из
этого следует, что любые попытки устранить его константность приводят к
непредсказуемому результату. Теоретически реализация STL может записывать
такие данные в область памяти, доступную только для чтения (например, в
страницу виртуальной памяти, которая после исходной записи защищается
вызовом системной функции), и попытки устранить их константность в лучшем
случае ни к чему не приведут. Я никогда не слышал о реализациях, которые
бы поступали подобным образом, но если вы стремитесь придерживаться
правил, установленных в Стандарте, - никогда не пытайтесь устранять
константность ключей в контейнерах тар и mul timap.
Несомненно, вы слышали, что подобные преобразования рискованны. Надеюсь,
вы будете избегать их по мере возможности. Выполняя преобразование, вы
временно отказываетесь от страховки, обеспечиваемой системой типов, а
описанные проблемы дают представление о том, что может произойти при ее
отсутствии.
Многие преобразования (включая только что рассмотренные) не являются
абсолютно необходимыми. Самый безопасный и универсальный способ
модификации элементов контейнера set, multiset, map или mul timap состоит
из пяти простых шагов.
1. Найдите элемент, который требуется изменить. Если вы не уверены в
том, как сделать это оптимальным образом, обратитесь к рекомендациям по
поводу поиска в совете 45.
2. Создайте копию изменяемого элемента. Помните, что для контейнеров
тар/ mul timap первый компонент копии не должен объявляться константным -
ведь именно его мы и собираемся изменить!
3. Удалите элемент из контейнера. Обычно для этого используется
функция erase (см. совет 9).
4. Измените копию и присвойте значение, которое должно находиться в
контейнере.
5. Вставьте новое значение в контейнер. Если новый элемент в порядке
сортировки контейнера находится в позиции удаленного элемента или в
соседней позиции, воспользуйтесь "рекомендательной" формой i nsert,
повышающей эффективность вставки от логарифмической до постоянной
сложности. В качестве рекомендации обычно используется итератор,
полученный на шаге 1.
98 Глава 3 • Ассоциативные контейнеры
Ниже приведен знакомый пример с контейнером объектов Employee,
реализованный безопасным и переносимым способом:
EmplIDSet se; // Контейнер set объектов
// Employee, упорядоченных // по коду
Employee selectedID; // Объект работника с заданным кодом
EmpIDSet:riterator i= // Этап 1: поиск изменяемого элемента
se.find(selectedlD);
if (i!=se.end()) {
Employee e(*i): // Этап 2: копирование элемента
se.erase(i++): // Этап 3: удаление элемента.
// Увеличение итератора
// сохраняет его
// действительным (см. совет 9)
e.setTitleC'Corporate Deity"); // Этап 4: модификация копии
se.insert(i,е); // Этап 5: вставка нового значения.
// Рекомендуемая позиция совпадает
// с позицией исходного элемента
}
Итак, при изменении "на месте" элементов контейнеров set и multiset
следует помнить, что за сохранение порядка сортировки отвечает
программист.
Совет 23. Рассмотрите возможность замены ассоциативных контейнеров
сортированными векторами
Многие программисты STL, столкнувшись с необходимостью структуры данных с
быстрым поиском, немедленно выбирают стандартные ассоциативные контейнеры
set, multiset, map и multimap. В этом выборе нет ничего плохого, но он не
исчерпывает всех возможных вариантов. Если скорость поиска действительно
важна, подумайте об использовании нестандартных хэшированных контейнеров
(см. совет 25). При правильном выборе хэш-функций хэшированные контейнеры
могут обеспечить поиск с постоянным временем (а при неправильном выборе
хэш-функций или недостаточном размере таблиц быстродействие заметно
снижается, но на практике это встречается относительно редко). Во многих
случаях предполагаемое постоянное время поиска превосходит
гарантированное логарифмическое время, характерное для контейнеров set,
map и их mul ti -аналогов.
Даже если гарантированное логарифмическое время поиска вас устраивает,
стандартные ассоциативные контейнеры не всегда являются лучшим выбором.
Как ни странно, стандартные ассоциативные контейнеры по быстродействию
нередко уступают банальному контейнеру vector. Чтобы эффективно
использовать
Совет 23 99
STL, необходимо понимать, в каких случаях vector превосходит стандартные
ассоциативные контейнеры по скорости поиска.
Стандартные ассоциативные контейнеры обычно реализуются в виде
сбалансированных бинарных деревьев. Сбалансированное бинарное дерево
представляет собой структуру данных, оптимизированную для комбинированных
операций вставки, удаления и поиска. Другими словами, оно предназначено
для приложений, которые вставляют в контейнер несколько элементов, затем
Предыдущая << 1 .. 44 45 46 47 48 49 < 50 > 51 52 53 54 55 56 .. 114 >> Следующая