Герб Саттер - Стандарты программирования на С++. 101 правило и рекомендация
Пример 2. Гетерогенные контейнеры. Для того чтобы получить контейнер, хранящий и владеющий объектами различных, но связанных типов, например, типов, производных от общего базового класса, лучше использовать container<shared_ptr<Base> >. Альтернативой является хранение прокси-объектов, невиртуальные функции которых передают вызовы соответствующим виртуальным функциям реальных объектов.
Пример 3. Контейнеры типов, не являющихся значениями. Для того чтобы хранить объекты, несмотря на невозможность их копирования или другое их поведение, делающее их типами, не являющимися значениями (например, DatabaseLock или TcpConnection), их следует хранить опосредованно, с использованием интеллектуальных указателей (например, container<shared_ptr<DatabaseLock> > или container<shared_ptr<TcpConnection> >).
Пример 4. Необязательные значения. Если вам нужен контейнер map<Thing,Widget>, но некоторые Thing не имеют связанных с ними объектов Widget, можно использовать map<Thing, shared_ptr<Widget> >.
Пример 5. Индексные контейнеры. Если вам нужен контейнер, хранящий объекты, и доступ к ним с использованием разных видов упорядочения без пересортировки основного контейнера, вы можете воспользоваться вторичным контейнером, который "указывает в" основной контейнер, и отсортировать его различными способами с применением предикатов сравнения с разыменованием. Однако вместо контейнера указателей лучше использовать контейнер объектов типа MainContainer::iterator (которые являются значениями).
Ссылки[Allison98] §14 • [Austern99] §6 • [Dewhurst03] §68 • [Josuttis99] §5.10.2 • [Koenig97] §5 • [Meyers01] §3, §7-8 • [SuttHysl04b]
80. Предпочитайте push_back другим способам расширения последовательности
Используйте push_back везде, где это возможно. Если для вас не важна позиция вставки нового объекта, лучше всего использовать для добавления элемента в последовательность функцию push_back. Все прочие средства могут оказаться как гораздо менее быстрыми, так и менее понятными.
ОбсуждениеВы можете вставить элементы в последовательность в разных точках с использованием insert; добавить элементы в последовательность можно разными способами, включая следующие:
vector<int> vec; // vec пуст
vec.resize(vec.size() + 1, 1); // vec содержит { 1 }
vec.insert(vec.end(), 2); // vec содержит { 1, 2 }
vec.push_back(3); // vec содержит { 1, 2, 3 }
Среди прочих методов push_back единственный имеет постоянное амортизированное время работы. Время работы других методов хуже — вплоть до квадратичного. Излишне говорить, что при больших размерах данных плохое время работы препятствует масштабируемости (см. рекомендацию 7).
Магия push_back проста: эта функция увеличивает емкость экспоненциально, а не на фиксированное значение. Следовательно, количество перераспределений памяти и копирований быстро уменьшается с увеличением размера. В случае контейнера, который заполняется с использованием только лишь функции push_back, каждый элемент копируется в среднем только один раз — независимо от конечного размера контейнера.
Конечно, resize и insert могут воспользоваться той же стратегией, но это уже зависит от реализации; гарантию дает только push_back.
Алгоритмы не могут непосредственно обращаться к push_back, поскольку они не имеют доступа к контейнерам. Вы можете потребовать от алгоритма использовать push_back, воспользовавшись back_inserter.
ИсключенияЕсли вы добавляете не один элемент, а диапазон, то даже если добавление выполняется в конец контейнера, лучше использовать функцию для вставки диапазона значений (см. рекомендацию 81).
Экспоненциальный рост приводит к расточительному выделению памяти. Для тонкой настройки роста можно явно вызвать функцию reserve — функции push_back, resize и подобные не будут перераспределять память, если ее достаточно для работы. Для получения вектора "правильного размера" следует воспользоваться идиомой "горячей посадки" (см. рекомендацию 82).
Ссылки[Stroustrup00] §3.7-8, §16.3.5, §17.1.4.1
81. Предпочитайте операции с диапазонами операциям с отдельными элементами
При добавлении элементов в контейнер лучше использовать операции с диапазонами (т.е. функцию insert, которая получает пару итераторов), а не последовательность вызовов функции для вставки одного элемента. Вызов функции для диапазона обычно проще написать, легче читать, и он более эффективен, чем явный цикл (см. также рекомендацию 84).
ОбсуждениеЧем больший контекст передается функции, тем больше вероятность того, что она сможет лучше распорядиться полученной информацией. В частности, когда вы вызываете функцию и передаете ей пару итераторов, указывающих некоторый диапазон, она может выполнить оптимизацию, основанную на знании количества объектов, которые должны быть добавлены (вычисляемое как distance(first, last)).
To же самое можно сказать и об операциях "повторить n раз", например, о конструкторе vector, который получает количество повторений и значение.
ПримерыПример 1. vector::insert. Пусть вам надо добавить n элементов в vector v. Многократный вызов v.insert(position,x) может привести к неоднократному перераспределению памяти, когда вектор v имеет недостаточно места для размещения нового элемента. Что еще хуже, вставка каждого отдельного элемента имеет линейное время работы, поскольку она должна перенести ряд элементов, чтобы освободить требуемую позицию для вставляемого элемента, а это приводит к тому, что вставка n элементов при помощи последовательных вызовов имеет квадратичное время работы! Конечно, избежать проблемы множественного перераспределения памяти можно при помощи вызова reserve, но это не снизит количества перемещений элементов и квадратичное время работы такого алгоритма. Быстрее и проще ясно сказать, что вам надо: v.insert(position,first,last), где first и last — итераторы, определяющие диапазон элементов, которые должны быть добавлены в v. (Если first и last — входные итераторы, то возможности определить размер диапазона перед его действительным проходом нет, так что вектору v может потребоваться многократное перераспределение памяти; тем не менее, версия для вставки диапазона все равно скорее всего будет более производительной, чем вставка отдельных элементов.)
Пример 2. Создание и присваивание диапазона. Вызов конструктора (или функции присваивания), который получает диапазон итераторов, обычно выполняется быстрее, чем вызов конструктора по умолчанию (или функции clear) с последующими индивидуальными вставками в контейнер.
Ссылки[Meyers01] §5 • [Stroustrup00] §16.3.8
82. Используйте подходящие идиомы для реального уменьшения емкости контейнера и удаления элементов
Для того чтобы действительно избавиться от излишней емкости контейнера, воспользуйтесь трюком с использованием обмена, а для реального удаления элементов из контейнера — идиомой erase-remove.
ОбсуждениеНекоторые контейнеры (например, vector, string, deque) могут иметь "лишнюю" емкость, которая больше не будет использоваться. Хотя стандартная библиотека C++ не предоставляет гарантированного способа для удаления излишней емкости, следующая идиома на практике оказывается вполне работоспособной:
container<T>(c).swap(c); // Идиома "горячей посадки" для
// устранения излишней емкости
// контейнера
Для того чтобы полностью опустошить c, удалив все элементы и убрав всю емкость, идиома должна выглядеть следующим образом:
container<T>().swap(c); // Идиома для удаления всего
// содержимого и емкости
Кроме того, обычно для новичков в программировании с использованием STL оказывается сюрпризом то, что алгоритм remove в действительности не удаляет элементы из контейнера. Понятно, что данный алгоритм на это не способен — ведь алгоритм работает только с диапазоном итераторов и не может ничего реально удалить из контейнера без вызова функции-члена контейнера, обычно erase. Удаление сводится к перемещению элементов, которые должны быть "удалены", и возврату итератора, указывающего на элемент, следующий за последним неудаленным. Для реального удаления элементов из контейнера после вызова remove следует вызвать erase — воспользоваться идиомой erase-remove. Например, для реального удаления всех элементов, равных value, из контейнера с, можно написать:
