STL. Последовательные контейнеры — различия между версиями
Строка 46: | Строка 46: | ||
=== deque === | === deque === | ||
+ | <source lang="cpp"> | ||
+ | #include <deque> | ||
+ | std::deque<int> d; | ||
+ | d.push_back(10); | ||
+ | d.push_front(7); | ||
+ | // + методы, присущие vector | ||
+ | </source> | ||
+ | |||
+ | == Итераторы == | ||
+ | При работе с непрерывными массивами мы использовали указатели с операциями <code>*p</code> и <code>++p</code>. У контейнеров для таких целей применяются итераторы. | ||
+ | <source lang="cpp"> | ||
+ | vector<int> v(100, 0); | ||
+ | vector<int>::iterator it = v.begin(); | ||
+ | for (; it != v.end(); ++it) | ||
+ | *it = 5; | ||
+ | </source> | ||
+ | Если заменить вектор на другой контейнер, последний цикл будет работать по-прежнему (с учётом того, что такой конструктор есть тольео у вектора). | ||
+ | '''Замечание:''' В условии цикла разумно использовать именно оператор !=, а не <, поскольку последний определён не для всех итераторов. | ||
+ | |||
+ | == list == | ||
to be continued... | to be continued... |
Версия 16:59, 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
to be continued...