Мы знаем, что вы уже предпочитаете использовать стандартные контейнеры вместо написанных вручную. Но какой именно контейнер следует использовать? Что должно (и что не должно) храниться в контейнерах и почему? Как следует заполнять контейнеры? Какие важные идиомы надо знать?
В этом разделе имеются ответы на все перечисленные (и не только) вопросы. И не случайно, что три первые рекомендации в нем содержат слова "Используйте
vector
...".
В этом разделе мы считаем наиболее значимой рекомендацию 79 — "Храните в контейнерах только значения или интеллектуальные указатели". К ней мы добавим — если даже вы не планируете применять [Boost] и [C++TR104] для иных целей, все равно воспользуйтесь их интеллектуальным указателем
Очень важно использовать "правильный контейнер". Если у вас есть весомые причины выбрать определенный тип контейнера, используйте тот контейнер, который наиболее подходит для вашей задачи.
Если конкретных предпочтений нет, возьмите
vector
и спокойно работайте, зная, что вы сделали верный выбор. Обсуждение
Ниже представлены три главных аспекта, которые касаются программирования вообще, и выбора контейнера в частности.
• Следует писать в первую очередь корректный, простой и понятный код (см. рекомендацию 6). Предпочтителен выбор контейнера, который позволит вам написать наиболее понятный код. Так, если вам требуется вставка в определенную позицию, используйте последовательный контейнер (например,
vector
,
list
). Если вам нужен итератор произвольного доступа, выберите
vector
,
deque
или
string
. Если нужен словарный поиск наподобие
c[0]=42;
, воспользуйтесь ассоциативным контейнером (например,
set
,
map
) — но если вам требуется упорядоченная ассоциативная коллекция, то вы не можете использовать контейнеры с использованием хеширования (нестандартные
hash_
… или стандартные
unordered_
… контейнеры).
• Вопросы эффективности при написании должны учитываться только тогда и там, где это действительно необходимо (см. рекомендацию 8). Если на основании проведенных измерений с реальными данными доказано, что скорость поиска действительно критична, можно воспользоваться контейнерами с использованием хеширования (нестандартными
hash_
… или стандартными
unordered_
… контейнерами), затем — отсортированным
vector
, затем —
set
или
map
, обычно в приведенном порядке. Даже в этой ситуации отличия асимптотического времени работы (с использованием "большого O", например, линейное и логарифмическое время работы; см. рекомендацию 7) имеет значение, только если контейнеры достаточно велики, чтобы постоянные множители перестали играть роль. Для контейнеров, содержащих небольшие объекты наподобие double, для преодоления влияния постоянных множителей обычно требуется по крайней мере несколько тысяч элементов.
• Там, где это возможно и разумно, лучше писать транзакционный код со строгой гарантией безопасности код (см. рекомендацию 71), и не использовать некорректные объекты (см. рекомендацию 99). Если для вставки и удаления элементов вам требуется транзакционная семантика, или если необходимо минимизировать недействительность итераторов, лучше воспользоваться контейнерами на основе узлов (например,
list
,
set
,
map
).
В противном случае следуйте совету Стандарта: "
vector
представляет собой тип последовательности, который нужно использовать по умолчанию" ([C++03] §23.1.1).
Если вы сомневаетесь в данном совете, спросите сами себя — действительно ли у вас есть непреодолимые причины не использовать стандартный контейнер
vector
, который обладает следующими свойствами.
• Гарантирует минимальные среди всех контейнеров накладные расходы памяти на хранение (ноль байтов на объект).
• Гарантирует наивысшую среди всех контейнеров скорость доступа к хранимым элементам.
• Гарантирует локальность ссылок, означающую, что объекты, находящиеся рядом друг с другом в контейнере, гарантированно находятся рядом и в памяти, что не гарантирует ни один другой контейнер.
• Гарантирует совместимость размещения в памяти с размещением, используемым языком программирования С, в отличие от остальных стандартных контейнеров (см. рекомендации 77 и 78).
• Гарантирует наличие самых гибких итераторов (произвольного доступа).
• Почти гарантированно имеет самые быстрые итераторы (указатели или классы со сравнимой производительностью, которые зачастую работают в окончательной (не отладочной) версии с той же скоростью, что и указатели).
Есть ли у вас причины не использовать такой контейнер по умолчанию? Если у вас есть такая причина, связанная с одним из трех аспектов в начале этой рекомендации, то все замечательно — просто воспользуйтесь наиболее подходящим для вас контейнером. Если такой причины нет — возьмите
vector
и спокойно работайте, зная, что вы сделали верный выбор.
И последнее — лучше использовать контейнеры и алгоритмы стандартной библиотеки, а не стороннего производителя или разработанные самостоятельно.
Примеры
Пример. Использование
vector
для небольших списков. Распространенное заблуждение — использовать
list
только потому, что "очевидно, что
list
—подходящий тип для выполнения операций со списком", таких как вставка в средину последовательности. Тип
vector
для небольших списков практически всегда превосходит тип
list
. Несмотря на то, что вставка в средину последовательности требует линейного времени работы у
vector
, и постоянного — у
list
, вектор с небольшим количеством элементов обычно справляется с этой задачей быстрее — за счет меньшего постоянного множителя; преимущества асимптотического времени работы
list
проявляются только при больших количествах элементов в контейнере.
Таким образом, используйте
vector
, пока размеры данных не потребуют иного выбора (см. рекомендацию 7), либо пока не станет существенной обеспечение строгой гарантии безопасности при возможной генерации исключений копирующим конструктором или копирующим оператором присваивания типа объектов, хранящихся в контейнере. В последнем случае может оказаться важным, что контейнер
list
обеспечивает строгую гарантию безопасности для операции вставки в коллекцию таких типов. Ссылки
Избегайте реализации абстракция массива посредством массивов в стиле С, арифметики указателей и примитивов управления памятью. Использование
vector
или
string
не только сделает проще вашу жизнь, но и позволит написать более безопасную и масштабируемую программу. Обсуждение
Сегодня едва ли не основными вопросами при написании программного обеспечения являются вопросы безопасности и переполнения буфера. Ограничения, связанные с фиксированным размером массивов, доставляют немало беспокойства, даже если приложению удается остаться в рамках корректности. Все эти проблемы связаны с использованием старых средств С, таких как встроенные массивы, указатели и их арифметика, а также управление памятью вручную вместо таких высокоуровневых концепций, как буферы, векторы и строки.
Вот некоторые из причин, по которым массивам в стиле С следует предпочесть стандартные средства С++.
• Они автоматически управляют собственной памятью. Больше не требуется никаких фиксированных буферов с размером "большим, чем любая разумная длина" ("бомба с часовым механизмом" — вот как правильно прочесть это определение), или сплошных перераспределений памяти при помощи
reallос
и соответствующих обновлений указателей.
• У них богатый интерфейс. Вы легко и выразительно можете реализовать сложную функциональность.
• Они совместимы с моделью памяти в С.
vector
и
string::c_str
могут быть переданы функциям API на языке С. В частности, в С++
vector
служит "переходником" к С и другим языкам программирования (см. рекомендации 76 и 78).
• Они обеспечивают расширенные возможности проверки. Стандартные средства позволяют реализовать (в отладочном режиме) итераторы и операторы индексирования, которые способны выявить большой класс ошибок памяти. Многие из современных реализаций стандартной библиотеки предоставляют такие отладочные возможности — воспользуйтесь ими! (См. рекомендацию 83.)
• Они практически не снижают эффективность ваших программ. В классах
vector
и
string
при выборе между эффективностью и безопасностью решение принимается в пользу эффективности (естественно, не в отладочном режиме). Тем не менее, стандартные средства оказываются гораздо лучшей платформой для создания безопасных компонентов, чем обычные массивы и указатели.
• Они стимулируют оптимизацию. Современные реализации стандартной библиотеки включают оптимизации, о которых многие из нас просто никогда бы и не подумали.
Применение массива может быть оправданно, когда его размер фиксирован на стадии компиляции (например,
float[3]
для трехмерной точки; переход к четвертому измерению все равно потребует перепроектирования программы). Ссылки
служат шлюзом для сообщения с API на других языках. Однако не полагайтесь на то, что итераторы являются указателями; для получения адреса элемента, на который ссылается
vector<T>::iterator iter
, используйте выражение
&*iter
. Обсуждение
vector
(в первую очередь) и
string::c_str
и
string::data
(во вторую) представляют собой наилучшие способы обмена данными с API на других языках вообще и с библиотеками на С в частности.
Данные
vector
всегда хранятся последовательно, так что получение адреса первого элемента вектора дает указатель на его содержимое. Используйте
&*v.begin()
,
&v[0]
или
&v.front()
для получения указателя на первый элемент
v
. Для получения указателя на n-й элемент вектора лучше сначала провести арифметические вычисления, а затем получить адрес (например,
&v.begin()[n]
или
&v[n]
) вместо получения указателя на начало данных с последующим применением арифметики указателей (например,
(&v.front())[n]
). Это связано с тем, что в первом случае в отладочной реализации выполняется проверка на доступ к элементу за пределами
v
(см. рекомендацию 83).
Нельзя полагаться на то, что
v.begin()
возвращает указатель на первый элемент или, в общем случае, что итераторы вектора являются указателями. Хотя некоторые реализации STL определяют
vector<T>::iterator
как обычный указатель
T*
, итераторы могут быть (и все чаще так оно и есть) полноценными типами (еще раз см. рекомендацию 83).
Хотя в большинстве реализаций для
string
также используется непрерывный блок памяти, это не гарантируется стандартом, так что никогда не используйте адрес символа в строке, считая его указателем на все содержимое строки. Хорошая новость заключается в том, что функция
string::c_str
всегда возвращает строку в стиле С с завершающим нулевым символом (
string::data
также возвращает указатель на непрерывный блок памяти, но не гарантирует наличия завершающего нулевого символа).
Когда вы передаете указатель на данные объекта
v
типа
vector
, код на языке С может как читать, так и записывать элементы
v
; однако он не должен выходить за границы данных. Хорошо продуманный API на языке С должен получать наряду с указателем либо максимальное количество объектов (до
v.size()
), либо указатель на элемент, следующий за последним (
&*v.begin()+v.size()
).
Если у вас есть контейнер объектов типа
T
, отличный от
vector
или
string
, и вы хотите передать его содержимое (или заполнить его) функции API на другом языке программирования, которая ожидает указатель на массив объектов типа
T
, скопируйте содержимое контейнера в (или из)
vector<T>
, который может непосредственно сообщаться с такими функциями. Ссылки
Храните к контейнерах объекты-значения. Контейнеры полагают, что их содержимое имеет тип значения, включая непосредственно хранящиеся значения, интеллектуальные указатели и итераторы.
Обсуждение
Наиболее распространенное использование контейнеров — для непосредственного хранения значений (например,
vector<int>, set<string>
). В случае контейнеров указателей, если контейнер владеет объектами, на которые указывает, то лучше использовать контейнер интеллектуальных указателей со счетчиком ссылок (например,
list<shared_ptr<Widget> >
); в противном случае можно выбрать контейнер обычных указателей (например,
list<Widget*>
) или иных значений, подобных указателям — таких как итераторы (например,
list<vector<Widget>::iterator>
). Примеры
Пример 1.
auto_ptr
. Объекты
auto_ptr<T>
не являются объектами-значениями из-за своей семантики передачи владения при копировании. Использование контейнера объектов
auto_ptr
(например,
vector<auto_ptr<int> >
) должно привести к ошибке компиляции. Но даже в случае успешной компиляции никогда не пишите такой код — вместо этого вам следует использовать контейнер интеллектуальных указателей
shared_ptr
.
Пример 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. Индексные контейнеры. Если вам нужен контейнер, хранящий объекты, и доступ к ним с использованием разных видов упорядочения без пересортировки основного контейнера, вы можете воспользоваться вторичным контейнером, который "указывает в" основной контейнер, и отсортировать его различными способами с применением предикатов сравнения с разыменованием. Однако вместо контейнера указателей лучше использовать контейнер объектов типа
везде, где это возможно. Если для вас не важна позиция вставки нового объекта, лучше всего использовать для добавления элемента в последовательность функцию
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). Ссылки
При добавлении элементов в контейнер лучше использовать операции с диапазонами (т.е. функцию
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
) с последующими индивидуальными вставками в контейнер. Ссылки
Для того чтобы действительно избавиться от излишней емкости контейнера, воспользуйтесь трюком с использованием обмена, а для реального удаления элементов из контейнера — идиомой
erase
-
remove
. Обсуждение
Некоторые контейнеры (например,
vector, string
,
deque
) могут иметь "лишнюю" емкость, которая больше не будет использоваться. Хотя стандартная библиотека C++ не предоставляет гарантированного способа для удаления излишней емкости, следующая идиома на практике оказывается вполне работоспособной:
container<T>(c).swap(c); // Идиома "горячей посадки" для
// устранения излишней емкости
// контейнера
Для того чтобы полностью опустошить
c
, удалив все элементы и убрав всю емкость, идиома должна выглядеть следующим образом:
container<T>().swap(c); // Идиома для удаления всего
// содержимого и емкости
Кроме того, обычно для новичков в программировании с использованием STL оказывается сюрпризом то, что алгоритм
remove
в действительности не удаляет элементы из контейнера. Понятно, что данный алгоритм на это не способен — ведь алгоритм работает только с диапазоном итераторов и не может ничего реально удалить из контейнера без вызова функции-члена контейнера, обычно
erase
. Удаление сводится к перемещению элементов, которые должны быть "удалены", и возврату итератора, указывающего на элемент, следующий за последним неудаленным. Для реального удаления элементов из контейнера после вызова
remove
следует вызвать
erase
— воспользоваться идиомой
erase
-
remove
. Например, для реального удаления всех элементов, равных value, из контейнера с, можно написать:
Описанная идиома "горячей усадки" не работает с реализациями
std::string
с копированием при записи. Обычно работает вызов
s.reserve(0)
или такой трюк, как
string(s.begin(), s.end()).swap(s);
, в котором использован конструктор на основе двух итераторов. На практике эти методы обычно работают и устраняют излишнюю емкость. (Было бы еще лучше, чтобы реализации
std::string
не использовали такой устаревший метод оптимизации, как копирование при записи; см. [Sutter02].) Ссылки
