Си++/Стандартная библиотека

Стандартная библиотека

STL

Общие сведения

Контейнеры. Итераторы. Функторы. Предикаты.

Контейнеры — это template-шаблоны классов, поддерживающих стандартные системы организации данных, таких как массив, односвязный и двусвязный списки и т.п. По сути это оболочка над контейнером, для которого перегружены операторы: ++, *, -- и может быть другие.

Соответственно итератор — это класс, предназначенный для перебора элементов контейнера.

Функторы и предикаты используются в библиотеке алгоритмов STL

Функтор — объект класса в котором перегружен оператор (). Количество аргументов определяется задачей, для которой нужен функтор.

Предикат — функция, возвращающая bool, также это может быть функтор оператор () которого возвращает bool. Унарный предикат — предикат принимающий 1 аргумент, к примеру !a. Бинарный предикат — предикат, принимающий 2 аргумента, примеры: a>b, a<b и др.

Контейнеры

Виды. Последовательные и ассоциативные. Адаптеры (??!, что это?).

• vector. Обертка вокруг массива, выделяемого по new. Поддерживает проверку границы (если использовать v.at(i), а не v[i]), а также автоматическую реаллокацию при добавлении в хвост и вставке/удалении в середину.

Очень быстрый operator[], линейный по времени (из-за умной реаллокации) push_back(), но медленная вставка в середину, кроме того, любая вставка инвалидует все итераторы (STL, построенная в отладочном режиме, сама отлавливает ошибки использования инвалидованных итераторов). Совместим с массивом языка Си — std::vector::operator T* вернет указатель на массив Си, который можно передавать, например, в вызовы операционной системы.

Саттер и Александреску в своей книге пишут: «если вы не уверены, какой именно контейнер вам нужен — смело используйте vector».

• deque. Двунаправленная очередь, реализованная как коллекция страниц стандартного размера.

Очень быстрая вставка/удаление и с головы, и с хвоста, кроме того, эти операции не инвалидуют итераторы. operator[] чуть медленнее, чем у vector, но тем не менее использование deque «только с хвоста» (семантика аналогична vector, класс называется stack) оправдано и имеет свои особенности — operator[] медленнее, зато не инвалидуются итераторы (кроме вставки/удаления в середину) и куда лучше общий паттерн аллокации и фрагментации памяти (важно при большом количестве объектов).

• queue. deque, используемая в режиме «добавление только в голову, удаления только с хвоста».

• list. Список.

Не имеет operator[], и его итераторы не являются random-access. Паттерн аллокации памяти — по блочку на объект. Преимущества: не инвалидует итераторы никогда, и очень быстрые вставки/удаление в середину.

• set

Красно-черное дерево из объектов с операцией поиска по ключу, и тип ключа, и тип объекта — типовые параметры. Хранится в отсортированном виде, алгоритм sort для него ничего не делает.

• map

set из пар объектов, ключ — тип первого объекта. Ассоциативный массив (как в Perl), у которого в квадратных скобках может стоять любой тип, а не только целое число.

Аллокаторы

Все контейнеры STL используют т.н. аллокаторы для размещения объектов в памяти. Аллокатор можно указать как типовой параметр, по умолчанию используется std::allocator.

Аллокатор делает следующее:

• определяет (как AlType::pointer) класс «обобщенного указателя» на объект. Этот указатель

должен иметь все операции, определенные для указателя языка Си, а также operator T* (возвращает указатель Си) и operator * (возвращает ссылку). Для операций должны поддерживаться гарантии языка Си (типа *(a + i) тождественно a[i] и так далее). Как именно реализован этот указатель — личное дело аллокатора.

• определяет методы allocate() — выделяет блочок памяти для хранения N объектов типа T,

возвращает обобщенный указатель на его начало, с гарантией, что прибавления к этому указателю дадут указатели на последующие объекты, free() — undo для allocate(), construct() — создает объект по адресу, на который ссылается обобщенный указатель, и free() — undo для construct().

• std::allocator::pointer есть обычный указатель языка Си, методы реализованы примерно так:

pointer std::allocator::allocate(size_t N)
{
  return (pointer)new char( N * sizeof(T) );
}
void std::allocator::free(pointer p)
{
  delete p;
}
void std::allocator::construct(pointer p)
{
  (void)new(p)T(); // placement new
}
void std::allocator::construct(pointer p, T& o)
{
  (void)new(p)T(o); // placement new
}
void std::allocator::destroy(pointer p)
{
  p->~T();
}

• возможно писать свои реализации аллокаторов, при этом с ними будут работать все контейнеры, и общий внутренний код контейнеров, ответственный за "раздвижение" контейнера при вставке в середину и т.д.

Итераторы

Обобщение указателя. Классы итераторов.

Позволяют писать код для работы с контейнером (например, алгоритмы STL — см. ниже), не зависящий от типа контейнера.

В любом контейнере объявлен (через typedef) тип его итератора — Cont::iterator

У любого контейнера есть метод Cont::iterator begin(), возвращающий итератор на первый (в порядке обхода) элемент.

У любого итератора перегружена операция ++, означает шаг на следующий элемент.

У любого контейнера есть метод end(), возвращающий лже-итератор (не ссылается на валидную память!), который есть результат ++ над итератором, ссылающимся на последний (в порядке обхода) элемент.

Итераторы можно сравнивать на равенство.

У итератора есть operator T*, возвращает указатель на объект, на который ссылается итератор, и operator *, который преобразует итератор к ссылке на этот же объект.

Правильный код для обхода контейнера:

c.iterator itBegin = c.begin();
c.iterator itEnd = c.end();
for( c.iterator it = itBegin; it != itEnd; ++it )
{
 // на каждом шаге *it есть следующий объект внутри c
}

Заметим, что это позволяет писать код, работающий с диапазонами итераторов, а не с контейнерами как таковыми, что повышает легкость замены в программе одного итератора на другой — vector на list и т.д.

Алгоритмы STL (см. ниже) реализованы именно так.

После внесения изменений в контейнер некоторые (или все) итераторы на него могут прийти в невалидное состояние. Какие именно - зависит от типа контейнера и типа изменения (в хвост/голову/середину). Обращение к инвалидованному итератору есть грубая ошибка, в релизной версии обычно вызывающая крах программы. Отладочные версии STL умеют проверять на такие ошибки.

Итераторы бывают однонаправленные, двунаправленные (есть operator--), и с произвольным доступом (есть [] и прибавления/вычитания целых чисел, семантика строго как у указателя Си). Каков данный итератор в этом смысле - зависит от контейнера, vector и deque имеют итераторы с произвольным доступом, а list — нет.

Алгоритмы

Алгоритмы над контейнерами позволяют, независимо от типа контейнера, работать с его данными с помощью итератора контейнера. Ниже приведены некоторые примеры из библиотеки алгоритмов STL, для её подключения нужно указать #include <algorithm>. Каждый алгоритм в это библиотеке описывает целевую задачу и поэтому очень мал, поэтому советую не лениться и смотреть определение неизвестных классов и функций.

for_each

Код этой функции очень прост (хотя и по началу непонятен, т.к. записан в библиотеке ужасным образом в плане эстетизма записи кода):

namespace std {
template<class _II, class _Fn> inline 
_Fn for_each(_II _F, _II _L, _Fn _Op)
{
  for (; _F != _L; ++_F)
  _Op(*_F);
  return (_Op); 
}
} // end namespace std

рассмотрим аргументы:

_F — итератор на элемент контейнера, с которого нужно начинать

_L — итератор на элемент контейнера, которым нужно заканчивать

_Op — функция от одного аргумента или функтор, у которого перегружена операция () для одного аргумента. Тип аргумента должен соответствовать типу данных, содержащихся в контейнере.

Как видим, функция for_each всего-то-навсего для каждого элемента в контейнере вызывает функцию или оператор функтора. Также видно, что возвращаемое значение не играет роли. И все. Пример использования:

//наш функтор
class FunctorToAdd
{
public:
  void operator()(int& zn)
  {
  //что-то делаем с аргументом
  ++zn;
  }
};
 
void main()
{
  vector<int> mass;
  mass.push_back(1);
  mass.push_back(2);
  mass.push_back(3);

  //заметим, что мы создаем объект класса FunctorToAdd с помощью возвращающего конструктора
  std::for_each(mass.begin(),mass.end(),FunctorToAdd());

  cout<<mass[0]<<endl;
  cout<<mass[1]<<endl;
  cout<<mass[2]<<endl;
}

В данной задаче (увеличение каждого элемента на 1) можно обойтись и простой функцией:

void FuncToAdd(int& zn)
{
  ++zn;
}
 
std::for_each(mass.begin(),mass.end(),FuncToAdd);

но в более сложных задачах может пригодится объект.

transform

Тут проще посмотреть на определение:

namespace std {
template<class _II, class _OI, class _Uop> inline
_OI transform(_II _F, _II _L, _OI _X, _Uop _U)
{
  for (; _F != _L; ++_F, ++_X)
  *_X = _U(*_F);
  return (_X); 
}
} // end namespace std

transform помещает в новый контейнер (_X — итератор на его начало) значения, которые вернет наша функция (_U) или функтор от аргумента из исходного контейнера. Если указать источник равный приемнику, то будут соответственно изменены значения исходного контейнера. Пример использования:

//нужно создать другую функцию, т.к. в transform используется возвращаемое значение
int FuncToAdd2(int zn)
{
  return ++zn;
}

list<int> mass2;
std::transform(mass.begin(),mass.end(), back_inserter( mass2 ), FuncToAdd2 );

back_inserter — функция, которая возвращает объект (back_insert_iterator), который в свою очередь определяет оператор * (возвращает *this) и оператор = , в котором вызывает push_back для нашего контейнера mass2. Понятно в чем фишка? Это как раз нам и нужно, т.к. mass2 у нас пуст, а в функции transfrom как раз выполняется присваивание.

count_if

Подсчитывает количество элементов в указанном диапазоне контейнера, для которых выполняется унарный предикат (третий аргумент). К примеру, если у нас массив mass2=[0,1,2,3,4], то:

bool Count(int z)
{
  return z>2;
}
 
//вернет 2
cout<< count_if(mass2.begin(),mass2.end(),Count) <<endl;

Ниже будет показан пример как этого же результата можно добится используя адаптеры вместо функции.

partition

Переставляет элементы контейнера так, что сначала идут элементы, меньшие, чем данный, а потом - большие.

Линейное время исполнения. Не выделяет дополнительную память. (уточнить требования к bidir и random у итераторов! кажется, обязателен BidIt).

stable_partition

То же, что partition, но с гарантией, что не будут меняться местами элементы, «равные» друг другу.

Выделяет временную дополнительную память для всего множества.

nth_element

«Недосортировка». Переставляет элементы так, что в позиции N окажется тот элемент, который оказался бы там при полной сортировке. При этом не дается никаких гарантий на остальные элементы (уточнить! кажется, предыдущие гарантированно все меньше, а последующие — все больше).

«Половина» qsort с рекурсией только по одной половинке, а не по обеим.

Не нужна дополнительная память (хвостовая рекурсия заменена циклом, даже стек не потребляется). Время исполнения линейное.

partial_sort

Находит N наименьших элементов, и располагает их в порядке возрастания в начале контейнера. Никаких гарантий на остальные элементы.

«Половина» от heap sort.

partial_sort всего контейнера есть полный heap sort.

Время N * log N (без деградации на неудачных данных), память не нужна.

sort

В зависимости от параметра «порог» — либо qsort (по умолчанию), либо heap sort, либо сначала quick или heap, а затем insertion sort для мелких отрезков.

Требования по памяти и времени — см. классические описания алгоритмов.

stable_sort

То же, что sort, но гарантирует не-перестановку равных элементов.

Merge sort. Память нужна сразу и на все сортируемое множество, о времени выполнения — см. классическо описание алгоритма (обычно медленнее qsort, но не деградирует на неудачных входных данных).

Адаптеры

Для работы нам потребуется добавить #include <functional>

В примере, где мы показывали работу с count_if не очень-то удобно создавать функцию (отвлекает как никак )). Поэтому рассмотрим следующий код, выполняющий ту же самую работу:

 cout<< count_if(mass2.begin(),mass2.end(), bind2nd(greater<int>(),2)) <<endl;

Страшно? Ну ничего, сейчас всё объясню. greater — класс в котором перегружен оператор (), в котором происходит сравнение 2-х аргументов (т.е. return (_X > _Y)). Т.е. это настоящий бинарный предикат. А теперь давайте представим, как было бы хорошо, если бы на место первого аргумента (_X) подставлялся элемент из массива, а во второй какое-нибудь заданное нами число (2). bind2nd как раз это и делает. При его конструировании мы указываем бинарный предикат и значение, которое сохраняется и подставляется в greater<int>::operator() при вызове bind2nd::operator(). Тем самым мы превращаем наш бинарный предикат в унарный. Что и требуется для функции count_if.

Для тех кто не понял bind2nd и есть адаптер. Существует также bind1st, который заменяет не второй аргумент, а первый. Поэкспериментируйте.

Библиотека ввода-вывода

Потоки вывода

Вывод пользовательских типов.

Потоки ввода

Ввод пользовательских типов.