STL. Последовательные контейнеры — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
Строка 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...