o std::list очень медленно осуществляет обход элементов из-за особенностей размещения данных;
o std::vector и std::deque всегда работают быстрее с типами данных небольших размеров;
o std::list хорошо обрабатывает большие элементы;
o std::deque показывает лучшую производительность при вставке элементов в случайные позиции, в особенности - в начало очереди;
o std::deque и std::vectorплохо справляются с данными с высокой стоимостью копирующих конструкторов и операторов присваивания.
Соответственно, заключение о том, где использовать контейнеры:
o Сложные вычисления: std::vector или std::deque;
o Линейный поиск: std::vector или std::deque;
o Случайная вставка или удаление: std::deque или std::list. Если размер данных мал, то лучше использовать std::deque;
o Работа с данными больших размеров: std::list;
o Нетривиальные типы данных: std::list;
o Вставка в начало: std::deque или std::list.
Алгоритмы STL
Итераторы
Итераторы предназначены для перебора элементов контейнеров. Их универсальность позволяет писать код, не зависящий от типа контейнера. Итераторы имеют семантику указателей:
Поддерживают операции ++, --, *, ->.
Полседовательность задается двумя итераторами:
Итератор p указывает на первый элемент контейнера, итератор q - на элемент, следующий за последним. На первый взгляд такой способ задания последовательности может показаться неестественным. Казалось бы, разумнее задавать последовательность таким образом, при котором итератор q указывает на ее последний элемент, то есть представлять последовательность в виде отрезка [p, q]. Но тогда у нас не было бы возможности задать пустую последовательность: если оба итератора p и qуказывают на один и тот же элемент, то это означало бы, что в контейнере содержится один элемент. В то время как представление последовательности в виде полуинтервала [p, q) позволяет задать пустой контейнер: если p и q указывают на один и тот же элемент, то последовательность пуста.
Итераторы можно разделить на категории:
Random access iterator (RA) Повторяет полностью синтаксис и семантику указателя (самый сильный итератор): поддерживает ++, --, [], арифметические операции.
Bidirectional iterator (BiDi) Поддерживает только ++, --. Это более слабый итератор.
Forward iterator (Fwd) Поддерживает только ++. Forward итераторы делятся на две подкатегории:
Output iterator ++, write (только запись)
Input iterator ++, read (только чтение)
RA ⊂ BiDi ⊂ Fwd У std::vector и std::deque RA итераторы, у остальных контейнеров - BiDi.
Также существует Reverse Iterator (rev), у которого операции ++ и -- инвертированы (действуют в обратные стороны к таким же операциям у обычного итератора). Получение из reverse итератора обычного итератора (original) производится с помощью функции base(). Получение из обычного итератора reverse итератора - с помощью конструктора. Например:
using namespace std;list<int> l;for (list<int>::iterator i = l.begin(); i != l.end(); ++i){ ...}for (list<int>::reverse_iterator i = l.rbegin(); i != l.rend(); ++i){ list<int>::iterator j = i.base(); ...}
rbegin эквивалентен end, rend эквивалентен begin:
Если reverse итератор указывает на 3 (третий элемент на рисунке), то обычный будет указывать на 4 (четвертый элемент на рисунке). Об этом важно помнить. base() - это функция, которая выполняет неявное преобразование.
Из любого BiDi итератора можно получить rev итератор. Например, это можно сделать самим, написав класс, который содержит обычный итератор, и в котором перегружены операторы ++ и --. Но это уже написано:
#include <iterator> std::reverse_iterator<It> rev_it(it); // сконструировали rev итератор от BiDi
Это бывает нужно, если, например, требуется написать шаблонную функцию, внутри которой должны выполняться какие-то операции с контейнером в обратном порядке, и которая не должна зависеть от типа контейнера (reverse итераторы есть у всех контейнеров). Например:
template<class It>void f (It p, It q){ copy(std::reverse_iterator<It>(p), std::reverse_iterator<It>(q), out);}
Примеры STL алгоритмов для итераторов:
std::advance(it, n) Продвигает итератор на n позиций вперед (аналогично p += n для указателей). Для RA итераторов использует [], для BiDi - ++. Если происходит выход за границы контейнера, то undefined behaviour.
std::distance(it1, it2) Возвращает расстояние между итераторами (аналогично q - p для указателей) при условии, что it1 ≤ it2 В противном случае undefined behaviour, так как этот алгоритм фактически вычисляет, сколько раз нужно продвинуть итератор it1 на одну позицию, чтобы получить итератор it2.
Кроме того, существует класс iterator_traits<It>. Он предназначен для получения информации о связанных с данным итератором типах. Этот класс не создает данных, а просто содержит typedef'ы:
iterator_traits<It>::value_type - тип элемента, на который может указывать итератор.
iterator_traits<It>::reference - тип ссылки на элемент, на которую может указывать итератор.
iterator_traits<It>::pointer - тип указателя на элемент, на который может указывать итератор.
iterator_traits<It>::difference_type - тип значения, которое получается при вычитании одного итератора из другого.
Алгоритмы
#include <algorithm>
В STL более 100 алгоритмов. Мы будем рассматривать не все. Мы не будем рассматривать:
Операции с неинициализированными данными.
Алгоритмы для работы с кучей.
Операции над множествами.
Операции с перестановками.
Мы будем рассматривать следующие алгоритмы:
Микро-алгоритмы
Алгоритмы, не модифицирующие последовательности
Алгоритмы типа find
Модифицирующие алгоритмы
Микро-алгоритмы
swap(T &a, T &b) Меняет местами значения двух элементов.
iter_swap(It p, It q) Меняет местами значения элементов, на которые указывают итераторы.
max(const T &a,const T &b ) Возвращает максимальный элемент.
min(const T &a,const T &b ) Возвращает минимальный элемент.
У этих алгоритмов есть версии с тремя параметрами. Третий параметр принимает бинарный предикат, задающий упорядоченность объектов.
Алгоритмы, не модифицирующие последовательности
size_t count(It p, It q, const T &x) Возвращает, сколько раз элемент со значением x входит в последовательность, заданную итераторами p и q.
size_t count_if(It p, It q, Pr pred) Возвращает, сколько раз предикат pred возвращает значение true. Например, count_if(p, q, divides_by(8)) вернет, сколько элементов кратно 8;
Алгоритмы типа find
find(It p, It q, const T &x) Возвращает итератор на первое вхождение элемента x в последовательность, заданную итераторами p и q.
find_if(It p, It q, Pr pred) Возвращает итератор на первый элемент, для которого предикат pred вернул значение true.
find_first_of(It p, It q, Itr i, Itr j) Возвращает итератор на первое вхождение любого элемента из последовательности, заданной итераторами i и j, в последовательность, заданную итераторами pи q. Последовательности могут быть разных типов (например std::vector и std::list).
min_element(It p, It q) Возвращает итератор на минимальный элемент последовательности.
max_element(It p, It q) Возвращает итератор на максимальный элемент последовательности.
equal(It p, It q, Itr i) Сравнивает две последовательности на эквивалентность. Вторая последовательность задается одним итератором, так как последовательности должны быть одинаковой длины. Если вторая короче, то undefined behaviour.
pair <It, Itr> mismach(It p, It q, Itr i) Возвращает пару итераторов, указывающую на первое несовпадение последовательностей.
F for_each(It p, It q, F func) Для каждого элемента последовательности применяет функтор func. Возвращаемое значение функтора после каждого применения игнорируется. Возвращает функтор func после его применения ко всем элементам.
bool binary_search(It p, It q, const T &x) Возвращает true, если в упорядоченной последовательности есть элемент, значение которого равно x, false в противном случае. Если хотим получить итератор на элемент со значением x, то нужно использовать алгоритмы lower_bound(It p, It q, const T &x), upper_bound(It p, It q, const T &x), equal_range(It p, It q, const T &x), которые выполняют то же, что и одноименные методы для контейнера std::set. Эти алгоритмы работают за линейное время на BiDi итераторах и за логарифмическое время на RA итераторах.
Все эти алгоритмы имеют версии с параметром, принимающим бинарный предикат, задающий упорядоченность объектов.
Модифицирующие алгоритмы
fill(It p, It q, const T &x), fill_n(It p, Size n, const T &x) Заполняют последовательность значениями, равными значению x.
generate(It p, It q, F gen), generate_n(It p, Size n, F gen) Заполняют последовательность значениями, сгенерированными функтором gen (например, генератором случайных чисел).
random_shuffle(It p, It q), random_shuffle(It p, It q, F &rand) Перемешивает элементы в случайном порядке: меняет местами каждый элемент с элементом, номер которого выбирается случайно. Третьим параметром можно задать функтор, который будет выбирать этот случайный номер. Можно передавать генератор случайных чисел, но распределение должно быть равномерным (каждая перестановка должна генерироваться с вероятностью 1/n!, а это совсем не то же самое, что каждый элемент окажется на i-м месте с вероятностью 1/n). Требует RA итераторов.
copy(It p, It q, Itr out) Копирует значения элементов последовательности, заданной итераторами p и q, в последовательность, начинающуюся с итератора out. copy_backward(It p, It q, Itr out) Копирует элементы последовательности, заданной итераторами p и q, в последовательность, заканчивающуюся итератором out. Итераторы должны быть BiDi.
remove_copy(It p, It q, Itr out, const T &x) Копирует значения элементов из последовательности, заданной итераторами p и q, в последовательность, начинающуюся с итератора out, за исключением элементов, значения которых равны значению x. remove_copy_if(It p, It q, Itr out, Pr pred) Копирует значения элементов из последовательности, заданной итераторами p и q, в последовательность, начинающуюся с итератора out, за исключением элементов, для которых предикат pred возвращает значение true.
reverse(It p, It q) Переставляет элементы в обратном порядке. reverse_copy(It p, It q, Itr out) Копирует значения элементов в обратном порядке.
rotate(It p, It middle, It q) Сдвигает элементы последовательности так, что элемент, на который указывает итератор middle становится первым.
Этот алгоритм реализован по-разному для разных категорий итераторов (RA, BiDi, Fwd).
swap_ranges(It p, It q, Itr i) Меняет местами элементы последовательности, заданной итераторами p и q, с соответствующими элементами последовательности, начинающейся с и итератораout.
remove(It p, It q, const T &x) Удаляет из последовательности элементы, значения которых совпадают по значению с x. Возвращает итератор на новый конец последовательности. Например:
o using namespace std;o vector<int> v;o ...o vector<int>::iterator new_end = std::remove(v.begin(), v.end(), 3); // хотим удалить все тройки
В действительности remove ничего не удаляет, так как ему не передается контейнер.
remove внутри себя как бы вызывает remove_copy_if. Поэтому последние два элемента в примере на рисунке останутся без изменений. Правильный вариант удаления:
Удаляем все, что находится между итератором, который вернул remove, и концом последовательности. Это называется remove-erase-idiom. remove_if(It p, It q, Pr pred) Удаляет из последовательности элементы, для которых предикат pred возвращает true. Возвращает итератор на новый конец последовательности.
unique(It p, It q), unique(It p, It q, Pr pred) Удаляет одинаковые подряд идущие элементы, оставляя только по одному элементу для каждого значения. Элементы последовательности должны быть отсортированы. Работает аналогично алгоритмам remove и remove_if, оставляя в начале только уникальные элементы, а в конце - то, что осталось. В качестве третьего параметра можно передавать предикат, сравнивающий два элемента и возвращающий true, если элементы равны, и false в противном случае. unique_copy(It p, It q, Itr out), unique_copy(It p, It q, Itr out, Pr pred) Копирует уникальные элементы в последовательность, начинающуюся с итератора out.
transform(It p, It q, Itr out, F func) К каждому элементу входящей последовательности применяет функтор func и записывает результат в последовательность, начинающуюся с итератора out. transform(It p, It q, Itr i, Iter out, F func) Применяет бинарный функтор func к каждой паре элементов из двух входящих последовательностей и записывает результат в результирующую последовательность.
accimulate(It p, It q, T i, F func) Последовательно применяет бинарный функтор func к парам (i, *p++), где i - некоторое начальное значение, которое затем каждый раз заменяется значением, которое возвращает функтор. Функтор должен возвращать значение типа T. Реализация этого алгоритма выглядит примерно следующим образом:
o while (p != q)o {o i = func(i, *(p++));o }o return i;
Например, если в качестве i передать 0, а в качестве func - функтор, вычисляющий сумму, то посчитаем сумму элементов последовательности. Если в качестве iпередать 1, а в качестве func - функтор, вычисляющий произведение, то получим произведение элементов и т.д.
sort(It p, It q), sort(It p, It q, Pr pred) Сортирует элементы последовательности в порядке возрастания. stable_sort(It p, It q), stable_sort(It p, It q, Pr pred) Сортирует элементы, сохраняя порядок элементов с одинаковыми значениями относительно друг друга. Эти алгоритмы требуют RA итераторов, поэтому на списке работать не будут. Но у списка есть собственные функции члены sort, stable_sort.
void nth_element(It p, It nth, It q), void nth_element(It p, It q, It nth, Pr pred) Позволяет получить n-й по порядку элемент (n-й по счету, как если бы массив был отсортирован), переставляя элементы таким образом, что все элементы до него меньше, либо равны ему, а элементы после - больше, либо равны ему.
partition(It p, It q, Pr pred) Переставляет элементы последовательности таким образом, что все элементы, для которых предикат вернул true, предшествуют тем, для которых он вернулfalse. Возвращает итератор на первый элемент из второй группы.
void partial_sort(It p, It middle, It q), void partial_sort(It p, It middle, It q, Pr pred) Переставляет элементы последовательности так, что элементы межу итераторами p и q располагаются в том порядке, как если бы последовательность была отсортирована, а элементы в оставшейся части - в произвольном порядке. То есть получаем часть отсортированной последовательности (не то же самое, что отсортированную часть).
merge(It p, It q, Itr i, Itr j, Iter out), merge(It p, It q, Itr i, Itr j, Iter out, Pr pred) Сортирует две последовательности слиянием.
Функторы и предикаты
Функторы и предикаты - это классы, объекты которых похожи на функцию (в них перегружен оператор () ). Например:
struct cmp{ bool operator ()(int a, int b) const { return a < b; // а можно, например, return a % 7 < b % 7 }}
Требование для предиката - оператор () должен возвращать значение типа bool. Требование для функтора - у оператора () тип возвращаемого значения должен быть отличным от bool.
struct sum2{ int operator ()(int a, int b) const { return (a + b) * (a + b); }}
Иногда удобно в предикате или функторе хранить некоторые данные. Например, предикат, который проверяет, больше ли нуля некоторое число:
bool operator ()(int a) const{ return a > 0;}
Но если понадобится сравнивать с произвольным числом, то стоит хранить это число внутри предиката.
bool operator ()(int a) const{ return a > k;}
Передавать число k через параметр не стоит, так как, например, может быть поставлено требование, чтобы сигнатура содержала только один параметр.
Предикаты с одним параметром называются унарными, с двумя - бинарными.
АЛЛОКАТОРЫ
#include <memory>#include <iostream>#include <string> int main(){ std::allocator<int> a1; // default allocator for ints int* a = a1.allocate(10); // space for 10 ints a[9] = 7; std::cout << a[9] << '\n'; a1.deallocate(a, 10); // default allocator for strings std::allocator<std::string> a2; // same, but obtained by rebinding from the type of a1 decltype(a1)::rebind<std::string>::other a2_1; // same, but obtained by rebinding from the type of a1 via allocator_traits std::allocator_traits<decltype(a1)>::rebind_alloc<std::string> a2_2; std::string* s = a2.allocate(2); // space for 2 strings a2.construct(s, "foo"); a2.construct(s + 1, "bar"); std::cout << s[0] << ' ' << s[1] << '\n'; a2.destroy(s); a2.destroy(s + 1); a2.deallocate(s, 2);}
Как именно управляет - это надо смотреть в реализации. Зачем это нужно: рассмотрим два случая: 1) вы редко создаёте объекты, и у них долгое время жизни. Тогда вы вполне можете позволить себе выделять память для каждого объекта отдельно. 2) вы часто создаёте и уничтожаете объекты. Тогда вам может быть невыгодно постоянно обращаться к системе за выделением/освобождением памяти - вы можете выделить сразу большую область памяти, и отводить части этой памяти для свежесозданных объектов. При уничтожении вы просто помечаете адрес памяти как неиспользуемый, и не возвращаете память системе до конца работы приложения. Тут можно поуправлять тем, как расширяется, как уплотняется эта область памяти (например, для увеличения вероятности попадания в кэш процессора).
C++ частичная специализация шаблонов функций есть!!!