OpenSCADAWiki: Roman Savochenko/C Short All/part2/part8 ...

Home | Index | Changes | Comments | Users | Registration | Login  Password:  
 

2.8 Стандартная библиотека шаблонов (STL)

STL представляет собой большую библиотеку шаблонов включающую в себя три ключевых компонента: контейнеры, итераторы, алгоритмы. Кроме того, STL является расширяемой библиотекой. STL избегает операторов new и delete и использует распределители памяти(allocators) для выделения и высвобождения памяти. Существует возможность создавать пользовательские распределители памяти. Типы исключений в STL:

2.8.1 Контейнеры

Контейнеры делятся на три основных категории: контейнеры последовательностей, ассоциативные контейнеры и адаптеры контейнеров. Контейнеры последовательностей (sequence containers) и Ассоциативные контейнеры имеют общее название – контейнеры первого класса (first-class containers). Существует ещё четыре типа контейнеров, которые считаются «почти контейнерами» («near-containers») – С-подобные массивы, string, bitset и valarray.


Контейнерные заголовочные файлы стандартной библиотеки:

Общие имена типа typedef имеющиеся в контейнерах первого класса:


Таблица 11. Контейнерные классы STL
Имя
Назначение
Тип итератора
Контейнеры последовательностей
vectorБыстрые вставки и удаление в конец контейнера, прямой доступ к любому элементу.произв. доступ
dequeБыстрые вставки и удаления в начало и конец контейнера, прямой доступ к любому элементу.произв. доступ
listДвухсвязный список, быстрая вставка и удаление элементов везде.двунапр.
Ассоциативные контейнеры
setБыстрый поиск, дубликаты (одинаковые ключи)не допускаются.двунапр.
multisetБыстрый поиск, допускаются дубликаты.двунапр.
mapВзаимно однозначное соответствие, дубликаты не допускаются, быстрый поиск значения по ключу.двунапр.
multimapСоответствие «один ко многим», дублирование ключей допускается, быстрый поиск значения по ключу.двунапр.
Адаптеры контейнеров
stack«Последним пришел, первым вышел» (LIFO)не поддерж.
queue«Первым пришел, первым вышел» (FIFO)не поддерж.
priority_ queueЭлемент с наивысшим приоритетом всегда достигает выхода из очереди первым.не поддерж.

Таблица 12. Общие для всех STL-контейнеров функции
Имя
Назначение
default constructorКонструктор для обеспечения инициализации по умолчанию.
copy constructorКонструктор, который инициализирует контейнер в качестве копии существующего контейнера.
destructorДеструктор контейнера.
emptyПроверка контейнера на пустоту.
max_sizeВозвращает максимальное число элементов в контейнере.
sizeВозвращает число элементов в контейнере.
=Присваивает один контейнер другому.
<, <=, >, >=, ==, !=Сравнивает два контейнера.
swapПоменять местами элементы двух контейнеров.
Только в контейнерах первого класса
beginВозвращает iterator, либо const_iterator который ссылается на первый элемент контейнера.
endВозвращает iterator, либо const_iterator который ссылается на последний элемент контейнера.
rbeginВозвращает reverse_iterator, либо const_reverse_iterator который ссылается на последний элемент контейнера.
rendВозвращает reverse_iterator, либо const_reverse_iterator который ссылается на позицию перед первым элементом контейнера.
eraseУдаляет один или несколько элементов из контейнера.
clearУдаляет все элементы из контейнера.

Контейнеры последовательностей

Классы vector и deque реализованы на базе массивов. Класс list реализует связанный список. Дополнительные операции характерные для контейнеров последовательностей:


front
front();
Возвращает ссылку на первый элемент в контейнере.


back
back();
Возвращает ссылку на последний элемент в контейнере.


push_back
push_back();
Вставляет новый элемент в конец контейнера.


pop_back
pop_back();
Выталкивает последний элемент контейнера.


Контейнер vector обеспечивает структуру данных непрерывной областью памяти. Это позволяет обеспечивает эффективный прямой доступ к любому элементу контейнера vector посредством операции индексирования []. Все алгоритмы STL могут работать с контейнером vector. Итераторы для vector обычно реализуются как указатели на элементы контейнера vector.

std::vector<int> v;
v.push_back(2);
cout << "\nРазмер вектора v: " << v.size();

std::vector<int>::const_iterator p1;
for(p1 = v.begin(); p1 != v.end(); p1++) cout << *p1 << ' ';
std::vector<int>::reverse_iterator p2;
for(p2 = v.rbegin(); p2 != v.rend(); ++p2) cout << *p2 << ' ';

int a[ 6 ] = { 1, 2, 3, 4, 5, 6 };
std::vector<int> v1(a, a+6);
std::ostream_iterator<int> output(cout," ");
std::copy(v1.begin(), v1.end(), out); //печать вектора
try
{
  v1.at(100) = 777;   //доступ вне массива
}
catch(std::out_of_range e)
{ cout << "\nИсключение" << e.what(); }
v1.erase(v.begin());


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


inplace_merge
void inplace_merge(_BidirectionalIter first, _BidirectionalIter middle, _BidirectionalIter last, _Compare comp);
Объединяет две возростающие последовательности в одном и том же контейнере.


splice
splice();
Вырезает элементы из одного контейнера и помещает их в другой.


push_front
push_front();
Вставить элемент в начало контейнера.


pop_front
pop_front();
Вытолкнуть элемент с начала контейнера.


remove
remove();
Удалить элемент из начала контейнера.


merge
_OutputIter merge(_InputIter1 first1, _InputIter1 last1, _InputIter2 first2, _InputIter2 last2, _OutputIter result)
Объединяет две возростающие последовательности в одну.


sort
void sort(_RandomAccessIter first, _RandomAccessIter last);
Сортировка элементов в возрастающем порядке.


std::list<int> Values, otherValues;
Values.push_front(1);
Values.push_back(2);
values.sort();


Контейнер deque объединяет многие возможности классов vector и list. Реализуется на основе очереди с двумя концами и обеспечивает эффективный индексный доступ с эффективной операцией вставки в начало и конец контейнера. Класс deque обеспечивает поддержку итераторов произвольного доступа. Наиболее часто deque используется в качестве очереди FIFO.


std::deque<double> values;
std::ostream_iterator<double> output(cout," ");
values.push_front(2.2);
values.push_back(1.1);
for(int i=0; i < values.size(); ++i)
  cout << values[i] << ' ';
values.pop_front();
values[1]=5.4;

Ассоциативные контейнеры

Ассоциативные контейнеры STL предназначены для обеспечения прямого доступа с целью сохранения и выборки элементов с помощью ключей (ключи поиска). Имеется четыре ассоциативных контейнера: multiset, set, multimap, map. В каждом контейнере ключи сохраняются упорядоченными. Ассоциативные контейнеры поддерживают дополнительные функции:


equal_range
pair<_ForwardIter, _ForwardIter> equal_range(_ForwardIter first, _ForwardIter last, const _Tp& val);
Возвращает пару прямых итераторов, содержащих результаты lower_bound и upper_bound.


find
find();
Поиск ключа.


lower_bound
_ForwardIter __lower_bound(_ForwardIter first, _ForwardIter last, const _Tp& val, _Distance*)
Определения позиции первого вхождения указанного ключа.


upper_bound
_ForwardIter upper_bound(_ForwardIter first, _ForwardIter last, const _Tp& val)
Определения позиции за последним вхождением указанного ключа.


count
count();
Возвращает количество указанных ключей в контейнере.


Контейнеры multiset и set используются для быстрого сохранение и выборки ключей. Контейнер multiset допускает использование одинаковых ключей. Упорядочение элементов определяется компараторным объектом-функцией. Контейнеры поддерживает двунаправленные итераторы (но не итераторы произвольного доступа).


int a[10] = {7,22,9,1,18,30,100,22,85,13};
typedef std::multiset<int, std::<int> > ims;
ims intMultiset;
std::ostream_iterator<int> output(cout, " ");
intMultiset.insert(15);
result=intMultiset.find(20);
if ( result != intMultiset.end() ) cout << "Найдено значение";
intMultiset.insert(a, a+10);
std::copy(intMultiset.begin(),intMultiset.end(), output);


Контейнеры multimap и map используются для быстрого сохранения и нахождения ключей и ассоциированных значений (пара ключ/значение). При вставке в эти контейнеры используется объект pair. Контейнер multimap позволяет ассоциировать несколько значений с одним ключем. Упорядочение элементов определяется компараторным объектом-функцией. Контейнеры поддерживает двунаправленные итераторы (но не итераторы произвольного доступа).


typedef std::multimap<int, double, std::less<int> > mmid;
mmid pairs;
pairs.insert(mmid::value_type(15, 2.7) );
for(mmid::const_iterator iter = pairs.begin();
    iter != pairs.end(); ++iter)
  cout << iter->first << '\t' << iter->second << '\n';
pairs[25]=45.65;


Адаптеры контейнеров

STL предоставляет три адаптера контейнера – stack, queue, priority_queue. Адаптеры не являются контейнерами первого класса, поскольку они не предоставляют реализации фактической структуры данных в которой могут сохраняться элементы, и поскольку адаптеры не поддерживают итераторы. Все три класса адаптеров предоставляют функции-члены push и pop, которые реализуют соответствующий метод вставки элемента.


Адаптер stack обеспечивает структуру LIFO и может быть реализован с любым из контейнеров последовательности. Адаптер queue обеспечивает структуру FIFO и может быть реализован с контейнерами list и deque. Адаптер priority_queue обеспечивает очередь в которой наиболее приоритетное значение всегда будет удаляться первым. priority_queue может быть реализован с контейнерами vector и deque. Сравнение элементов выполняется с помощью функции-объекта less<T>.


std::stack<int> intDequeStack;
std::stack<int, std::vector<int> > intVectorStack;
std::stack<int, std::list<int> > intListStack;

intDequeStack.push(23);
intVectorStack.push(23);
intListStack.push(34);


2.8.2 Итераторы

Итераторы схожи с указателями и используются для указания на элементы контейнеров первого класса. STL контейнеры первого класса предоставляют функции-члены begin() и end(), которые возвращают итератор указывающий соответственно на первый и последний элемент контейнера. Если итератор i указывает на определённый элемент, то ++i указывает на «следующий» элемент, а *i ссылается на элемент, на который указывает i. Итератор, полученый из функции end(), может использоваться в сравнении на равенство и неравенство для определения окончания «движущегося итератора». Для ссылки на элемент контейнера используется объект типа iterator или const_iterator.


Таблица 13. Операции с итераторами для каждого типа итератора
Имя
Назначение
Все итераторы
++pПреинкримент итератора
p++Постинкримент итератора
Итераторы ввода
*pРазыменование итератора
p=p1Присвоение итератора итератору
p==p1Сравнение итераторов на равенство
p!=p1Сравнение итераторов на неравенство
Итераторы вывода
*pРазыменование итератора
p=p1Присвоение итератора итератору
Однонаправленные итераторы
*Обеспечивают все функциональные возможности итераторов ввода и вывода
Двунаправленные итераторы
-pПредекремент итератора
p-Постдекремент итератора
Итераторы с произвольным доступом
p+=iИнкремент итератора p на i позиций
p-=iДекремент итератора p на i позиций
p+iИтератор помещается на позицию p+i
p-iИтератор помещается на позицию p-i
p[i]Возвращение ссылку на элемент, смещённый от p на i позиций
p<p1, p<=p1, p>p1, p>=p1Сравнение итераторов

Категории итераторов:


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

2.8.3 Алгоритмы

Контейнеры инкапсулируют некоторые базовые операции, но STL-алгоритмы реализуются независимо от контейнеров. Алгоритмы оперируют элементами контейнеров только с помощью итераторов. Можно создавать собственные алгоритмы.

Алгоритмы, модифицирующие последовательности

copy
copy();
Копирование.


copy_backward
_BidirectionalIter2 __copy_backward(_BidirectionalIter1 first, _BidirectionalIter1 last, _BidirectionalIter2 result, bidirectional_iterator_tag, _Distance*)
Обратное копирование части одного контейнера в другой контейнер.


fill
void fill(_ForwardIter first, _ForwardIter last, const _Tp& value);
Заполняет все элементы контейнера значением <value>.


fill_n
_OutputIter fill_n(_OutputIter first, _Size n, const _Tp& value);
Заполняет указанные элементы контейнера значением <value>.


generate
void generate(_ForwardIter first, _ForwardIter last, _Generator gen)
Заполняет все элементы контейнера значением возвращаемым функцией <gen>.


generate_n
generate_n();
Заполняет указанные элементы контейнера значением возвращаемым функцией <gen>.


iter_swap
void iter_swap(_ForwardIter1 a, _ForwardIter2 b);
Перестановка значений контейнера (по ссылке).


includes
bool includes(_InputIter1 first1, _InputIter1 last1, _InputIter2 first2, _InputIter2 last2);
Проверяет находятся ли элементы второго множества в первом.


next_permutation
bool next_permutation(_BidirectionalIter first, _BidirectionalIter last);
Следующая перестановка в лексикографическом порядке.


prev_permutation
bool prev_permutation(_BidirectionalIter first, _BidirectionalIter last);
Предыдущая перестановка в лексикографическом порядке.


partition
_ForwardIter partition(_ForwardIter first, _ForwardIter last, _Predicate pred);
Разделение диапазонов элементов.


remove
_ForwardIter remove(_ForwardIter first, _ForwardIter last, const _Tp& value);
Удаление из указанного участка контейнера всех указанных объектов <value>


remove_copy
_OutputIter remove_copy(_InputIter first, _InputIter last, _OutputIter result, const _Tp& value);
Перенос из указанного участка контейнера в другой контейнер всех указанных объектов <value>.


remove_copy_if
remove_copy_if();
Перенос из указанного участка контейнера в другой контейнер объектов выбранных функцией сравнения <pred>.


remove_if
_ForwardIter remove_if(_ForwardIter first, _ForwardIter last, _Predicate pred);
Удаление из указанного участка контейнера объектов выбранных функцией сравнения <pred>


replace
void replace(_ForwardIter first, _ForwardIter last, const _Tp& old_value, const _Tp& new_value);
Производит замену объекта <old_value> на <new_value> по указанному участку контейнера.


replace_copy
_OutputIter replace_copy(_InputIter first, _InputIter last, _OutputIter result, const _Tp& old_value, const _Tp& new_value);
Производит замену объекта <old_value> на <new_value> по указанному участку контейнера и помещений старых значений в контейнер <result>.


replace_copy_if
_OutputIter replace_copy_if(Iterator first, Iterator last, _OutputIter result, _Predicate pred, const _Tp& new_value);
Производит замену объекта выбраного функцией <pred> на <new_value> по указанному участку контейнера и помещений старых значений в контейнер <result>.


replace_if
void replace_if(_ForwardIter __first, _ForwardIter last, _Predicate pred, const _Tp& new_value);
Производит замену объекта выбраного функцией <pred> на <new_value> по указанному участку контейнера.


reverse
void reverse(_BidirectionalIter first, _BidirectionalIter last, bidirectional_iterator_tag);
Инвертирование последовательности указанных элементов контейнера./


reverse_copy
_OutputIter reverse_copy(_BidirectionalIter first, _BidirectionalIter last, _OutputIter result);
Копирует указанные элементы в обратном порядке.


rotate
_ForwardIter rotate(_ForwardIter first, _ForwardIter middle, _ForwardIter last);
Ротация элементов.


rotate_copy
_OutputIter rotate_copy(_ForwardIter first, _ForwardIter middle, _ForwardIter last, _OutputIter result);
Ротация элементов с копированием.


set_difference
_OutputIter set_difference(_InputIter1 first1, _InputIter1 last1, _InputIter2 first2, _InputIter2 last2, _OutputIter result);
Определение элементов из первого множества отсутствующих во втором.


set_intersection
_OutputIter set_intersection(_InputIter1 first1, _InputIter1 last1, _InputIter2 first2, _InputIter2 last2, _OutputIter result);
Определение элементов из первого множества присутствующих во втором.


set_symmetric_difference
_OutputIter set_symmetric_difference(_InputIter1 first1, _InputIter1 last1, _InputIter2 first2, _InputIter2 last2, _OutputIter result);
Определение элементов из первого множества отсутствующих во втором и элементов второго отсутствующих в первом.


set_union
_OutputIter set_union(_InputIter1 first1, _InputIter1 last1, _InputIter2 first2, _InputIter2 last2, _OutputIter result);
Создаёт множество отсортированных элементов их двух контейнеров в третьем.


stable_partition
_ForwardIter stable_partition(_ForwardIter first, _ForwardIter last, _Predicate pred);
Подобна partition.


swap
void swap(_Tp& a, _Tp& b);
Перестановка значений контейнера.


swap_ranges
_ForwardIter2 swap_ranges(_ForwardIter1 first1, _ForwardIter1 last1, _ForwardIter2 first2);
Перестановка группы элементов контейнера.


transform
transform();
-//-


unique
_ForwardIter unique(_ForwardIter first, _ForwardIter last);
Удаляет из контейнера одинаковые элементы


unique_copy
_OutputIter unique_copy(_InputIter first, _InputIter last, _OutputIter result, _Tp*);
Копирует все уникальные элементы в другой контейнер.

Алгоритмы, не модифицирующие последовательности

adjacent_find
_ForwardIter adjacent_find(_ForwardIter first, _ForwardIter last, _BinaryPredicate binary_pred);
Возвращает итератор для чтения, указывающий на первый из двух идентичных смежных элементов в последовательности.


equal
inline bool equal(_InputIter1 first1, _InputIter1 last1,_InputIter2 first2);
Сравнение указанных участков двух контейнеров.


find
_InputIter find(_InputIter first, _InputIter last, const _Tp& val, input_iterator_tag);
Возвращает положение искомого значения <val>


find_each
find_each();
-//-


find_end
find_end();
-//-


find_first_of
find_first_of();
-//-


find_if
InputIter find_if(_InputIter first, _InputIter last, _Predicate pred, input_iterator_tag);
Возвращает положение значения определённого функцией <pred>.


lexicographical_compare
bool lexicographical_compare(_InputIter1 first1, _InputIter1 last1, _InputIter2 first2, _InputIter2 last2);
Используется для лексикографического сравнения двух массивов символов.


max
const _Tp& max(const _Tp& a, const _Tp& b);
Определение максимального значения.


min
const _Tp& min(const _Tp& a, const _Tp& b);
Определения минимального значения.


mismatch
pair<_InputIter1, _InputIter2> mismatch(_InputIter1 first1, _InputIter1 last1, _InputIter2 first2);
Выполняет сравнение указанных участков двух контейнеров и возвращает пару итераторов указывающих различные позиции контейнеров.

std::pair<std::vector<int>::iterator, std::vector<int>::iterator> location;
location = std::mismatch(v1.begin(),v1.end(),v3.begin());


search
search();
-//-


search_n
search_n();
-//-

Числовые алгоритмы <numeric>

accumulate
_Tp accumulate(_InputIterator first, _InputIterator last, _Tp init);
Суммирование значений указанной области контейнера.


adjacent_difference
_OutputIterator adjacent_difference(_InputIterator first, _InputIterator last, _OutputIterator result);
Вычисление разницы между парой смежных элементов


count
void count(_InputIter first, _InputIter last, const _Tp& value,_Size& n);
Выполняет подсчет количества объектов <value> в указанной области контейнера.


count_if
void count_if(_InputIter first, _InputIter last, _Predicate pred, _Size& n);
Выполняет подсчет количества объектов выбранных функцией <pred> в указанной области контейнера.


for_each
_Function for_each(_InputIter first, _InputIter last, _Function f);
Применение функции <f> к указанным элементам контейнера. Общая функция должна принимать текущий элемент в качестве аргумента и не должна модифицировать этот элемент.


inner_product
_Tp inner_product(_InputIterator1 first1, _InputIterator1 last1, _InputIterator2 first2, _Tp init);
Вычисление суммы произведений двух последовательностей.


max_element
_ForwardIter max_element(_ForwardIter first, _ForwardIter last);
Возвращает указатель на максимальный элемент в контейнере.


min_element
_ForwardIter min_element(_ForwardIter first, _ForwardIter last);
Возвращает указатель на минимальный элемент в контейнере.


nth_element
void nth_element(_RandomAccessIter first, _RandomAccessIter nth, _RandomAccessIter last);
Разделение диапазонов элементов.


partial_sum
_OutputIterator partial_sum(_InputIterator first, _InputIterator last, _OutputIterator result);
Вычисление суммы элементов двух контейнеров с накоплением.


partial_sort
void partial_sort(_RandomAccessIter first, _RandomAccessIter middle, _RandomAccessIter last);
Сортировка части последовательности.


partial_sort_copy
_RandomAccessIter partial_sort_copy(_InputIter first, _InputIter last, _RandomAccessIter result_first, _RandomAccessIter result_last);
Сортировка части последовательности с копированием результата.


random_shuffle
inline void random_shuffle(_RandomAccessIter first, _RandomAccessIter last);
Располагает элементы указанного участка контейнера в произвольном порядке.


stable_sort
void stable_sort(_RandomAccessIter first, _RandomAccessIter last);
Сортировка (аналогично sort)


transform
_OutputIter transform(_InputIter first, _InputIter last, _OutputIter result, _UnaryOperation oper);
Применение функции <f> к указанным элементам контейнера. Общая функция должна принимать текущий элемент в качестве аргумента, не должна модифицировать этот элемент и должна возвращать трансформированное значение.

Алгоритмы, сортировки кучи

make_heap
make_heap(_RandomAccessIterator first, _RandomAccessIterator last);
Создание и инициализация кучи.


pop_heap
void pop_heap(_RandomAccessIterator first, _RandomAccessIterator last);
Удаление элемента с вершины кучи.


push_heap
void push_heap(_RandomAccessIterator first, _RandomAccessIterator last);
Добавление нового элемента в кучу.


sort_heap
sort_heap(_RandomAccessIterator first, _RandomAccessIterator last, _Compare comp);
Сортировка последовательности значений.


2.8.4 Класс <bitset>

Класс bitset обеспечивает операции для создания и манипуляции наборами битов. Наборы битов имеют фиксированный размер: bitset<size> b;. Операции:


set
Установка указанного бита.


reset
Сброс указанного бита.


flip
Переключает бит.


at
Получить бит.


test
Проверка бита.


size
Возвращает число битов в наборе.


count
Возвращает число установленных битов.


any
Возвращает true если хоть один бит в наборе установлен.


none
Возвращает true если не один бит в наборе неустановлен.


==, !=
Сравнение наборов битов.


&=, |=, ^ =, >>=, <<=
Битовые операции над наборами битов.


to_string
Преобразует набор битов в строку.


to_ulong
Преобразует набор битов в unsigned long.


2.8.5 Объекты-функции

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


divides<T> – арифметический;
equal_to<T> – реляционный;
greater<T> – реляционный;
greater_equal<T> – реляционный;
less<T> – реляционный;
less_equal<T> – реляционный;
logical_and<T> – логический;
logical_not<T> – логический;
logical_or<T> – логический;
minus<T> – арифметический;
moduls<T> – арифметический;
negate<T> – арифметический;
not_equal_to<T> – реляционный;
plus<T> – арифметический;
multiplies<T> – арифметический;


 
Files[Hide files/form]
There is no comment on this page. [Display comments/form]