STL. Последовательные контейнеры — различия между версиями
Строка 54: | Строка 54: | ||
</source> | </source> | ||
− | == Итераторы == | + | === Итераторы === |
При работе с непрерывными массивами мы использовали указатели с операциями <code>*p</code> и <code>++p</code>. У контейнеров для таких целей применяются итераторы. | При работе с непрерывными массивами мы использовали указатели с операциями <code>*p</code> и <code>++p</code>. У контейнеров для таких целей применяются итераторы. | ||
<source lang="cpp"> | <source lang="cpp"> | ||
Строка 63: | Строка 63: | ||
</source> | </source> | ||
Если заменить вектор на другой контейнер, последний цикл будет работать по-прежнему (с учётом того, что такой конструктор есть тольео у вектора). | Если заменить вектор на другой контейнер, последний цикл будет работать по-прежнему (с учётом того, что такой конструктор есть тольео у вектора). | ||
+ | |||
'''Замечание:''' В условии цикла разумно использовать именно оператор !=, а не <, поскольку последний определён не для всех итераторов. | '''Замечание:''' В условии цикла разумно использовать именно оператор !=, а не <, поскольку последний определён не для всех итераторов. | ||
− | == list == | + | === list === |
+ | <source lang="cpp"> | ||
+ | #incude <list> | ||
+ | std::list<int> l; | ||
+ | l.push_back(7); | ||
+ | //и другие аналогичные методы | ||
+ | </source> | ||
+ | |||
+ | === Использование итераторов === | ||
+ | Вставка в список производится по итераторам: | ||
+ | <source lang="cpp"> | ||
+ | v.insert(v.begin() + 5, 10); //вставить 10 на 5-ю позицию | ||
+ | v.end(); //указывает на элемент после последнего! | ||
+ | </source> | ||
+ | Рассмотрим простой пример: | ||
+ | |||
+ | |1|2|3|4|5|6|7|8|9| | ||
+ | |||
+ | <code>v.begin() + 5</code> указывает на 6. Если от него получить итератор, который бежит в обратном направлении, он будет указывать на 5. Поэтому итератор удобнее рассматривать как указывающий на промежуток, а не на конкретный элемент. | ||
+ | |||
+ | === Различные замечания === | ||
+ | # <code>l.size()<//code> в большинстве реализаций работает за О(1). | ||
+ | # В <code>deque</code> удаление и добавление в начало и конец работают за О(1). | ||
+ | # <code>vector</code> не умеет уменьшаться, он только растёт. | ||
+ | <source lang="cpp"> | ||
+ | v.clear(); //v.erase(v.begin(), v.end()); | ||
+ | //чтобы действительно очистить буфер, надо: | ||
+ | vector<int>().swap(v); | ||
+ | //чтобы заменить, немного иначе: | ||
+ | vector<int>(v).swap(v); | ||
+ | </source> | ||
+ | # При расширении массивов могут возникнуть проблемы, а именно, инвалидация итераторов. Можно использовать: | ||
+ | <source lang="cpp"> | ||
+ | v.reserve(100); //зарезервировать размер буфера, равный 100 | ||
+ | v.reserve(v.size() + 100); | ||
+ | v.capacity; //размер буфера | ||
+ | </source> | ||
+ | # Инвалидация может так же произойти и при удалении элементов (итератор будет указывать не на тот элемент, который ожидается). Ниже приведены два примера правильной работы с итераторами: | ||
+ | <source lang="cpp"> | ||
+ | //удаляем все элементы, кратные 2 | ||
+ | for (it = v.begin(); it != v.end(); ) { | ||
+ | if (*it % 2) | ||
+ | v.erase(it); | ||
+ | else | ||
+ | ++it; | ||
+ | } | ||
+ | //вставим перед элементами, кратными 2, новые элементы, равные 0 | ||
+ | for (it = v.begin(); it != v.end(); ++it) { | ||
+ | if (*it % 2) { | ||
+ | it = v.insert(it, 0); | ||
+ | ++it; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | === string === | ||
to be continued... | to be continued... |
Версия 17:20, 20 марта 2011
Внимание! В лекции могут содержаться ошибки и неточности. Прошу исправлять по мере обнаружения.
Содержание
Введение в STL
STL - Standart Template Library. Она стандартизированна. Существует несколько реализаций, в том числе:
- GCC
- MS
- STL Port
В неё входят:
- Контейнеры
- Итераторы
- Алгоритмы
Последовательные контейнеры
Ко всем последовательным контейнерам предъявляются общие требования:
- Copy-constructable (т.е. публичный конструктор копирования).
- Assignable (т.е. публичный оператор присваивания).
- Стандартная семантика.
Разновидности
-
vector
- массив подряд идущих элементов. -
list
- список взаимосвязанных элеметов. -
deque
- совокупность связанных в список массивов фиксированной длины + индексная таблица. -
string/wstring
- строка.
Для использования этих контейнеров необходимо перед названием типов писать std::
.
vector
#include <vector>
using std::vector;
std::vector<int> v;
У шаблона есть и второй параметр - аллокатор. Он отвечает за стратегию распределения памяти. Его использовать не надо!
Основные методы вектора представлены ниже:
v.push_back(13); //добавить элемент к вектору
v.empty(); //вектор пуст?
v.size(); //количество элементов в векторе
v[i]; //обращение к i-му элементу вектора
v.at(i); //то же самое
v.erase(it); //удаление элемента по итератору (о них будет рассказано далее)
Пример хранения структуры графа:
vector<vector<int> > g;
deque
#include <deque>
std::deque<int> d;
d.push_back(10);
d.push_front(7);
// + методы, присущие vector
Итераторы
При работе с непрерывными массивами мы использовали указатели с операциями *p
и ++p
. У контейнеров для таких целей применяются итераторы.
vector<int> v(100, 0);
vector<int>::iterator it = v.begin();
for (; it != v.end(); ++it)
*it = 5;
Если заменить вектор на другой контейнер, последний цикл будет работать по-прежнему (с учётом того, что такой конструктор есть тольео у вектора).
Замечание: В условии цикла разумно использовать именно оператор !=, а не <, поскольку последний определён не для всех итераторов.
list
#incude <list>
std::list<int> l;
l.push_back(7);
//и другие аналогичные методы
Использование итераторов
Вставка в список производится по итераторам:
v.insert(v.begin() + 5, 10); //вставить 10 на 5-ю позицию
v.end(); //указывает на элемент после последнего!
Рассмотрим простой пример:
|1|2|3|4|5|6|7|8|9|
v.begin() + 5
указывает на 6. Если от него получить итератор, который бежит в обратном направлении, он будет указывать на 5. Поэтому итератор удобнее рассматривать как указывающий на промежуток, а не на конкретный элемент.
Различные замечания
-
l.size()<//code> в большинстве реализаций работает за О(1).
- В <code>deque удаление и добавление в начало и конец работают за О(1).
-
vector
не умеет уменьшаться, он только растёт.
v.clear(); //v.erase(v.begin(), v.end());
//чтобы действительно очистить буфер, надо:
vector<int>().swap(v);
//чтобы заменить, немного иначе:
vector<int>(v).swap(v);
- При расширении массивов могут возникнуть проблемы, а именно, инвалидация итераторов. Можно использовать:
v.reserve(100); //зарезервировать размер буфера, равный 100
v.reserve(v.size() + 100);
v.capacity; //размер буфера
- Инвалидация может так же произойти и при удалении элементов (итератор будет указывать не на тот элемент, который ожидается). Ниже приведены два примера правильной работы с итераторами:
//удаляем все элементы, кратные 2
for (it = v.begin(); it != v.end(); ) {
if (*it % 2)
v.erase(it);
else
++it;
}
//вставим перед элементами, кратными 2, новые элементы, равные 0
for (it = v.begin(); it != v.end(); ++it) {
if (*it % 2) {
it = v.insert(it, 0);
++it;
}
}
=== string ===
to be continued...