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

Материал из SEWiki
Перейти к: навигация, поиск
Строка 87: Строка 87:
  
 
=== Различные замечания ===
 
=== Различные замечания ===
# <code>l.size()<//code> в большинстве реализаций работает за О(1).
+
* <code>l.size()</code> в большинстве реализаций работает за О(1).
# В <code>deque</code> удаление и добавление в начало и конец работают за О(1).
+
* В <code>deque</code> удаление и добавление в начало и конец работают за О(1).
# <code>vector</code> не умеет уменьшаться, он только растёт.
+
* <code>vector</code> не умеет уменьшаться, он только растёт.
 
<source lang="cpp">
 
<source lang="cpp">
 
v.clear(); //v.erase(v.begin(), v.end());
 
v.clear(); //v.erase(v.begin(), v.end());
Строка 97: Строка 97:
 
vector<int>(v).swap(v);
 
vector<int>(v).swap(v);
 
</source>  
 
</source>  
# При расширении массивов могут возникнуть проблемы, а именно, инвалидация итераторов. Можно использовать:
+
* При расширении массивов могут возникнуть проблемы, а именно, инвалидация итераторов. Можно использовать:
 
<source lang="cpp">
 
<source lang="cpp">
 
v.reserve(100); //зарезервировать размер буфера, равный 100
 
v.reserve(100); //зарезервировать размер буфера, равный 100
Строка 103: Строка 103:
 
v.capacity; //размер буфера
 
v.capacity; //размер буфера
 
</source>
 
</source>
# Инвалидация может так же произойти и при удалении элементов (итератор будет указывать не на тот элемент, который ожидается). Ниже приведены два примера правильной работы с итераторами:
+
* Инвалидация может так же произойти и при удалении элементов (итератор будет указывать не на тот элемент, который ожидается). Ниже приведены два примера правильной работы с итераторами:
 
<source lang="cpp">
 
<source lang="cpp">
 
//удаляем все элементы, кратные 2
 
//удаляем все элементы, кратные 2
Строка 119: Строка 119:
 
   }
 
   }
 
}
 
}
 +
</source>
  
 
=== string ===
 
=== string ===
 +
<source lang="cpp">
 +
typedef basic_string<char> string;
 +
typedef basic_string<wchar> wstring;
 +
</source>
 +
Стратегия cow (copy on write) позволяет выиграть при копировании.
 +
 +
Для <code>const</code> объектов есть <code>const_iterator</code>.
 +
 +
Строки на самом деле имеют три параметра в конструкторе. Один из них - аллокатор, отвечает за распределение памяти, и другой - chartrait, определяет механизм сравнения строк.
  
to be continued...
+
=== Код в стиле С ===
 +
* <code>s.c_str();</code> возвращает строку в стиле С.
 +
* <code>string(str);</code> конструирует строку в стиле С++ от строки в стиле С.
 +
* <code>&v[0]; v.size();</code> возвращают указатель на начало массива и его длину.
 +
* <code>vector|list|deque<int>(p, p+size);</code> конструируют вектор, список или деку соответственно от массива.

Версия 17:31, 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() в большинстве реализаций работает за О(1).
  • В 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

typedef basic_string<char> string;
typedef basic_string<wchar> wstring;

Стратегия cow (copy on write) позволяет выиграть при копировании.

Для const объектов есть const_iterator.

Строки на самом деле имеют три параметра в конструкторе. Один из них - аллокатор, отвечает за распределение памяти, и другой - chartrait, определяет механизм сравнения строк.

Код в стиле С

  • s.c_str(); возвращает строку в стиле С.
  • string(str); конструирует строку в стиле С++ от строки в стиле С.
  • &v[0]; v.size(); возвращают указатель на начало массива и его длину.
  • vector|list|deque<int>(p, p+size); конструируют вектор, список или деку соответственно от массива.