Программирование. Принципы и практика использования C++ Исправленное издание
вернуться

Страуструп Бьерн
Шрифт:

Б.4.6. Операции над стеком и двусторонней очередью

Стандартные контейнеры

vector
и
deque
обеспечивают эффективные операции над концами (
back
) последовательности элементов. Кроме того, контейнеры
list
и
deque
обеспечивают аналогичные операции над началом (
front
) своей последовательности.

Обратите внимание на то, что функции

push_front
и
push_back
копируют элемент в контейнер. Это значит, что размер контейнера увеличивается (на единицу). Если копирующий конструктор элемента может генерировать исключения, то вставка может завершиться отказом.

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

front
и
back
(см. раздел Б.4.5). Мы не ставили себе задачу перечислить все ограничения; попробуйте догадаться об остальных (как правило, компиляторы сообщают пользователям об их неверных догадках) или обратитесь к более подробной документации.

Б.4.7. Операции над списком

Ниже приведены операции над списком.

Результат

q
функции
insert
ссылается на последний вставленный элемент. Результат
q
функции
erase
ссылается на элемент, следующий за последним удаленным элементом.

Б.4.8. Размер и емкость

Размер — это количество элементов в контейнере; емкость — это количество элементов, которое контейнер может содержать до того, как потребуется дополнительно увеличить память

Изменяя размер или емкость, можно переместить элементы в новое место. Из этого следует, что итераторы (а также указатели и ссылки) на элементы могут стать некорректными (т.е. относиться к старым адресам).

Б.4.9. Другие операции

Контейнеры можно копировать (см. раздел Б.4.3), сравнивать и обменивать.

Если сравнение контейнеров производится с помощью соответствующего оператора (например,

<
), то их элементы сравниваются с помощью эквивалентного оператора для сравнения элементов (например,
<
).

Б.4.10. Операции над ассоциативными контейнерами

Ассоциативные контейнеры обеспечивают поиск на основе ключей.

Упорядоченные ассоциативные контейнеры (

map
,
set
и др.) имеют необязательный шаблонный аргумент, указывающий тип предиката сравнения, например,
set<K,C>
использует предикат
C
для сравнения значений типа
K
.

Первый итератор пары, возвращенной функцией

equal_range
, равен
lower_bound
, а второй —
upper_bound
. Вы можете вывести на печать значения всех элементов, имеющих ключ "
Marian
" в контейнере
multimap<string,int>
, написав следующий код:

string k = "Marian";

typedef multimap<string,int>::iterator MI;

pair<MI,MI> pp = m.equal_range(k);

if (pp.first!=pp.second)

cout << "elements with value ' " << k << " ':\n";

else

cout << "no element with value ' " << k << " '\n";

for (MI p = pp.first; p!=pp.second; ++p) cout << p–>second << '\n';

В качестве альтернативы можно выполнить следующую эквивалентную инструкцию:

pair<MI,MI> pp = make_pair(m.lower_bound(k),m.upper_bound(k));

Однако эта инструкция выполняется вдвое дольше. Алгоритмы

equal_range
,
lower_bound
и
upper_bound
можно выполнять также для упорядоченных последовательностей (раздел Б.5.4). Определение класса
pair
приведено в разделе Б.6.3.

Б.5. Алгоритмы

В заголовке

<algorithm>
определено около 60 алгоритмов. Все они относятся к последовательностям, определенным парами итераторов (для ввода) или одним итератором (для вывода).