Глава 6 Управление данными с помощью контейнеров

6.0. Введение

Эта глава описывает структуры данных стандартной библиотеки, используемые для хранения данных. Часто они также называются контейнерами (containers), так как они содержат («contain») хранящиеся в них объекты. Также эта глава описывает другой тип контейнеров, который не является частью стандартной библиотеки, хотя и поставляется с большинством ее реализаций — хеш-контейнер.

Часть библиотеки, которая содержит контейнеры, часто называется Standard Template Library, или STL (стандартная библиотека шаблонов), именно так она называлась до ее включения в стандарт С++. STL включает не только контейнеры, обсуждаемые в этой главе, но и итераторы и алгоритмы, которые являются еще двумя строительными блоками STL, делающими STL гибкой библиотекой общего назначения. Так как эта глава в основном посвящена стандартным контейнерам, а не STL во всем ее многообразии, я буду называть контейнеры «стандартными контейнерами», а не «контейнерами STL», как это делается во многих книгах по С++. Хотя я по мере необходимости описываю итераторы и алгоритмы, более подробно они обсуждаются в главе 7.

Стандарт C++ использует для описания набора контейнеров точную терминологию. «Контейнер» в стандартной библиотеке C++ — это структура данных, имеющая четкий интерфейс, описанный в стандарте. Например, любой класс стандартной библиотеки С++, который называет себя контейнером, должен поддерживать метод 

begin
, который не имеет параметров и возвращает 
iterator
, указывающий на первый элемент в этом контейнере. Имеется большое количество обязательных конструкторов и функций-членов, определяющих, что такое контейнер в терминах С++. Также имеются необязательные методы, реализуемые только некоторыми контейнерами обычно теми, которые могут их эффективно реализовать.

Общий набор контейнеров подразделяется на два различных типа контейнеров: последовательные контейнеры и ассоциативные контейнеры. Последовательный контейнер (обычно называемый просто последовательностью) хранит объекты в порядке, указанном пользователем, и предоставляет необходимый для доступа и обработки элементов интерфейс (в дополнение к обязательному для контейнеров). Ассоциативные контейнеры хранят элементы в упорядоченном виде и, таким образом, не позволяют вставлять элементы в определенное место, хотя для увеличения эффективности при вставке можно указать дополнительные параметры. Как последовательности, так и ассоциативные контейнеры содержат обязательный интерфейс, но только последовательности имеют дополнительный набор операций, который поддерживается только теми последовательностями, для которых он эффективно реализуем. Эти дополнительные операции с последовательностями предоставляют большую гибкость и удобство, чем стандартный интерфейс.

Это выглядит очень похоже на наследование. Последовательность — это контейнер, ассоциативный контейнер — это контейнер, но контейнер — это не последовательность и не ассоциативный контейнер. Однако это не наследование в смысле С++, а наследование с точки зрения концепции, 

vector
— это последовательность, но это самостоятельный класс. Он не наследует от класса 
container
или подобного ему (реализации стандартной библиотеки имеют свободу в реализации 
vector
и других контейнеров, но стандарт не предписывает реализации стандартной библиотеки включать базовый класс 
container
). При разработке контейнеров было приложено большое количество усилий, и если вы хотите поподробнее узнать о них, обратитесь к книге Мэтта Остерна (Matt Austern) Generic Programming and the STL (Addison Wesley).

Эта глава содержит две части. Несколько первых рецептов рассказывают, как использовать 

vector
, который является стандартной последовательностью и одной из наиболее популярных структурой данных. Они описывают, как эффективно и рационально использовать 
vector
. Остальные рецепты описывают большую часть остальных широко применяемых стандартных контейнеров, включая два нестандартных хеш-контейнера, о которых я упоминал ранее.

6.1. Использование vector вместо массивов

Проблема

Требуется сохранить элементы (встроенные типы, объекты, указатели и т.п.) в виде последовательности, обеспечить произвольный доступ к ним, и не ограничивать место хранения массивом статического размера.

Решение

Используйте шаблон класса 

vector
стандартной библиотеки, определенный в
, и не используйте массивы. 
vector
выглядит и ведет себя, как массив, но имеет перед ним большое количество преимуществ в части безопасности и удобства. Пример 6.1 показывает несколько обычных операций с 
vector
.

Пример 6.1. Использование некоторых методов vector

#include 

#include 

#include 


using namespace std;


int main() {

 vector intVec;

 vector strVec;

 // Добавление элементов в "конец" вектора с помощью push_back

 intVec.push_back(3);

 intVec.push_back(9);

 intVec.push_back(6);

 string s = "Army";

 strVec.push_back(s);

 s = "Navy";

 strVec.push_back(s);

 s = "Air Force";

 strVec.push_back(s);

 // Для доступа к элементам используется operator[], как и для массивов

 for (vector::size_type i = 0; i < intVec.size(); ++i) {

  cout << "intVec[" << i << "] = " << intVec[i] << '\n';

 }

 // Или можно использовать итераторы

 for (vector::iterator p = strVec.begin();

  p != strVec.end(); ++p) {

  cout << *p << '\n';

 }

 // Если требуется безопасность, вместо operator[] используйте at(). Она

 // при использовании индекса > size() выбрасывает исключение out_of_range.

 try {

  intVec.at(300) = 2;

 } catch(out_of_range& e) {

  cerr << "out_of_range: " << e.what() << endl;

 }

}

Обсуждение

В целом, если требуется использовать массив, вместо него следует использовать 

vector
. 
vector
предлагает большую безопасность и гибкость, чем массив, а накладные расходы на производительность в большинстве случаев пренебрежимо малы, и если окажется, что они больше, чем можно себе позволить, производительность 
vector
можно увеличить, использовав некоторые его методы.

Если вы не знакомы с контейнерами, поставляющимися в составе стандартной библиотеки, или не сталкивались с использованием шаблонов классов (и их написанием), то объявление 

vector
в примере 6.1 требует некоторых пояснений. Объявление 
vector
имеет следующий вид.

vector

 typename Allocator = allocator > // используемый распределитель (allocator)

                     // памяти

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

Если вы хотите, чтобы 

vector
хранил элементы типа 
int
, объявите его, как в этом примере.

vector intVec;

А если вам требуется, чтобы он хранил строки, просто измените тип аргумента 

vector
.

vector strVec;

vector
может содержать любой тип С++, который поддерживает конструктор копирования и присвоение.

Следующее, что логически требуется сделать после создания экземпляра 

vector
, — это что-либо поместить в него. В конец вектора элементы добавляются с помощью 
push_back
.

intVec.push_back(3);

intVec.push_back(9);

intVec.push_back(6);

Это примерно эквивалентно добавлению элементов 0, 1 и 2 в массив. Это «примерно» эквивалентно потому, что, конечно, 

push_back
— это метод, который возвращает 
void
и помещает свой аргумент в конец вектора. 
operator[]
возвращает ссылку на область памяти, на которую указывает индекс массива, 
push_back
гарантирует, что во внутреннем буфере 
vector
окажется достаточно места для добавления аргумента. Если место есть, то он добавляется в следующий неиспользуемый индекс, а если нет, то буфер увеличивается с помощью зависящего от реализации алгоритма, а затем в него добавляется аргумент

Также с помощью метода 

insert
можно вставить элементы в середину вектора, хотя этого следует избегать из-за линейно возрастающей сложности этой операции. За более подробным обсуждением проблем производительности и их решения при использовании 
vector
обратитесь к рецепту 6.2. Чтобы вставить элемент, получите итератор на точку, куда требуется его вставить (обсуждение итераторов приводится в рецепте 7.1).

string s = "Marines";

vector::iterator p = find(strVec.begin()

strVec.end(), s);

if (s != strVec.end()) // Вставляет s непосредственно перед элементом,

 strVec.insert(p, s);  // на который указывает p

Перегруженные версии 

insert
позволяют вставлять в вектор n копий объекта, а также вставлять целый диапазон другой последовательности (эта последовательность может быть другим 
vector
, массивом, 
list
и т.п.).

Вместо вставки можно просто присвоить вектору уже существующую другую последовательность, стерев при этом то, что в нем содержалось до этого. Это выполняет метод 

assign
. Вектору можно присвоить диапазон значений или n копий одного и того же объекта, как здесь.

string sarr[3] = {"Ernie", "Bert", "Elmo"};

string s = "Oscar";

strVec.assign(&sarr[0], &sarr[3]); // Присвоить эту последовательность

strVec.assign(50, s);        // Присвоить 50 копий s

Если новая последовательность окажется больше, чем имеющийся размер буфера 

vector
, то 
assign
изменит размер буфера так, чтобы разместить в нем всю новую последовательность.

После того как данные помещены в 

vector
, имеется несколько способов получения их назад. Вероятно, наиболее интуитивным является 
operator[]
, который возвращает ссылку или 
const
-ссылку в зависимости от того, является ли вектор 
const
или нет, на элемент по указанному индексу. В этом отношении он ведет себя почти как массив:

for (int i = 0; i < intVec.size(); ++i) {

 std::cout << "intVec[" << i << "] = "

  << intVec[i] << '\n'; // rvalue

}

intVec[2] = 32; // lvalue

operator[]
также ведет себя как массив в том, что при использовании индекса, который больше, чем индекс последнего элемента 
vector
, результат не определен, что обычно означает, что будут повреждены данные программы или она обрушится. Избежать этого можно, запросив число элементов, содержащихся в 
vector
, с помощью 
size()
. Однако использованию 
operator[]
следует предпочитать итераторы, так как их использование является стандартным для перебора элементов любого стандартного контейнера.

for (vector::iterator p = strVec.begin();

 p != strVec.end(); ++p) {

 std::cout << *p << '\n';

}

Итераторы являются наиболее мощным подходом, так как они позволяют обращаться с контейнерами одинаковым образом. Например, при написании алгоритма, который работает с последовательностями элементов, расположенными между двумя итераторами, он сможет работать с любым стандартным контейнером. Это общий подход. При использовании произвольного доступа с помощью 

operator[]
вы ограничиваете себя использованием только тех контейнеров, которые поддерживают произвольный доступ. Первый подход позволяет алгоритмам стандартной библиотеки из
одинаково работать со стандартными контейнерами (и другими типами, ведущими себя, как они).

Также 

vector
предоставляет безопасность, которой просто невозможно достичь в случае обычных массивов. В отличие от массивов 
vector
с помощью метода 
at
предлагает проверку диапазонов. Если в 
at
передается неправильный индекс, он выбрасывает исключение 
out_of_range
, которое затем можно перехватить с помощью 
catch
и адекватно на него отреагировать. Например:

try {

 intVec.at(300) = 2;

} catch(std::out_of_range& e) {

 std::cerr << "out_of_range: " << e.what() << std::endl;

}

Как вы знаете, если обратиться к элементу за пределами массива с помощью 

operator[]
, оператор сделает то, что ему сказано сделать, и вернет то, что находится в указанной области памяти. Это плохо, так как либо программа обрушится в результате попытки доступа к области памяти, к которой она доступа не имеет, либо она молча изменит содержимое области памяти, принадлежащей другому объекту кучи, что обычно еще хуже. 
operator[]
для vector работает точно так же, но когда требуется обезопасить код, используйте 
at
.

Итак, вот краткий курс по 

vector
. Но что такое 
vector
? Если вы используете С++, то вас, вероятно, волнуют проблемы производительности, и вам не понравится, если вам просто дадут что-то и скажут, что это работает. Вполне справедливо. За обсуждением работы 
vector
и советами по его эффективному использованию обратитесь к рецепту 6.2.

Смотри также

Рецепт 6.2.

6.2. Эффективное использование vector

Проблема

Вы используете 

vector
, и при этом имеются жесткие требования по объему или времени выполнения кода и требуется снизить или устранить все накладные расходы.

Решение

Поймите, как реализован 

vector
, узнайте о сложности методов вставки и удаления и минимизируйте ненужные операции с памятью с помощью метода 
reserve
. Пример 6.2 показывает некоторые из этих методик в действии.

Пример 6.2. Эффективное использование vector

#include 

#include 

#include 


using std::vector;

using std::string;


void f(vector& vec) {

 // Передача vec по ссылке (или,

 // если требуется, через указатель)

 // ...

}


int main() {

 vector vec(500); // При создании vector говорим, что в него

              // планируется поместить определенное количество

              // объектов

 vector vec2;

 // Заполняем vec...

 f(vec);

 vec2 reserve(500); // Или постфактум говорим vector,

           // что требуется буфер достаточно большого

           // размера для хранения объектов

           // Заполняем vec2...

}

Обсуждение

Ключ к эффективному использованию 

vector
лежит в знании его работы. Когда у вас есть четкое представление реализации 
vector
, вопросы производительности становятся очевидными.

Как работает vector

vector
— это по сути управляемый массив. Более конкретно, 
vector
— это непрерывный фрагмент памяти (т.е. массив), который достаточно велик для хранения n объектов типа 
T
, где n больше или равно нулю и меньше или равно зависящему от реализации максимальному размеру. Обычно n увеличивается в процессе жизни контейнера при добавлении или удалении элементов, но оно никогда не уменьшается. Что отличает 
vector
от массива — это автоматическое управление памятью массива, методы для вставки и получения элементов и методы, которые предоставляют метаданные о контейнере, такие как размер (число элементов) и емкость (размер буфера), а также информацию о типе: 
vector::value_type
— это тип 
T
, 
vector::pointer
— это тип указатель-на-
T
и т.д. Два последних и некоторые другие являются частью любого стандартного контейнера, и они позволяют писать обобщенный код, который работает независимо от типа 
T
. Рисунок 6.1 показывает графическое представление того, что предоставляют некоторые из методов 
vector
, если 
vector
имеет размер 7 и емкость 10.

Рис. 6.1. Внутренности vector

Если вам любопытно, как поставщик вашей стандартной библиотеки реализовал 

vector
, скомпилируйте пример 6.1 и пройдите в отладчике все вызовы методов vector или откройте заголовочный файл
реализации стандартной библиотеки и изучите его. Код, который вы там увидите, по большей части не является дружественным к читателю, но он должен осветить некоторые моменты. Во-первых, если вы еще не видели кода библиотеки, он даст вам представление о методиках реализации, используемых для написания эффективного, переносимого обобщенного кода. Во-вторых, он даст точное представление о том, что представляют собой используемые вами контейнеры. При написании кода, который должен работать с различными реализациями стандартной библиотеки, это следует сделать в любом случае.

Однако независимо от поставщика библиотеки почти все реализации векторов похожи. В них есть переменная экземпляра, которая указывает на массив из 

T
, и элементы, добавляемые или присваиваемые вами, с помощью конструктора копирования или операции присвоения помешаются в элементы этого массива.

Обычно добавление объекта 

T
в следующий доступный слот буфера выполняется с помощью копирующего конструктора и new, которому передается тип создаваемого объекта, а также адрес, по которому он должен быть создан. Если вместо этого явно присвоить значение слоту, используя его индекс (с помощью 
operator[]
или 
at
), то будет использован оператор присвоения 
T
. Заметьте, что в обоих случаях объект клонируется либо с помощью конструктора копирования, либо 
T::operator=
. 
vector
не просто хранит адрес добавляемого объекта. Именно по этой причине любой тип, сохраняемый в векторе, должен поддерживать копирующий конструктор и присвоение. Эти свойства означают, что эквивалентный объект типа 
T
может быть создан с помощью вызова конструктора копирования 
T
или оператора присвоения. Это очень важно из-за семантики копирования 
vector
— если конструктор копирования или присвоение объектов не работает, то результаты, получаемые из vector, могут отличаться от того, что в него помещалось. А это плохо.

После добавления некоторого набора объектов в vector его буфер заполняется, и для добавления новых объектов его требуется увеличить. Алгоритм увеличения размера зависит от реализации, но обычно буфер размера n увеличивается до 2n+1. Важным здесь является то, как vector увеличивает свой буфер. Вы не можете просто сказать операционной системе неопределенно увеличить свой фрагмент памяти кучи. Требуется запросить новый фрагмент, который больше уже имеющегося. В результате процесс увеличения размера буфера выглядит следующим образом.

1. Выделить память для нового буфера.

2. Скопировать старые данные в новый буфер.

3. Удалить старый буфер.

Это позволяет 

vector
хранить все его объекты в одном непрерывном фрагменте памяти.

Оптимизация производительности vector

Предыдущий раздел должен дать вам представление о том, как объекты хранятся в векторе. Из этого обзора вам должны стать понятны главные моменты, связанные с производительностью, но в том случае, если вы еще не поняли, я расскажу о них.

Для начала, 

vector
(или любой другой контейнер из стандартной библиотеки) не хранит объекты. Он хранит копии объектов. Это значит, что каждый раз, когда в 
vector
заносится новый объект, он туда не «кладется». С помощью конструктора копирования или оператора присвоения он копируется в другое место. Аналогично при получении значения из 
vector
происходит копирование того, что находится в векторе по указанному индексу, в локальную переменную. Рассмотрим простое присвоение элемента 
vector
локальной переменной.

vector myVec;

// Поместить несколько объектов MyObj в myVec

MyObj obj = myVec[10]; // Скопировать объект с индексом 10

Это присвоение вызывает оператор присвоения 

obj
, в качестве правого операнда которого используется объект, возвращенный 
myVec[10]
. Накладные расходы на производительность при работе с большим количеством объектов резко возрастают, так что их лучше всего избегать.

Для снижения накладных расходов на копирование вместо помещения в 

vector
самих объектов поместите в него указатели. Сохранение указателей потребует меньшего количества циклов ЦП на добавление и получение данных, так как указатели проще скопировать, чем объекты, и, кроме того, это снизит объем памяти, необходимый для буфера 
vector
. Но помните, что при добавлении в контейнер стандартной библиотеки указателей контейнер не удаляет их при своем уничтожении. Контейнеры удаляют только содержащиеся в них объекты, т.е. переменные, которые хранят адреса объектов, но контейнер ничего не знает, хранится ли в нем указатель или объект. Все, что он знает, — это то, что это объект типа 
T
.

Изменение размера буфера тоже не дешево. Копирование каждого элемента буфера требует много работы, и этого лучше всего избегать. Чтобы защититься от этого, явно укажите размер буфера. Имеется пара способов сделать это. Простейшим способом сделать это является указание размера при создании вектора.

vector vec(1000);

Здесь резервируется место для 1000 строк, и при этом производится инициализация каждого слота буфера с помощью конструктора 

string
по умолчанию. При этом подходе приходится платить за создание каждой из этих строк, но добавляются определенные меры безопасности в виде инициализации каждого элемента буфера пустой строкой. Это означает, что при ссылке на элемент, значение которого еще не было присвоено, будет просто получена пустая строка.

Если требуется проинициализировать буфер каким-то определенным значением, можно передать объект, который требуется скопировать в каждый слот буфера.

string defString = "uninitialized";

vector vec(100, defString);

string s = vec[50]; // s = "uninitialized"

В этом варианте 

vec
с помощью конструктора копирования создаст 100 элементов, содержащих значение из 
defString
.

Другим способом резервирования пространства буфера является вызов метода 

reserve
, расположенный после создания 
vector
.

vector vec;

vec reserve(1000);

Главным различием между вызовом 

reserve
и указанием размера в конструкторе является то, что 
reserve
не инициализирует слоты буфера каким-либо значением. В частности, это означает, что не следует ссылаться на индексы, в которые еще ничего не записано.

vector vec(100);

string s = vec[50]; // без проблем: s содержит пустую строку

vector vec2;

vec2.reserve(100);

s = vec2[50];    // Не определено

Использование резервирования или указание числа объектов по умолчанию в конструкторе помогает избежать ненужных перераспределений буфера, Это приводит к увеличению производительности, но также позволяет избежать и еще одной проблемы: каждый раз, когда происходит перераспределение буфера, все итераторы, имевшиеся на этот момент и указывающие на элементы, становятся недействительными.

Наконец, плохой идеей является вставка элементов в любое место, кроме конца вектора. Посмотрите на рис. 6.1. Так как 

vector
— это просто массив с дополнительными прибамбасами, становится очевидно, почему следует добавлять элементы только в конец вектора. Объекты в 
vector
хранятся последовательно, так что при вставке элемента в любое место, кроме конца, скажем, по индексу n, объекты с n+1 до конца должны быть сдвинуты на один (в сторону конца) и освободить место для нового элемента. Сложность этой операции линейна, что означает, что она оказывается дорогостоящей даже для векторов скромного размера. Удаление элемента вектора имеет такой же эффект: оно означает, что все индексы больше n должны быть сдвинуты на один слот вверх. Если требуется возможность вставки и удаления в произвольном месте контейнера, вместо вектора следует использовать 
list
.

6.3. Копирование вектора

Проблема

Требуется скопировать содержимое одного 

vector
в другой.

Решение

Имеется пара способов сделать это. Можно при создании 

vector
использовать конструктор копирования, а можно использовать метод 
assign
. Пример 6.3 показывает оба этих способа.

Пример 6.3. Копирование содержимого vector

#include 

#include 

#include 

#include 


using namespace std;


// Вспомогательная функция для печати содержимого вектора

template

void vecPrint (const vector& vec) {

 cout << "{";

 for (typename vector::const_iterator p = vec.begin();

  p != vec.end(); ++p) {

  cout << "{" << *p << "} ";

 }

 cout << "}" << endl;

}


int main() {

 vector vec(5);

 string foo[] = {"My", "way", "or", "the", "highway"};

 vec[0] = "Today";

 vec[1] = "is";

 vec[2] = "a";

 vec[3] = "new";

 vec[4] = "day";

 vector vec2(vec);

 vecPrint(vec2);

 vec.at(0) = "Tomorrow";

 vec2.assign(vec.begin(), vec.end()); // Копирование каждого элемента

 vecPrint(vec2);            // с помощью присвоения

 vec2.assign(&foo[0], &foo[5]); // Присвоение работает для всего, что

 vecPrint(vec2);         // ведет себя как итератор

 vector::iterator p;

 p = find(vec.begin(), vec.end(), "new");

 vec2.assign(vec.begin(), p); // Копирование подмножества полного диапазона

 vecPrint(vec2);       // vec

}

Обсуждение

Копирование 

vector
просто. Имеется два способа сделать это. Можно скопировать один 
vector
в другой с помощью конструктора копирования, как и любой другой объект, а можно использовать метод 
assign
. О конструкторе копирования сказать почти нечего. Просто передайте в него 
vector
, который требуется скопировать, и все.

vector vec2(vec);

В этом случае 

vec2
будет содержать такое же число элементов, что и 
vec
, и каждый из этих элементов будет копией элемента 
vec
с таким же индексом. Каждый элемент копируется с помощью конструктора копирования 
string
. Так как здесь используется конструктор, буфер 
vec2
имеет размер, достаточный для хранения всего, что есть в 
vec
.

assign
работает аналогично, за исключением того, что за кулисами выполняется дополнительная работа, связанная с тем, что теперь дело касается целевого vector который уже может содержать данные. Во-первых, требуется удалить элементы, которые оказались, так сказать, под ногами. Вначале 
assign
для каждого из объектов, уже содержащихся в 
vec2
, вызывает деструктор. После этого он проверяет размер буфера 
vec2
, чтобы убедиться, что он достаточно большой, чтобы вместить то, что находится в 
vec
. Если он не достаточен, 
assign
изменяет размер буфера под размещение новых данных. Наконец, он копирует каждый элемент.

Кроме того, 

assign
можно использовать для копирования подмножества последовательности. Например, если требуется скопировать подмножество элементов 
vec
, просто укажите при вызове 
assign
необходимый диапазон.

vector::iterator p;

p = std::find(vec.begin(), vec.end(), "new");

vec2.assign(vec.begin(), p);

vecPrint(vec2);

В этом случае 

assign
скопирует все до, но не включая, 
p
. Причиной этого является соглашение, по которому во всех контейнерах и алгоритмах стандартной библиотеки 
assign(first, last)
копирует элементы, на которые указывает 
first
, до, но не включая, элемент, на который указывает 
last
. Такой диапазон, который включает первый элемент, но не включает последний, часто обозначается как (first, last).

Используйте 

assign
или конструктор копирования вместо самостоятельного циклического перебора. Это значит, не копируйте каждый элемент, перебирая 
vec
и помещая элементы в конец 
vec2
в цикле. Это потребует от вас большой избыточности кода и отключит все оптимизации, которые могут присутствовать в реализации 
assign
и конструктора копирования стандартной библиотеки.

6.4. Хранение указателей в векторе

Проблема

С целью повышения эффективности или по другим причинам невозможно хранить копии объектов в 

vector
, но их требуется как-то разместить.

Решение

Сохраните в 

vector
указатели на объекты, а не копии самих объектов. Но при этом не забудьте удалить объекты с помощью 
delete
, так как 
vector
этого за вас не сделает. Пример 6.4 показывает, как объявить 
vector
указателей и работать с ним.

Пример 6.4. Использование векторов указателей

#include 

#include 


using namespace std;


static const int NUM_OBJECTS = 10;


class MyClass { /*...*/ };


int main() {

 vector vec;

 MyClass* p = NULL;

 // Загрузить в vector объекты MyClass

 for (int i = 0; i < NUM_OBJECTS; i++) {

  p = new MyClass();

  vec.push_back(p);

 }

 // Выполнить обработку данных, затем удалить объекты, когда

 // они уже не нужны

 for (vector::iterator pObj = vec.begin();

  pObj != vec.end(); ++pObj) {

  delete *pObj; // заметьте, что здесь удаляется то на что указывает pObj,

        // который является указателем

 }

 vec.clear(); // Очистить содержимое, чтобы больше никто не попытался

        // удалить его еще раз

}

Обсуждение

Сохранить указатели в 

vector
можно точно так же, как и все остальное. Объявите vector указателей таким образом:

vector vec;

Здесь важно запомнить, что 

vector
хранит значения, не обращая внимания на то, что они означают. Следовательно, он не знает, что для указателей перед их удалением следует использовать 
delete
. Если выделить память, затем поместить указатели в память 
vector
, то по окончании работы следует самостоятельно удалить память. Не дайте ввести себя в заблуждение термину «контейнер», думая, что если в 
vector
сохранить указатель, то это подразумевает владение им.

После удаления указателей следует явно очистить 

vector
— по той же причине, по которой следует присваивать переменным-указателям по окончании работы с ними значение NULL. Это предотвратит ошибочное повторное удаление.

6.5. Хранение объектов в списке

Проблема

Требуется хранить элементы в виде последовательности, но vector не соответствует всем требованиям. В частности, требуется иметь возможность эффективно добавлять и удалять элементы в середине последовательности, а не только в ее конце.

Решение

Для хранения данных используйте 

list
, объявленный в
. 
list
предлагает более высокую производительность и большую гибкость при изменении последовательности в произвольных местах. Пример 6.5 показывает, как использовать 
list
, а также демонстрирует некоторые из его уникальных операций.

Пример 6.5. Использование list

#include 

#include 

#include 

#include 


using namespace std;


// Простая функция для печати

template

struct printer {

 void operator()(const T& s) {

  cout << s << '\n';

 }

};


bool inline even(int n) {

 return(n % 2 == 0);

}


printer strPrinter;

printer intPrinter;


int main() {

 list lstOne;

 list lstTwo;

 lstOne.push_back("Red");

 lstOne.push_back("Green");

 lstOne.push_back("Blue");

 lstTwo.push_front("Orange");

 lstTwo.push_front("Yellow");

 lstTwo.push_front("Fuschia");

 for_each(lstOne.begin(), // Напечатать каждый элемент списка,

  lstOne.end(),      // используя пользовательскую функцию печати

  strPrinter);

 lstOne.sort(); // list содержит методы для сортировки

 lstTwo.sort();

 lstOne.merge(lstTwo);  // Объединить два списка и напечатать

 for_each(lstOne.begin(), // результаты (перед объединением списки должны

  lstOne.end(),       // быть отсортированы)

  strPrinter);

 list intLst;

 intLst.push_back(0);

 intLst.push_back(1);

 intLst.push_back(2);

 intLst.push_back(3);

 intLst.push_back(4);

 // Удалить все значения больше 2

 intLst.remove_if(bind2nd(greater(), 2));

 for_each(intLst.begin(), intLst.end(), intPrinter);

 // Или удалить все четные значения

 intLst.remove_if(even);

}

Обсуждение

list
— это последовательность, обеспечивающая постоянную сложность операций вставки и удаления элементов в произвольную позицию, но обладающая линейной сложностью их поиска. Обычно 
list
реализуется как двухсвязный список, что означает, что каждый элемент хранится в узле, содержащем указатели на предыдущий и следующий элементы последовательности. Он обеспечивает все требования к контейнеру стандартной последовательности, полюс предоставляет несколько уникальных методов.

Объявление 

list
не вызывает сложностей — просто укажите тип элементов, которые в нем будут храниться, и, опционально, класс распределителя памяти.

list

 typename Allocator = allocator > // Используемый распределитель

                     // памяти

Параметр шаблона 

Value
— это тип элементов, которые будут храниться в 
list
. Это должен быть тип, который поддерживает конструктор копирования и присвоение. 
Allocator
— это используемый класс распределителя памяти. По умолчанию используется стандартный распределитель (и в большинстве случаев его вполне достаточно).

Далее приведено типичное объявление 

list
(см. пример 6.5).

list lstOne;

После объявления списка поместите в него что-нибудь с помощью 

push_front
или 
push_back
, как здесь.

lstOne.push_back("Red"); // Добавление элементов в конец списка

lstOne.push_back("Green");

lstOne.push_back("Blue");


lstTwo.push_front("Orange"); // Добавление элементов в начало

lstTwo.push_front("Yellow");

lstTwo.push_front("Fuschia");

Помещение элементов в 

list
занимает постоянное время, а не амортизированное постоянное время, как в случае с 
vector
. Реализации 
list
не требуется периодически изменять размер буфера, так что в них не будет возникать периодических падений производительности, как при использовании 
vector
. 
list
просто должен обновить набор указателей, и больше ничего.

Для удаления элементов из начала или конца 

list
используйте 
pop_front
или 
pop_back
(без аргументов). Несмотря на их имя, методы «pop» не возвращают извлекаемый элемент, как это можно ожидать, исходя из обычной семантики стеков.

Обычно 

list
выглядит так, как показано на рис. 6.2. Каждый узел содержит (по меньшей мере) три части: объект, в нем содержащийся, указатель на предыдущий узел и указатель на следующий узел. В оставшейся части рецепта я буду ссылаться на указатели на следующий и предыдущий узлы как 
next_
и 
prev_
.

Рис. 6.2. Список с двунаправленными связями

Когда вы увидите, как реализован 

list
, станет очевидно, почему некоторые операции имеют сложность, отличную от их сложности для 
vector
. Добавление элемента в любое место 
list
требует только изменения указателей 
next_
и 
prev_
предыдущего и следующего элементов. Приятным моментом в 
list
является то, что при вставке и удалении элементов в помощью 
insert
и 
erase
устаревают значения только тех итераторов, которые указывают на затрагиваемый(е) объект(ы). Итераторы для других элементов не теряют актуальности.

Методы вставки и удаления — это 

insert
и 
erase
, 
insert
в качестве первого аргумента принимает итератор, а в качестве второго — либо объект типа 
T
, либо количество и затем объект типа 
T
, либо начальный и конечный итераторы. Первый аргумент-итератор указывает на элемент, непосредственно перед которым должна произойти вставка. Перегрузки 
insert
используются вот так.

list strlst;

list::iterator p;

// ...

string s = "Scion";

p = find(strLst.begin(), strLst.end(), // std::find из 

 "Toyota");

strLst.insert(p, s);   // Вставить s сразу перед p

strLst.insert(p, 16, s); // Вставить 16 копий s непосредственно перед p

strLst insert(p, myOtherStrLst.begin(), // Вставить все, что содержится

 myOtherStrLst.end());          // в myOtherStrLst, перед p

Удаление элементов аналогично.

p = find(strLst.begin(), strLst.end(), // std::find из  

 "Toyota");

strLst1.erase(p); // Удаляем этот элемент

strLst2.erase(p, strLst.end()); // Удаляем от p до конца

strLst3.clear(); // Удаляем все элементы

В дополнение к методам стандартных контейнеров 

list
предоставляет несколько своих. Первый — это 
splice
.

splice
делает то, что означает его имя: он объединяет два 
list
в один. Вот как можно объединить 
lstTwo
с 
lstOne
из примера 6.5.

list::iterator p = // Находим, куда вставить второй

 std::find(lstOne.begin(), // список

  lstOne.end(), "Green");

lstOne.splice(p, lstTwo); // Вставляем lstTwo непосредственно перед "Green"

p
— это итератор, который указывает на элемент в 
lstOne
. 
lstTwo
вставляется в 
lstTwo
непосредственно перед 
p
. Как и в случае со вставкой, все, что здесь требуется сделать, — это изменить указатели 
next_
и 
prev_
соответствующих узлов, так что эта операция занимает постоянное время. После объединения 
lstTwo
с 
lstOne
первый очищается, и именно поэтому этот параметр не объявлен как 
const
. Также можно вставить в 
lstOne
один элемент или диапазон элементов из 
lstTwo
. В обоих случаях элементы, объединяемые с другим списком, удаляются из первоначального.

Если списки отсортированы (

list
содержит свой собственный метод 
sort
, 
std::sort
с 
list
не работает) и требуется объединить их в один, сохранив их порядок, то вместо 
splice
используйте 
merge
. 
merge
объединяет два списка в один, и если два элемента оказываются одинаковыми, то в конечную версию попадает элемент из 
lstOne
. Как и в случае со 
splice
, список, переданный в качестве аргумента, по окончании объединения очищается.

Также 

list
содержит несколько удобных операций для удаления элементов. Представьте, что вам требуется удалить все вхождения какого-либо элемента. Все, что для этого требуется сделать, это вызвать 
remove
, передав такой аргумент, который при сравнении с элементами 
list
будет давать 
(*p == item) != false
, где 
p
— это итератор 
list
. 
remove
вызывается вот так.

strLst.remove("Harry");

В результате из 

strLst
будут удалены все элементы, у которых 
el == "Harry"
. Если требуется удалить элементы, которые удовлетворяют какому-либо предикату, такому как больше какого-либо значения, используйте 
remove_if
.

bool inline even(int n) {

 return(n % 2 == 0);

}


list intLst;


// Fill up intLst...

intLst.remove_if(even); // Удаляет все элементы, для которых even(*p)

             // != false

Если предикаты более сложные, то попробуйте использовать какие-то из функторов из

. Например, если требуется удалить элементы, которые больше определенного значения, используйте в 
remove_if
объединение из 
greater
(из
) и 
bind2nd
.

intLst.remove_if(std::bind2nd(std::greater(), 2));

В результате этого из 

intLst
будут удалены все значения, которые больше 2. Эта запись несколько необычна, но ничего сложного в ней нет. 
bind2nd
принимает два аргумента — объект функции (назовем ее 
f
) и значение (
v
) — и возвращает объект функции, который принимает один аргумент (
arg
) и вызывает 
f(arg, v)
. 
bind2nd
— это простой способ делать подобные вещи без необходимости писать набор небольших функций.

list
— это хорошая альтернатива вектору, когда требуется стандартный последовательный контейнер. Другое внутреннее представление 
list
позволяет ему обеспечить другой уровень сложности многих стандартных операций с последовательностями и несколько дополнительных операций.

Смотри также

Рецепт 6.1.

6.6. Отображение строк на другие объекты

Проблема

Имеются объекты, которые требуется сохранить в памяти, и вы хотите хранить их по ключам типа 

string
. Требуется иметь возможность быстро добавлять, удалять и получать элементы (с, как максимум, логарифмической сложностью).

Решение

Для отображения ключей (

string
) на значения (любой тип, который подчиняется семантике значений) используйте стандартный контейнер 
map
, объявленный в
. Пример 6.6 показывает, как это делается.

Пример 6.6. Создание отображения строк

#include 

#include 

#include 


using namespace std;


int main() {

 map strMap;

 strMap["Monday"] = "Montag";

 strMap["Tuesday"] = "Dienstag";

 strMap["Wednesday"] = "Mittwoch";

 strMap["Thursday"] = "Donnerstag";

 strMap["Friday"] = "Freitag";

 strMap["Saturday"] = "Samstag";

 // strMap.insert(make_pair("Sunday", "Sonntag"));

 strMap.insert(pair("Sunday", "Sonntag"));

 for(map::iterator p = strMap.begin();

  p != strMap.end(); ++p) {

  cout << "English: " << p->first

  << German: " << p->second << endl;

 }

 cout << endl;

 strMap.erase(strMap.find("Tuesday"));

 for (map::iterator p = strMap.begin();

  p ! = strMap.end(); ++p) {

  cout << "English: " << p->first

  << ", German: " << p->second << endl;

 }

}

Обсуждение

map
— это ассоциативный контейнер, который отображает ключи на значения, предоставляет логарифмическую сложность вставки и поиска и постоянную сложность удаления одного элемента. Обычно разработчики используют отображение для хранения объектов по их ключам типа 
string
. Именно это делает пример 6.6. В этом случае отображаемый тип является строкой, но он может быть почти чем угодно.

Отображение объявляется вот так.

map

 typename Value,  // Тип значения

 typename LessThanFun = std::less, // Функция/функтор,

                     // используемые для сортировки

 typename Alloc = std::allocator > // Распределитель памяти

Key
и 
Value
— это типы ключа и связанного значения, которые хранятся в отображении. 
LessThanFun
— это функция или функтор, который принимает два аргумента и возвращает истину, если первый меньше, чем второй. По умолчанию используется стандартный функтор 
less
. 
Alloc
— это распределитель памяти, и по умолчанию используется стандартный.

Использование 

map
довольно просто. Объявите тип ключа и значения вот так.

map strMan;

В результате будет создан 

map
, в котором и ключ, и значение имеют тип 
string
. С помощью 
operator[]
поместите в отображение объекты, что интуитивно и легко читаемо.

strMap["Monday"] = Montag";

strMap["Tuesday"] = "Dienstag";

strMap["Wednesday"] = "Mittwoch"; // ...

В результате в 

map
будут вставлены элементы с индексом (например, 
"Monday"
) в качестве ключа и правым операндом в качестве значения. Они хранятся в порядке, определяемом параметром шаблона 
LessThanFun
, и если он не указан, то 
map
использует 
std::less
.

Чтобы получить значения из 

map
, используйте 
operator[]
в правой части присвоения, как здесь.

wedInGerman = strMap["Wednesday"];

В манере всех стандартных контейнеров значение, связанное с ключом 

"Wednesday"
, с помощью 
operator=
копируется в объект 
wedInGerman
.

operator[]
— это удобный способ вставки или обновления элементов или получения значений из map, но он имеет побочный эффект, который может оказаться неожиданным. Строго говоря, 
operator[k]
возвращает ссылку на значение, ассоциированное с 
k
— независимо от того, существует ли 
k
в 
map
или нет. Если 
k
уже находится в 
map
, то возвращается ассоциированное с ним значение. Если нет, то 
k
вставляется, а затем используется конструктор по умолчанию, который создает объект значения для этого ключа. Чтобы сделать это более понятным, рассмотрим, что делает следующий код.

map mapZipCodes;    // Сейчас здесь ноль элементов

string myZip = mapZipCodes["Tempe"]; // В map пока что нет элементов,

                   // но чему теперь равно count()?

Что находится в 

myZip
и сколько теперь элементов в 
mapZipCodes
? Так как 
operator[]
вставляет указанный ключ, если он не существует, 
myZip
содержит пустую строку, а в 
mapZipCodes
содержится один элемент. Это может оказаться нежелательно, но независимо от вашего желания помните, что 
operator[]
не является 
const
-методом: всегда есть вероятность того, что он изменит состояние 
map
, добавив узел.

Метод 

insert
предоставляет альтернативный метод добавления пар в отображение, 
insert
выполняет строгую вставку, а не вставку/обновление, как 
operator[]
. При использовании map (но не 
multimap
, который может содержать дублирующиеся ключи) 
insert
, если ключ уже существует, не делает ничего. По сравнению с ним 
operator[]
, если ключ уже существует, заменяет значение объекта для этого ключа на новое.

Но синтаксис вставки требует несколько большей работы, чем 

operator[]
, и он связан с тем, как 
map
хранит данные. Рассмотрим строку из примера 6.6.

strMap.insert(std::make_pair("Sunday", "Sonntag"));

ma

p
хранит пары ключ/значение в объекте 
pair
, 
pair
— это простой вспомогательный шаблон класса (объявленный в
и включенный в
), который хранит два значения двух типов. Чтобы объявить 
pair
из двух 
string
, сделайте так.

pair myPair;

Первый и второй элементы в 

pair
доступны по открытым членам 
first
и 
second
. При использовании для доступа к элементам 
map
оператора 
operator[]
обычно работать с 
pair
не приходится, но в случае со многими другими методами это придется делать, так что следует знать, как создавать и использовать объекты 
pair
. Например, итераторы разыменовываются в простые объекты 
pair
, так что при их использовании, как это делается в примере 6.6, следует знать, как получить ключ и его значение.

for (map iterator p = strMap.begin();

 p != strMap.end(); ++p)

 cout << "English: " << p->first

  << ", German: " << p->second << endl;

Ключ хранится в 

first
, а значение хранится в 
second
.

Однако это не объясняет, почему я использовал 

make_pair
. 
make_pair
— это вспомогательный шаблон функции, который создает объект 
pair
на основе двух переданных в него аргументов. Некоторые предпочитают этот подход вызову конструктора 
pair
, так как шаблон класса не может догадаться о типах своих аргументов, в то время как шаблон функции может. Таким образом, эти две строки кода функционально эквивалентны.

strMap.insert(std::make_pair("Sunday", "Sonntag"));

strMap.insert(std::pair("Sunday", "Sonntag"));

map
не допускает наличия дублирующихся ключей. Если требуется разрешить дублирование ключей, следует использовать 
multimap
, который является 
map
, разрешающим наличие несколько одинаковых ключей. Его интерфейс идентичен 
map
, но поведение методов в необходимых случаях отличается. В табл. 6.1 приведен перечень методов, которые есть в одном, но отсутствуют в другом, и пояснения различий в поведении общих методов, map и 
multimap
содержат несколько 
typedef
, которые описывают различные значения, хранящиеся в них. В табл. 6.1 они используются следующим образом:

key_type

Это тип ключа. В 

string map,
объявленном как 
map
, 
key_type
должен быть 
string
.

mapped_type

Это тип значения, на которое отображается ключ. В 

string map
, объявленном как 
map
, 
mapped_type
должен быть 
MyClass*
.

value_type

Это тип объекта, содержащего ключ и значение, которой, применительно к 

map
и 
multimap
, является 
pair
.


Табл. 6.1. map и multimap

Метод map, multimap или оба Поведение 
T& operator[] (const key_type& k)
 
map
 Возвращает ссылку на объект значения, сохраненный с ключом 
k
. Если 
k
в map отсутствует, то он добавляется, а объект значения создается с помощью конструктора по умолчанию		 
iterator insert(const value_type& v) pair insert(const value_type& v)
 Оба Первая версия вставляет 
v
в 
multimap
и возвращает итератор, который указывает на вставленную пару 
pair
. Вторая версия вставляет 
v
и 
map
при условии, что в 
map
еще не содержится ключа, равного 
v
. Возвращаемая 
pair
содержит итератор который указывает на вставленную 
pair
, если произошла вставка, и 
bool
, указывающий, была ли вставка успешной		 
iterator find(const key_type& k)
 Оба Возвращает итератор или 
const_iterator
, который указывает на
 mapped_type
, соответствующий 
k
. В 
multimap
не гарантируется, что возвращаемый итератор будет указывать на первое значение, соответствующее 
k
. Если ключа, равного k, нет, то возвращаемый итератор равен 
end()

Также табл 6.1 показывает разницу в поведении между 

map
и 
multimap
.

Если 

operator[]
вам не подходит, т.е. другой способ найти ключ в 
map
. Для этого можно использовать метод 
find
.

map::const_iterator p

 = strMap.find("Thursday");


if (p != strMap.end())

 cout << "Thursday = " << p->second << endl;

Но не забудьте, что при использовании 

multimap
не гарантируется, что возвращаемый элемент будет первым элементом с ключом, равным искомому. Если нужен первый элемент, чей ключ не меньше определенного значения или не больше определенного значения, используйте 
lower_bound
или 
upper_bound
. 
lower_bound
возвращает итератор, указывающий на первую пару ключ/значение, равную или большую, чем аргумент 
key_type
. Другими словами, если ваш 
map
содержит дни недели, как в примере 6.6, следующий код вернет итератор, который указывает на пару, содержащую 
"Friday"
и 
"Freitag"
.

p = strMap.lower_bound("Foo");

if (p != strMap.end())

 cout << p->first << " = " << p->second << endl;

Это происходит благодаря тому, что первый ключ больше или равен 

"Foo"
. 
upper_bound
работает аналогично, но с противоположным условием.

В начале этого обсуждения я упоминал, что элементы в map хранятся в отсортированном по ключам порядке, так что при переборе от 

begin
до 
end
каждый элемент будет «больше», чем предшествующий (а в 
multimap
— больше или равен ему) Но при использовании более сложных ключей, чем 
string
или числа, может потребоваться указать, как при вставке элементов в отображение следует сравнивать ключи.

По умолчанию ключи хранятся с помощью стандартного функтора 

less
(объявленного в
). 
less
— это двоичная функция (принимает два аргумента одинакового типа), которая возвращает 
bool
, указывающий на то, больше ли первый аргумент, чем второй, или нет. Другими словами, 
less(a, b)
возвращает 
a < b
. Если это не то, что вам требуется, создайте свой собственный функтор и объявите 
map
с его помощью. Например, если в качестве ключа используется объект 
Person
и каждый 
Person
имеет имя и фамилию, то может потребоваться сравнивать фамилии и имена. Пример 6.7 показывает способ сделать это.

Пример 6.7. Использование собственного функтора сортировки

#include 

#include 

#include 


using namespace std;


class Person {

 friend class PersonLessThan;

public:

 Person(const string& first, const string& last) :

  lastName_(last), firstName_(first) {}

 // ...

 string getFirstName() const {return(firstName_);}

 string getLastName() const {return(lastName_);}

private:

 string lastName_;

 string firstName_;

};


class PersonLessThan {

public:

 bool operator()(const Person& per1,

  const Person& per2) const {

  if (per1.lastName_ < per2. lastName_)    // Сравнить фамилии,

  return(true);                // а затем

  else if (per1.lastName_ == per2.lastName_) // имена

  return(per1.firstName_ < per2.firstName_);

  else

  return(false);

 }

};


int main() {

 map personMap;

 Person per1("Billy", "Silly"),

  per2("Johnny", "Goofball"),

 per3("Frank", "Stank"),

  реr4("Albert", "Goofball");

 personMap[per1] = "cool";

 personMap[per2] = "not cool";

 personMap[per3] = "not cool";

 personMap[per4] = "cool";

 for (map::const_iterator p =

  personMap.begin(); p != personMap.end(); ++p) {

  cout << p->first.getFirstName() << " " << p->first.getLastName()

  << " is " << p->second << endl;

 }

}

map
— это прекрасный способ хранить пары ключ/значение. После того как вы поймете поведение его частей, таких как 
operator[]
и хранение данных (в виде объектов 
pair
), 
map
предоставит простоту в использовании и высокую производительность.

Смотри также

Рецепт 6.7.

6.7. Использование хеш-контейнеров

Проблема

Требуется сохранить ключи и значения, обеспечив постоянное время доступа к элементам, и не требуется хранения элементов в упорядоченном виде.

Решение

Используйте один из связанных с хешами контейнеров — 

hash_map
или 
hash_set
. Однако помните, что они не входят в число стандартных контейнеров, определяемых стандартом С++, а представляют собой расширения, включаемые большинством реализаций стандартной библиотеки. Пример 6.8 показывает, как использовать 
hash_set
.

Пример 6.8. Хранение строк в hash_set

#include 

#include 

#include 


int main() {

 hash_set hsString;

 string s = "bravo";

 hsString.insert(s);

 s = "alpha";

 hsString.insert(s);

 s = "charlie";

 hsString.insert(s);

 for (hash set::const_iterator p = hsString.begin();

  p != hsString.end(); ++p)

  cout << *p << endl; // заметьте, что здесь не гарантируется хранение

            // в упорядоченном виде

}

Обсуждение

Контейнеры, основанные на хешах, — это популярные во всех языках структуры данных, и прискорбно, что стандарт C++ не требует их реализации. Однако если требуется использовать хеш-контейнер, то не все потеряно: высока вероятность, что используемая вами реализация стандартной библиотеки содержит 

hash_map
и 
hash_set
, но тот факт, что они не стандартизованы, означает, что их интерфейсы могут отличаться от одной реализации стандартной библиотеки к другой. Я опишу хеш-контейнеры, которые поставляются в составе реализации стандартной библиотеки STLPort.

STLPort — это свободно распространяемая переносимая реализация стандартной библиотеки, существующая уже довольно длительное время и предоставляющая хеш-контейнеры. При использовании другой библиотеки интерфейс может быть другим, но общая идея будет той же самой.

Главной особенностью хеш-контейнеров (называемых во многих книгах по ассоциативными хеш-контейнерами) является то, что они в общем случае предоставляют постоянное время поиска, вставки и удаления элементов, а в худшем случае эти операции имеют линейное время. Ценой постоянного времени выполнения этих операций является то, что в хеш-контейнере они хранятся в неупорядоченном виде, как в 

map
.

Посмотрите на пример 6.8. Использование хеш-контейнера (в данном случае 

hash_set
) довольно просто — объявите его как большинство других контейнеров и начните вставлять в него элементы.

hash_set hsString; // hash_set строк

string s = "bravo";

hsString.insert(s); // Вставка копии s

Использование 

hash_map
аналогично, за исключением того, что требуется, как минимум, указать типы данных используемых ключей и значений. Это аналогично 
map
.

hash_map

hmStrings; // Отображение строк на строки

string key = "key";

string val = "val";

hmStrings[key] = val;

Это только основы использования хеш-контейнеров. Также имеется набор параметров шаблона, которые позволяют указать используемую хеш-функцию, функцию, проверяющую ключи на эквивалентность, и объект, используемый для распределения памяти. Я опишу их немного позже.

В большинстве библиотек есть четыре хеш-контейнера, и они похожи на другие ассоциативные контейнеры стандартной библиотеки (т.е. 

map
и 
set
). Это 
hash_map
, 
hash_multimap
, 
hash_set
и 
hash_multiset
. хеш-контейнеры реализуются с помощью хеш- таблицы. Хеш-таблица — это структура данных, которая обеспечивает постоянное время доступа к элементам, используя для этого хеш-функцию перехода к месту, близкому к хранению искомого объекта, а не проход по древовидной структуре. Разница между 
hash_map
и 
hash_set
состоит в том, как данные хранятся в хеш-таблице.

Объявления контейнеров, использующих хеш-таблицу, в STLPort выглядят так.

hash_map

 Value,          // Тип значения,

              // связанного с ключом

 HashFun = hash,   // Используемая хеш-функция

 EqualKey = equal_to // Функция, используемая для

              // проверки равенства ключей

 Alloc = alloc>;      // Используемый распределитель памяти


hash_set

 HashFun = hash,    // Используемая хеш-функция

 EqualKey = equal_to, // Функция, используемая для

              // проверки равенства ключей

 Alloc = alloc>;      // Используемый распределитель памяти

hash_map
— это хеш-таблица, которая хранит значения как объекты 
pair
. Это означает, что когда я буду далее описывать хеш-таблицы, «элементы» в таблице будут означать пары ключ/значение. 
hash_map
не хранит ключи значение по отдельности (как и map). 
hash_set
просто хранит ключ как значение.

Параметр шаблона 

HashFun
— это функция, которая превращает объекты типа 
Key
в значения, которые могут быть сохранены как 
size_t
. Более подробно это описывается ниже. Параметр шаблона 
EqualKey
— это функция, которая принимает два аргумента и, если они эквивалентны, возвращает 
true
. В контейнерах 
hash_map
и 
hash_set
два ключа не могут быть равны, 
hash_multimap
и 
hash_multiset
могут содержать по нескольку одинаковых ключей. Как и в случае с другими контейнерами, 
Alloc
— это используемый распределитель памяти.

Хеш-таблица содержит две части. В ней есть относительно большой вектор, где каждый индекс это «участок». Каждый из участков является на самом деле указателем на первый узел в относительно коротком одно- или двухсвязном списке (в STLPort — односвязном). Именно в этих списках и хранятся данные. Чтобы получить число участков в хеш-контейнере, используйте метод 

bucket_count
. Рисунок 6.3 дает представление о том, как выглядит в памяти хеш-отображение.

Рис. 6.3. Хеш-таблица

Рассмотрим использование 

hash_set
из примера 6.8. При вставке элемента контейнер вначале должен определить, к какому участку он относится. Это делается с помощью вызова хеш-функции контейнера, передачи в нее ключа (хеш-функция обсуждается немного позже) и вычисления остатка от деления значения на число участков. В результате получается индекс в векторе участков.

Если вы незнакомы с тем, что такое «хеширование», то это очень простая концепция. Если есть какое-то значение (скажем, массив типа 

char
), то хеш-функция для него — это функция, которая принимает один аргумент и возвращает значение хеша типа 
size_t
(т.е. число). В идеале требуется хеш-функция, которая генерирует уникальные значения хешей, но она не обязана это делать. Эта функция в математическом смысле неоднозначна: несколько строк типа string могут иметь одно и то же значение хеша. Далее я скажу, почему это не страшно.

STLPort включает в

и
такую хеш-функцию как шаблон функции. Однако эта функция не работает для любого объекта, так как невозможно создать общей хеш-функции, которая бы работала с любым вводом. Вместо этого имеется несколько специализированных встроенных типов, наиболее часто используемых для ключей в хеш-таблицах. Например, если требуется посмотреть, как выглядит значение хеша, хешируйте строку символов.

std::hash hashFun;

std::cout << "\"Hashomatic\" хешируется как "

 << hashFun("Hashomatic") << '\n';

Вы увидите что-то похожее на следующее.

"Hashomatic" хешируется как 189555649

STLPort предоставляет специализации для следующих типов: 

char*
, 
const char*
, 
char
, 
unsigned char
, 
signed char
, 
short
, 
unsigned short
, 
int
, 
unsigned int
, 
long
и 
unsigned long
. Кажется, что их очень много, но в целом это означает, что библиотека содержит встроенные хеш-функции, которые поддерживают символьные строки и числа. Если требуется хешировать что-то другое, то просто укажите собственную хеш-функцию.

При помещении элемента в хеш-таблицу она определяет, какому участку принадлежит элемент, используя оператор взятия остатка от деления и число участков, т.е. 

hashFun(key) % bucket_count()
. Это быстрый оператор, который указывает непосредственно на индекс в главном векторе, по которому начинается участок.

Хеш-контейнер можно использовать как обычный ассоциативный контейнер, используя для добавления элементов в, скажем, 

hash_map
оператор 
operator[]
. Разница заключается в том, что вы знаете, что вставка и поиск займут постоянное время, а не логарифмическое. Рассмотрим пример 6.9, который содержит простой класс, отображающий имена логинов на объекты 
Session
. Он использует некоторые из возможностей хеш-контейнеров, описываемых в этом рецепте.

Пример 6.9. Простой менеджер сессий

#include 

#include 

#include 


using namespace std;


class Session { /* ... */ };


// Облегчение читаемости с помощью typedef

typedef hash_map SessionHashMap;


class SessionManager {

public:

 SessionManager() : sessionMap_(500) {} // Инициализация хеш-таблицы

                     // 500-ми участками


 ~SessionManager() {

 for (SessionHashMap::iterator p = sessionMap_.begin();

  p != sessionMap_.end(); ++p)

  delete (*p).second; // Удаление объекта Session

 }


 Session* addSession(const string& login) {

  Session* p = NULL;

  if (!(p = getSession(login))) {

  p = new Session();

  sessionMap_[login] = d; // Присвоение новой сессии с помощью

  }             // operator[]

  return(p);

 }


 Session* getSession(const string& login) {

  return(sessionMap_[login]);

 }

 // ...


private:

 SessionHashMap sessionMap_;

};

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

По хеш-функциям и таблицам написано огромное количество книг. Если вы заинтересовались этим вопросом, поищите в Google «C++ hash function».

Смотри также

Рецепт 6.6.

6.8. Хранение объектов в упорядоченном виде

Проблема

Требуется сохранить набор объектов в заданном порядке, например с целью доступа к упорядоченным диапазонам этих объектов без их пересортировки при каждом таком обращении.

Решение

Используйте ассоциативный контейнер 

set
, объявленный в
, который хранит элементы в упорядоченном виде. По умолчанию он использует стандартный шаблон класса 
less
(который для своих аргументов вызывает 
operator<
), а можно передать в него собственный предикат сортировки. Пример 6.10 показывает, как сохранить строки в 
set
.

Пример 6.10. Хранение строк в set

#include 

#include 

#include 


using namespace std;


int main() {

 set setStr;

 string s = "Bill";

 setStr.insert(s);

 s = "Steve";

 setStr.insert(s);

 s = "Randy";

 setStr.insert(s);

 s = "Howard";

 setStr.insert(s);

 for (set::const_iterator p = setStr.begin();

  p != setStr.end(); ++p)

  cout << *p << endl;

}

Так как значения хранятся в упорядоченном виде, вывод будет выглядеть так.

Bill

Howard

Randy

Steve

Обсуждение

set
(набор) — это ассоциативный контейнер, который предоставляет логарифмическую сложность вставки и поиска и постоянную сложность удаления элементов (если требуется удалить найденный элемент), 
set
— это уникальный ассоциативный контейнер, что означает, что никакие два элемента не могут быть равны, однако если требуется хранить несколько экземпляров одинаковых элементов, используйте 
multiset
, 
set
можно представить как набор в математическом смысле, т.е. коллекцию элементов, в дополнение обеспечивающую поддержание определенного порядка элементов.

Поддерживаются вставка и поиск элементов, но, как и список, набор не позволяет производить произвольный доступ к элементам. Если требуется получить что-то из набора, то можно найти элемент с помощью метода 

find
или перебрать элементы с помощью 
set::iterator
или 
set::const_iterator
. Объявление набора имеет знакомый вид.

set

 typename LessThanFun = std::less, // Функция/Функтор

                     // используемый для сортировки

 typename Alloc = std::allocator > // Распределитель памяти

Указывать 

Key
требуется всегда, иногда требуется предоставить собственную 
LessThanFun
, а указывать собственный распределитель требуется очень редко (так что я не буду здесь его описывать).

Параметр шаблона 

Key
— это, как и в случае с другими стандартными контейнерами, тип сохраняемых элементов. Для 
set
он определяется через 
typedef
как 
set::key_type
, так что доступ к нему есть при выполнении программы. Класс 
Key
должен обеспечивать конструктор копирования и присвоение, и все.

Пример 6.10 показывает, как использовать 

set
для строк. Использование набора для хранения объектов других типов работает точно так же — объявите набор с именем класса в качестве параметра шаблона.

std::set setMyObjs;

Это все, что требуется сделать для использования набора простейшим образом. Но в большинстве случаев жизнь не будет такой простой. Например, при сохранении в наборе указателей использовать предикат сортировки по умолчанию нельзя, так как он просто отсортирует объекты по их адресам. Чтобы гарантировать, что элементы будут отсортированы правильно, требуется создать собственный предикат, выполняющий сравнение «меньше чем». Пример 6.11 показывает, как это делается.

Пример 6.11. Хранение указателей в set

#include 

#include 

#include 

#include 

#include 


using namespace std;


// Класс для сравнения строк, переданных через указатели

struct strPtrLess {

 bool operator()(const string* p1,

  const string* p2) {

  assert(p1 && p2);

  return(*p1 < *p2);

 }


 int main() (

  set setStrPtr; // Передаем специальный

                    // «меньше чем» функтор

 string s1 = "Tom";

 string s2 = "Dick";

 string s3 = "Harry";

 setStrPtr.insert(&s1);

 setStrPtr.insert(&s2);

 setStrPtr.insert(&s3);

 for (set::const_iterator p =

  setStrPtr.begin(); p != setStrPtr.end(); ++p)

  cout << **p << endl; // Разыменовываем итератор и то, на что

            // он указывает

}

strPtrLess
возвращает истину, если строка, на которую указывает 
p1
, меньше, чем та, на которую указывает 
p2
. Это делает его двоичным предикатом, так как он принимает два аргумента и возвращает 
bool
. Так как 
operator<
определен для 
string
, для сравнения я использую именно его. На самом деле, если требуется использовать более общий подход, используйте для предиката сравнения шаблон класса

template

class ptrLess {

public:

 bool operator()(const T* p1,

  const T* p2) {

  assert(p1 && p2);

  return(*p1 < *p2);

 }

};

Это работает для указателей на любые объекты, для которых определен 

operator<
. Объявление набора с его использованием имеет такой вид.

set > setStrPtr;

set
поддерживает многие из функций, поддерживаемых другими стандартными последовательными контейнерами (например, 
begin
, 
end
, 
size
, 
max_size
) и другими ассоциативными контейнерами (например, 
insert
, 
erase
, 
clear
, 
find
).

При использовании 

set
помните, что при каждом изменении состояния набора выполняется его сортировка. Когда число его элементов велико, логарифмическая сложность добавления или удаления элементов может оказаться очень большой — вам действительно требуется, чтобы объекты сортировались каждый раз? Если нет, то для повышения производительности используйте 
vector
или 
list
и сортируйте его только тогда, когда это необходимо, что обычно имеет сложность порядка n*log(n).

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

Проблема

Имеется несколько экземпляров стандартного контейнера (

list
, 
set
и т.п.) и требуется сохранить их в еще одном контейнере.

Решение

Сохраните в главном контейнере указатели на остальные контейнеры. Например, можно использовать 

map
для хранения ключа типа 
string
и указателя на 
set
как значения. Пример 6.12 показывает простой класс журналирования транзакций, который хранит данные как map из пар, состоящих из 
string
и указателей на 
set
.

Пример 6.12. Хранение набора указателей в отображении

#include 

#include 

#include 

#include 


using namespace std;


typedef set SetStr

typedef map MapStrSetStr;


// Фиктивный класс базы данных

class DBConn {

public:

 void beginTxn() {}

 void endTxn() {}

 void execSql(string& sql) {}

};


class SimpleTxnLog {

public:

 SimpleTxrLog() {}

 ~SimpleTxrLog() {purge();}


 // Добавляем в список выражение SQL

 void addTxn(const string& id

  const string& sql) {

  SetStr* pSet = log_[id]; // Здесь создается запись для

  if (pSet == NULL) {    // данного id, если ее еще нет

  pSet = new SetStr();

  log_[id] = pSet;

  }

  pSet->insert(sol);

 }


 // Применение выражений SQL к базе данных, по одной транзакции

 // за один раз

 void apply() {

  for (MapStrSetStr::iterator p = log_.begin();

  p != log_.end(); ++p) {

  conn_->beginTxn();

  // Помните, что итератор отображения ссылается на объект

  // типа pair. Указатель на набор хранится в p->second.

  for (SetStr::iterator pSql = p->second->begin();

   pSql != p->second->end(); ++pSql) {

   string s = *pSql;

   conn_->execSql(s);

   cout << "Executing SQL: " << s << endl;

  }

  conn_->endTxn();

  delete p->second;

  }

  log_.clear();

 }


 void purge() {

  for (MapStrSetStr::iterator p = log_.begin();

  p != log_.end(); ++p)

  delete p->second;

 log_.clear();

 }

 //...


private:

 MapStrSetStr log_;

 DBConn* conn_;

}
;

Обсуждение

Пример 6.12 предлагает ситуацию, где может потребоваться хранение одного контейнера в другом. Представьте, что требуется сохранить набор выражений SQL в виде пакета, выполнить их в будущем все сразу для реляционной базы данных. Именно это делает 

SimpleTxnLog
. Чтобы сделать его еще полезнее, можно добавить в него другие методы, а для обеспечения безопасности — добавить обработку исключений, но целью этого примера является показать, как хранить один тип контейнеров в другом.

Для начала я создаю несколько 

typedef
, облегчающих чтение кода.

typedef std::set SetStr;

typedef std::map MapStrSetStr;

При использовании шаблонов шаблонов (шаблонов… и т.д.) объявления становятся очень длинными, что затрудняет их чтение, так что облегчите себе жизнь, использовав 

typedef
. Более того, использование 
typedef
облегчает внесение изменений в объявление шаблонов, избавляя от необходимости выполнять поиск и замену во многих местах большого количества исходных файлов.

Класс 

DBConn
— это фиктивный класс, который представляет подключение к реляционной базе данных. Интересно здесь то, как в 
SimpleTxnLog
определяется метод 
addTxn
. В начале этой функции я смотрю, существует ли уже объект набора для переданного 
id
.

SetStr* pSet = log_[id];

log_
— это 
map
(см. рецепт 6.6), так что 
operator[]
выполняет поиск 
id
и смотрит, связаны ли с ним какие-либо данные. Если да, то возвращается объект данных, и 
pSet
не равен 
NULL
. Если нет, он создается, и возвращается указатель, который будет равен 
NULL
. Затем я проверяю, указывает ли на что-то 
pSet
, и определяю, требуется ли создать еще один набор.

if (pSet == NULL) {

 pSet = new SetStr(); // SetStr = std::set

 log_[id] = pSet;

}

Так как 

pSet
— это копия объекта данных, хранящихся в map (указатель на набор), а не само значение, то после создания 
set
я должен поместить его обратно в связанный с ним ключ в 
map
. После этого все, что остается сделать, — это добавить элемент в набор и выйти.

pSet->insert(sql);

Выполнив указанные шаги, я в один контейнер (

map
) добавил указатель на адрес другого контейнера (
set
). Что я не делал — это добавление объекта 
set
в 
map
. Разница очень существенна. Так как контейнеры обладают семантикой копирования, следующий код приведет к копированию всего набора 
s
в 
map
.

set s;

// Заполнить s данными...

log_[id] = s; // Скопировать s и добавить его копию в log_

Это приведет к огромному числу дополнительных нежелательных копирований. Следовательно, общее правило при использовании контейнеров из контейнеров — это использовать указатели на контейнеры.

ТЕЛЕГРАМ

Канал с обзорами, анонсами новинок и книжными подборками

Книжный Вестник

Бот для удобного поиска книг (если не нашлось на сайте)

Поиск книг

Свежие любовные романы в удобных форматах

Любовные романы

О психологии, саморазвитии и личностном росте

Саморазвитие

Детективы и триллеры, все новинки

Детективы

Фантастика и фэнтези, все новинки

Фантастика

Отборные классические книги

Классика
ВКОНТАКТЕ

Цитаты, афоризмы, стихи, книжные подборки, обсуждения и многое другое

Книжный Вестник
БИБЛИОТЕКИ

Библиотека с любовными романами, которая наверняка придётся по вкусу женской части аудитории

Любовные романы

Библиотека с фантастикой и фэнтези, а также смежных жанров

Фантастика

Самые популярные книги в формате фб2

Топ фб2 книги