Site Tools


stl

Контейнеры

Последовательные контейнеры

vector

+ скоростной случайный доступ O(1)
+ скоростная вставка и изъятие в конец. O(1)
+ может распологаться в непрерывном участке памяти -> арифметика указателей, копирование памяти и т.д.
- медленная вставка (insert) или изъятее (erase) данных из середины, так как приходится перекраивать всю структуру. O(n)

list

+ В любом месте контейнера вставка и удаление производятся очень быстро — за O(1).
- Доступ по индексу за O(n)
- Поиск перебором медленнее, чем у вектора из-за большего времени доступа к элементу.
- не имеет произвольного доступа по [] и .at()

deque

+ скоростной случайный доступ
+ быстрый доступ к обоим концам O(1)
- медленная вставка или изъятие из середины
Ассоциативные контейнеры

set и multiset

+ хранит только ключевые объекты. Каждому объекту - один ключ.
+ multi -                         Каждому объекту - может быть сопоставленно множество ключей.

map и multimap

+ ассоциирует ключевые объекты с целевым объектом, хранящим значение. Одному значению - один ключ.
+ multi -                                                             Одному значению - может быть сопоставленно множество ключей.



Итераторы

со случайным доступом  оба направления + случайный доступ
двунаправленный        оба направления
прямой                 только направленное
выходной               только запись в поток\файл
входной                только чтение потока\файла

Адаптеры интераторов

  • обратный итератор - позволяет проходить в обратном порядке
list<int>::reverse_iterator revit;
revit = theList.rbegin();
while(revit != theList.rend()){
    cout << *revit++ << " ";
}
  • итератор вставки - copy и mergy будут именно вставлять данные а не замещать существующие.
copy(dequeObj1.begin(), dequeObj1.end(), front_inserter(dequeObj2)); // а также back_inserter и inserter(dequeObj2, dequeObj2.begin())
  • итератор неиницилизированного хранения - хранить в участке памяти еще не инициализированные данные.

Алгоритмы

#include <algorithm>

sort
find
count
for_each

Адаптеры

stack - FILO добавление и удаление элементов осуществляется с одного конца.
queue - FIFO в один конец добавляем элементы, а с другого — вынимать.
priority_queue - предоставляет приоритеты в очереди

Функциональный объект

#include <functional>

greater

FAQ

Требование к типам, которые можно использовать с контейнерами.
Конструктор копии		Создает новый элемент, идентичный старому		Используется при каждой вставке элемента в контейнер
Оператор присваивания		Заменяет содержимое элемента копией исходного элемента	Используется при каждой модификации элемента
Деструктор			Разрушает элемент					Используется при каждом удалении элемента
Конструктор по умолчанию	Создает элемент без аргументов				Применяется только для определенных операций
operator==			Сравнивает два элемента					Используется при выполнении operator== для двух контейнеров
operator<			Определяет, меньше ли один элемент другого		Используется при выполнении operator< для двух контейнеров
гарантии по алгоритмической сложности операций
пример: http://stackoverflow.com/questions/181693/what-are-the-complexity-guarantees-of-the-standard-containers
Структуры данных
vector - при резервирование использует непрерывный участок памяти, в следствии может вести себя как обычный массив.
list и deque - не заботятся о своем размещение и часто сегментированны.
set и map - древовидная, куча или таблица.
auto_ptr: для чего нужен и почему нельзя использовать в контейнерах.
умный указатель - сам заботится о своем удаление. Причин несколько, одна из наиболее значимых - при присвоение auto_ptr, исходная auto_ptr деряет доступ к своему значению.
Разница между контейнерами и адаптерами контейнеров
Задачки на выбор контейнеров

Требования к функторам
Какие алгоритмы требуют упорядоченности
You could leave a comment if you were logged in.
stl.txt · Last modified: 2013/04/10 04:54 by konovalov

Page Tools