About Teletype
Join
M
@mrnimda
August 1, 2019

C++ STL

Библиотека стандартных шаблонов (STL)

набор согласованных обобщённых алгоритмов, контейнеров, средств доступа к их содержимому и различных вспомогательных функций в C++.

Начнем рассмотрение с краткого обзора основных коллекций. Какой тип коллекции вы будете использовать, зависит от ваших задач, поэтому необходимо знать их внутреннее устройство для наиболее эффективного использования. Рассмотрим наиболее часто используемые типы коллекций.
• vector - коллекция элементов Т, сохраненных в массиве, увеличиваемом по мере необходимости. Для того, чтобы начать использование данной коллекции, включите #include <vector>.
• list - коллекция элементов Т, сохраненных, как двунаправленный связанный список. Для того, чтобы начать использование данной коллекции, включите #include <list>.
• map - это коллекция, сохраняющая пары значений pair<const Key, T>. Эта коллекция предназначена для быстрого поиска значения T по ключу const Key. В качестве ключа может быть использовано все, что угодно, например, строка или int но при этом необходимо помнить, что главной особенностью ключа является возможность применить к нему операцию сравнения. Быстрый поиск значения по ключу осуществляется благодаря тому, что пары хранятся в отсортированном виде. Эта коллекция имеет соответственно и недостаток - скорость вставки новой пары обратно пропорциональна количеству элементов, сохраненных в коллекции, поскольку просто добавить новое значение в конец коллекции не получится. Еще одна важная вещь, которую необходимо помнить при использовании данной коллекции - ключ должен быть уникальным. Для того, чтобы начать использование данной коллекции, включите #include <map>. Если вы хотите использовать данную коллекцию, чтобы избежать дубликатов, то вы избежите их только по ключу.
• set - это коллекция уникальных значений const Key - каждое из которых является также и ключом - то есть, проще говоря, это отсортированная коллекция, предназначенная для быстрого поиска необходимого значения. К ключу предъявляются те же требования, что и в случае ключа для map. Естественно, использовать ее для этой цели нет смысла, если вы хотите сохранить в ней простые типы данных, по меньшей мере вам необходимо определить свой класс, хранящий пару ключ - значение и определяющий операцию сравнения по ключу. Очень удобно использовать данную коллекцию, если вы хотите избежать повторного сохранения одного и того же значения. Для того, чтобы начать использование данной коллекции, включите #include <set>.
• multimap - это модифицированный map, в котором отсутствует требования уникальности ключа - то есть, если вы произведете поиск по ключу, то вам вернется не одно значение, а набор значений, сохраненных с данным ключом. Для того, чтобы начать использование данной коллекции включите #include <map>.
• multiset - то же самое относится и к этой коллекции, требования уникальности ключа в ней не существует, что приводит к возможности хранения дубликатов значений. Тем не менее, существует возможность быстрого нахождения значений по ключу в случае, если вы определили свой класс. Поскольку все значения в map и set хранятся в отсортированном виде, то получается, что в этих коллекциях мы можем очень быстро отыскать необходимое нам значение по ключу, но при этом операция вставки нового элемента T будет стоить нам несколько дороже, чем например в vector. Для того, чтобы начать использование данной коллекции, включите #include <set>.

STL Строки

Не существует серьезной библиотеки, которая бы не включала в себя свой класс для представления строк или даже несколько подобных классов. STL - строки поддерживают как формат ASCII, так и формат Unicode.
• string - представляет из себя коллекцию, хранящую символы char в формате ASCII. Для того, чтобы использовать данную коллекцию, вам необходимо включить #include <string>.
• wstring - это коллекция для хранения двухбайтных символов wchar_t, которые используются для представления всего набора символов в формате Unicode. Для того, чтобы использовать данную коллекцию, вам необходимо включить #include <xstring>.

Строковые потоки

Используются для организации сохранения простых типов данных в STL строки в стиле C++. 

//stl.cpp: Defines the entry point for the console application
#include <iostream>
#include <strstream>
#include <string>
using namespace std;

int main()
{
	strstream xstr;
	for (int i = 0; i < 10; i++)
	{
		xstr << "Demo " << i << endl;
	}
	cout << xstr.str();
	string str;
	str.assign(xstr.str(), xstr.pcount());
	cout << str.c_str();
	return 0;
}

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

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

Основные методы, которые присутствуют почти во всех STL коллекциях, приведены ниже.

• empty - определяет, является ли коллекция пустой.
• size - определяет размер коллекции.
• begin - возвращает прямой итератор, указывающий на начало коллекции.
• end - возвращает прямой итератор, указывающий на конец коллекции. При этом надо учесть, что реально он не указывает на ее последний элемент, а указывает на воображаемый несуществующий элемент, следующий за последним.
• rbegin - возвращает обратный итератор, указывающий на начало коллекции.
• rend - возвращает обратный итератор, указывающий на конец коллекции. При этом надо учесть, что реально он не указывает на ее последний элемент, а указывает на воображаемый несуществующий элемент, следующий за последним.
• clear - удаляет все элементы коллекции, при этом, если в вашей коллекции сохранены указатели, то вы должны не забыть удалить все элементы вручную посредством вызова delete для каждого указателя.
• erase - удаляет элемент или несколько элементов из коллекции.
• capacity - вместимость коллекции определяет реальный размер - то есть размер буфера коллекции, а не то, сколько в нем хранится элементов. Когда вы создаете коллекцию, то выделяется некоторое количество памяти. Как только размер буфера оказывается меньшим, чем размер, необходимый для хранения всех элементов коллекции, происходит выделение памяти для нового буфера, а все элементы старого копируются в новый буфер. При этом размер нового буфера будет в два раза большим, чем размер буфера, выделенного перед этим - такая стратегия позволяет уменьшить количество операций перераспределения памяти, но при этом очень расточительно расходуется память. Причем в некоторых реализациях STL первое выделение памяти происходит не в конструкторе, а как ни странно, при добавлении первого элемента коллекции. Фрагмент программы ниже демонстрирует, что размер и вместимость коллекции - две разные сущности:

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> vec;
	cout << "Real size of array in vector: " << vec.capacity()
		<< endl;
	for (int j = 0; j < 10; j++)
	{
		vec.push_back(10);
	}
	cout << "Real size of array in vector: " << vec.capacity()
		<< endl;
	return 0;
}

Vector

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

У вектора есть оператор operator [], который позволяет нам пользоваться вектором так же, как обычным массивом. Этот оператор используется также в map, deque, string и wstring.

#include <vector>

size - возвращает число элементов в векторе.

at - анологичен [ ], помогает получать доступ к какому-либо элементу вектора под каким-либо индексом. Так же проверяет границы массива в отличие от [ ] at работает медленнее.

clear - очищает vector от всех элементов.

pop_back - удаляет последний элемент.

push_back - добавляет элемент в конец.

capacity - возвращает целочисленную переменную, определяет ёмкость вектора(размер буфера).

reserve - указывает сколько элементов должно быть в запасе у вектора(размер capacity).

shrink_to_fit - уменьшает кол-во используемой памяти за счёт освобождения неиспользованной.

empty - проверка есть ли элементы в векторе.

resize - изменяет размер вектора на заданную величину.

insert - отвечает за вставку элементов в вектор.

erase - удаляет элемент вектора.

swap - обменять содержимое двух векторов.

begin - возвращает итератор на первый элемент вектора.

Итераторы

Итератор - это абстракция, которая ведет себя, как указатель с некоторыми ограничениями или без них, то есть, сохраняет все свойства своего прародителя. Указатель - это тоже итератор. В действительности, итераторы, в большинстве случаев, это объектные обертки указателей. Вот как примерно может выглядеть внутреннее устройство итератора:

class Iterator
{
T* pointer;
public:
T* GetPointer ()
{
return this - >pointer;
}
void SetPointer (T* pointer)
{
this - >pointer = pointer;
}
:
};

Но итератор представляет собой более высокий уровень абстракции, чем указатель, поэтому утверждение, что итератор - это указатель в некоторых случаях может быть неверно. А вот обратное будет верно всегда. Вот несколько формализованных определений для итератора:

Итераторы обеспечивают доступ к элементам в коллекции
Итераторы для конкретного класса коллекции определяются внутри класса этой коллекции. В STL существует три типа итераторов: iterator, reverse_iterator, и random access iterator. Для обхода коллекции от меньшего индекса к большему, используются обычные или forward итераторы. Для обхода коллекции в обратном направлении используются reverse итераторы. Random access iterator являются итераторами, которые могут обходить коллекцию как вперед, так и назад. Ниже приведен пример использования итераторов для удаления половины элементов вектора:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void printInt(int number);
int main()
{
	vector<int> myVec;
	vector<int>::iterator first, last;
	for (long i = 0; i<10; i++)
	{
		myVec.push_back(i);
	}
	first = myVec.begin();
	last = myVec.begin() + 5;
	if (last >= myVec.end())
	{
		return -1;
	}
	myVec.erase(first, last);
	for_each(myVec.begin(), myVec.end(), printInt);
	return 0;
}
void printInt(int number)
{
	cout << number << endl;
}

Важно помнить, что когда вы получаете итератор к коллекции, а после этого модифицируете коллекцию, то этот итератор становится уже непригодным к использованию. Естественно, не все изменения приводят к непригодности итератора для дальнейшего использования, а только изменения структуры коллекции. В случае же, если вы просто измените значения, сохраненные в коллекции, то ничего страшного не произойдет и итератор не испортится.

Это сущности которые нужны для взаимодействия с элементами, которые представлены в различных контейнерах stl.

vector<тип>::iterator имя;

Чтобы вывести значение и любую работу со значением итератора на консоль, нужно применить метод разименования *имя.

advance(имя_итератора, шаг) -> Если не поддерживается *(имя_итератора + шаг)

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

В контексте STL термин выходной означает, что итератор используется для передачи информации из программы в контейнер. Выходной итератор аналогичен входному за исключением того, что его разыменование гарантированно предоставляет программе возможность изменять значение контейнера, но не читать его.

Контейнеры

Контейнер — это объект, который хранит в себе другие объекты одного типа.
Хранимые объекты могут быть объектами 1в смысле объектно ориентированного программирования либо значениями встроенных типов. Данные, сохраненные в контейнере, принадлежат ему. Это означает, что когда время существования контейнера истекает, это же происходит с сохраненными в нем данными.

Ассоциативный контейнер — еще одно уточнение концепции контейнеров.
Ассоциативный контейнер связывает значение с ключом, который служит для отыскания значения.

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

Функциональные объекты (функторы)

Функтор — это любой объект, который может использоваться с
операцией () в манере, подобной функции.

Концепции функторов

  • генератор —это функтор, который может быть вызван без аргументов;
  • унарная функция — функтор, который может быть вызван с одним аргументом;
  • бинарная функция — функтор, который может быть вызван с двумя аргументами.
  • унарная функция, которая возвращает булевское значение, представляет собой предикат.
  • бинарная функция, которая возвращает булевское значение, представляет собой бинарный предикат.

Алгоритмы

STL - алгоритмы представляют набор готовых функций, которые могут быть применены к STL коллекциям и могут быть подразделены на три основных группы:

Функции для перебора всех членов коллекции и выполнения определенных действий над каждым из них:

count, count_if, find, find_if, adjacent_find, for_each, mismatch, equal, search copy, 
copy_backward, swap, iter_swap, swap_ranges, fill, fill_n, generate, generate_n, 
replace, replace_if, transform, remove, remove_if, remove_copy, remove_copy_if, unique, 
unique_copy, reverse, reverse_copy, rotate, rotate_copy, random_shuffle, partition, 
stable_partition

Функции для сортировки членов коллекции:

Sort, stable_sort, partial_sort, partial_sort_copy, nth_element, binary_search, 
lower_bound, upper_bound, equal_range, merge, inplace_merge, includes, set_union, 
set_intersection, set_difference, set_symmetric_difference, make_heap, push_heap, 
pop_heap, sort_heap, min, max, min_element, max_element, lexographical_compare, 
next_permutation, prev_permutation

Функции для выполнения определенных арифметических действий над членами коллекции:

Accumulate, inner_product, partial_sum, adjacent_difference

Группы алгоритмов

  • немодифицирующие последовательные операции;
  • модифицирующие последовательные операции;
  • сортирующие и связанные с ними операции;
  • обобщенные числовые операции.

Немодифицирующие последовательные операции обрабатывают каждый элемент в диапазоне. Эти операции оставляют контейнер без изменений. Например, find () и for_each () относятся к этой категории.

Модифицирующие последовательные операции также обрабатывают каждый
элемент в контейнере. Однако, как следует из их названия, они могут изменить
содержимое контейнера. Изменения могут касаться значений либо порядка, в котором они сохранены. Функции transform (), random_shuf f le () и copy () относятся к этой категории.

Сортирующие и связанные с ними операции включают некоторые сортирующие
функции (в том числе sort ()), а также ряд других функций, включая операции с
наборами (множествами).

Числовые операции включают функции для суммирования содержимого
диапазона, вычисления внутреннего произведения двух контейнеров, подсчета частичных сумм и вычисления разностей соседних элементов.

Сравнение функций и методов контейнеров

Иногда возникает ситуация, когда требуется произвести выбор между
использованием метода STL либо функции STL. Обычно лучшим вариантом является метод. Во-первых, он должен быть лучше оптимизирован для конкретного контейнера. Во-вторых, будучи функцией-членом, он может пользоваться средствами управления памятью класса шаблона и при необходимости изменять размер контейнера.

Предикаты

Для многих алгоритмов STL необходимо задать условие, посредством которого алгоритм определяет, что ему необходимо делать с тем или иным членом коллекции. По определению, предикат - это функция, принимающая один или более параметров и возвращающая значения истина или ложь. Предикат может быть функцией или функтором. Существует также набор стандартных предикатов.

std::function

Вызывается #include<functional>

Альтернатива указателям на функции.

void Foo { }

int main
{
    std::function<void()>f;
    f = Foo;
    f();
}

std::pair

Является шаблоном структуры, который предоставляет возможность хранить два разнородных объекта, как единое целое.

std::pair<std::string, std::string>
Aha
August 1, 2019, 07:31
0 reactions
0 views