В предыдущей заметке речь шла о массивах как прототипе и прародителе контейнеров. Теперь дошла очередь до собственно контейнерных классов и поддерживающих их библиотек.
Под термином библиотека стандартных шаблонов (STL, Standard Template Library) понимают набор интерфейсов и компонентов, первоначально разработанных Александром Степановым, Менг Ли и другими сотрудниками AT&T Bell Laboratories и Hewlett-Packard Research Laboratories в начале 90-х годов (хотя и позже ещё весьма многие приложили руку к тому, что стало на сегодня стандартным компонентом C++). Далее библиотека STL перешла в собственность компании SGI, а также была включена как компонент в набор библиотек Boost. И наконец библиотека STL вошла в стандарты C++ 1998 и 2003 годов (ISO/IEC 14882:1998 и ISO/IEC 14882:2003) и с тех пор считается одной из составных частей стандартной библиотек C++.
Стандарт не называет эту часть библиотеки STL, но эту хронологию хорошо бы учитывать, разбираясь с какой версией компилятора, языка и литературы вы имеете дело — в процессе сокращения HP STL до размеров, подходящих для стандартизации, часть алгоритмов и функторов выпали из состава библиотеки, а кое-что, со временем, и добавляется (например, расширение набора переопределенных прототипов некоторых методов контейнеров). По тексту будет использоваться традиционное название STL только чтобы было ясно какую часть стандартной библиотеки C++ мы имеем в виду.
Первоначальной целью STL (это хорошо видно из хронологии комментариев в заголовочных файлах) было создание боле гибкой модели регулярных контейнеров по сравнению с массивами и обобщение на них некоторых широко используемых алгоритмов (таких как поиск, сортировка и некоторых других). Но затея оказалась плодотворнее первоначальных намерений, и была существенно расширена. STL вводит ряд понятий и структур данных, которые почти во всех случаях позволяют сильно упростить программный код. Вводятся следующие категории понятий:
Библиотека STL — это весьма обширная область. Её описанию посвящены целые отдельные книги. Здесь же, в силу достаточно начального уровня знакомства, ограниченности объёма и следованию объявленных ранее целей, будет рассмотрена техника использования STL на интуитивно ясных примерах. Синтаксис STL основан на использовании таких синтаксических конструкций языка C++ как шаблоны (templates) классов и шаблоны функций. Но для успешного применения техники STL совсем не обязательно глубокое понимание техники templates (это может прийти позже).
Центральным понятием STL, вокруг которого крутится всё остальное, это контейнер (ещё используют термин коллекция). Контейнер — это набор некоторого количества обязательно однотипных элементов, упакованных в контейнер определённым образом. Простейшим прототипом контейнера в классическом языке C++ является массив. Тот способ, которым элементы упаковываются в контейнер и определяет тип контейнера и особенности работы с элементами в таком контейнере. STL вводит целый ряд разнообразных типов контейнеров, основные из них:
Мы рассмотрим на примерах использования последовательно основных из них, переходя от более простых к сложным. Простейшим типом контейнеров является вектор. Близким прототипом вектора является массив С++, но размер вектора может динамически изменяться в любое время операциями добавления (метод push_back()) или удалении (например, метод pop_back()) элемента. Так же, как и для массива, мы можем обратиться к произвольному элементу вектора операцией индексации [ n ]. То, что уже сказано — это уже и есть первый, поверхностный слой познаний о vector, но который достаточен для ого, чтобы позволить начать с ним работать на аналогиях того, как мы работаетм с традиционными массивами:
Здесь видно достаточно интересное поведение вектора (в этом и его смысл): как только при добавлении очередного элемента вектора его ёмкости становится недостаточно для ещё одного элемента, делается новое размещение вектора, резервируя для него удвоенную ёмкость (с запасом, чтобы следующее же добавление нового элемента не потребовало тут же нового переразмещения).
Примечание: Показанное выше удвоение ёмкости вектора при переразмещении — это характерное поведение для реализации библиотек компилятора GCC. Но точный алгоритм резервирования ёмкости под будущие элементы стандарт оставляет на волю реализатора, поэтому на него нельзя рассчитывать, и описан он здесь только для качественного понимания картины (реализации Visual Studio ведут себя по-другому, резервируя только небольшой избыток… это вы изучите сами).
Отметим на дальнейшее, пока без комментариев, то важное обстоятельство, что операции помещения элементов в контейнер выполняет копирование элемента, что влечёт за собой а).требование наличия копирующего конструктора для типа элементов и б).для структурных элементов это может привести к заметным затратам производительности.
Таким образом мы получили эквивалент массива C++, размер которого (size()) динамически меняется в произвольных пределах от нескольких единиц до миллионов элементов. Обратим внимание (это очень важно), что увеличение размера вектора достигается ни в коем случае не индексацией за пределы его текущего размера, а «заталкиванием» (метод push_back()) нового элемента в конец вектора (симметрично, метод pop_back() выталкивает последний элемент из массива и уменьшает его size()). Другой способ изменить размер вектора — это сразу вызвать методы resize() под нужный размер. Именно потому, что размер вектора, в отличие от массива, может динамически меняться, для вектора предусмотрено 2 разных способа индексации: как операция [ i ] и как метод-функция at( i ). Они различаются: метод at() проверяет текущий размер вектора size(), и при индексации за его границу возбуждает исключение. Напротив, операция индексации не проверяет границу, что небезопасно, но зато это быстрее. Метод at() позволяет нам контролировать выход за границы вектора и либо квалифицировать это как логическую ошибку, либо корректировать текущий размер контейнера под потребность, как в вот таком фрагменте (здесь попыток доступа вдвое больше, чем реально выполненных операций):
Стандарт C++11 привносит дополнительные выразительные средства, такие, например, как списки инициализации и выводимость типов, которые намного упрощают работу с контейнерами (и даже делают ненужными старые привычные приёмы записи). Вот как может описываться матрица, когда одновременно описываются её а). конфигурация (квадратная, хотя может быть прямоугольная и даже треугольная), b). размерность (3х3) и c). инициализирующие значения:
А заодно, здесь же показана работа с векторами (транспонирование квадратной матрицы и вывод в выходной поток) как с псевдо-массивами (пользуясь только индексированием), чем вектора, по существу, и являются (в частности, показано как тип элемента вектор определяется на основании выводимого типа по стандарту C++11):
Примечание: В рамках того, что мы уже знаем о векторах, возникает иногда вопрос: а как строго должен определяться тип возвращаемого size() результата (чтобы избежать зависимости от платформы) и, соответственно, любых переменных циклов, оперирующих с размером вектора? Временами от блюстителей чистоты синтаксиса следует ответ, что это должен быть size_t, и этот ответ — неверный (тем более, что для многих платформ size_t и определяется как unsigned int). Если вы захотите записать абсолютно строгого определение типа size() вектора, то строку в примере выше следует записать вот так:
Или, полагаясь на выводимость типов C++11, вот так:
Отметив здесь этот тонкий нюанс (приняв к сведению), мы не станем его применять далее, во избежания лишней громоздкости примеров, а будем использовать для размерностей просто unsigned.
P.S. Кого это, возможно, заинтересует, архив всех примеров кода для проверки и дальнейших экспериментов (как предыдущей и этой частей, так и всех последующих) можно взять здесь или здесь, чтобы не колотить всё это вручную.
Под термином библиотека стандартных шаблонов (STL, Standard Template Library) понимают набор интерфейсов и компонентов, первоначально разработанных Александром Степановым, Менг Ли и другими сотрудниками AT&T Bell Laboratories и Hewlett-Packard Research Laboratories в начале 90-х годов (хотя и позже ещё весьма многие приложили руку к тому, что стало на сегодня стандартным компонентом C++). Далее библиотека STL перешла в собственность компании SGI, а также была включена как компонент в набор библиотек Boost. И наконец библиотека STL вошла в стандарты C++ 1998 и 2003 годов (ISO/IEC 14882:1998 и ISO/IEC 14882:2003) и с тех пор считается одной из составных частей стандартной библиотек C++.
Стандарт не называет эту часть библиотеки STL, но эту хронологию хорошо бы учитывать, разбираясь с какой версией компилятора, языка и литературы вы имеете дело — в процессе сокращения HP STL до размеров, подходящих для стандартизации, часть алгоритмов и функторов выпали из состава библиотеки, а кое-что, со временем, и добавляется (например, расширение набора переопределенных прототипов некоторых методов контейнеров). По тексту будет использоваться традиционное название STL только чтобы было ясно какую часть стандартной библиотеки C++ мы имеем в виду.
Первоначальной целью STL (это хорошо видно из хронологии комментариев в заголовочных файлах) было создание боле гибкой модели регулярных контейнеров по сравнению с массивами и обобщение на них некоторых широко используемых алгоритмов (таких как поиск, сортировка и некоторых других). Но затея оказалась плодотворнее первоначальных намерений, и была существенно расширена. STL вводит ряд понятий и структур данных, которые почти во всех случаях позволяют сильно упростить программный код. Вводятся следующие категории понятий:
- Контейнер — способ хранения набора объектов в памяти.
- Итератор — средство доступа к содержимому отдельных объектов в контейнере.
- Алгоритм — определение наиболее стандартных вычислительных процедур на контейнерах.
- Адаптер — адаптация основны категорий для обеспечения наиболее употребляемых интерфейсов (таких как стек или очередь).
- Функтор (функциональный объект) — сокрытие функции в объекте для использования её другими категориями.
Библиотека STL — это весьма обширная область. Её описанию посвящены целые отдельные книги. Здесь же, в силу достаточно начального уровня знакомства, ограниченности объёма и следованию объявленных ранее целей, будет рассмотрена техника использования STL на интуитивно ясных примерах. Синтаксис STL основан на использовании таких синтаксических конструкций языка C++ как шаблоны (templates) классов и шаблоны функций. Но для успешного применения техники STL совсем не обязательно глубокое понимание техники templates (это может прийти позже).
Центральным понятием STL, вокруг которого крутится всё остальное, это контейнер (ещё используют термин коллекция). Контейнер — это набор некоторого количества обязательно однотипных элементов, упакованных в контейнер определённым образом. Простейшим прототипом контейнера в классическом языке C++ является массив. Тот способ, которым элементы упаковываются в контейнер и определяет тип контейнера и особенности работы с элементами в таком контейнере. STL вводит целый ряд разнообразных типов контейнеров, основные из них:
- последовательные контейнеры — вектор (vector), двусвязный список (list), дэк (deque);
- ассоциативные контейнеры — множества (set и multiset ), хэш-таблицы (map и multimap);
- псевдо контейнеры — битовые маски (bitset), строки (string и wstring), массивы (valarray);
Мы рассмотрим на примерах использования последовательно основных из них, переходя от более простых к сложным. Простейшим типом контейнеров является вектор. Близким прототипом вектора является массив С++, но размер вектора может динамически изменяться в любое время операциями добавления (метод push_back()) или удалении (например, метод pop_back()) элемента. Так же, как и для массива, мы можем обратиться к произвольному элементу вектора операцией индексации [ n ]. То, что уже сказано — это уже и есть первый, поверхностный слой познаний о vector, но который достаточен для ого, чтобы позволить начать с ним работать на аналогиях того, как мы работаетм с традиционными массивами:
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
void put( const vector<float>& v ) {
cout << "capacity=" << v.capacity()
<< ", size=" << v.size() << " : ";
for( unsigned i = 0; i < v.size(); i++ )
cout << v[ i ] << " ";
cout << endl;
}
vector<float>& operator +=( vector<float>& v, unsigned n ) {
float last = v[ v.size() - 1 ];
for( unsigned i = 0; i < n; i++ )
v.push_back( last + i + 1 );
return v;
}
int main( void ) {
float data[] = { 1., 2., 3., 4., 5., 6., 7. };
int n = sizeof( data ) / sizeof( data[ 0 ] );
vector<float> array( data, data + n );
cout << "max_size=" << array.max_size()
<< " ((INT_MAX+1)/2)=" << ( (unsigned)INT_MAX + 1 ) / 2 << endl;
put( array );
put( array += 2 );
put( array += 6 );
}
Описание vector<float> (это и есть упоминавшийся ранее template в описании класса) объявляет в коде <b>объект</b>: векторэлементов типа float. Далее мы видим такие методы класса vector как max_size() — максимально возможная длина векторов вообще (константа реализации), size() — текущий размер (число элементов) вектора, capacity() — текущая ёмкость вектора, максимальное число элементов, которое может быть помещено в вектор в текущем его размещении. Выполнение этого фрагмента даст что-то примерно следующее (детали могут различаться в зависимости от реализации):
$ ./vect1
max_size=1073741823 ((INT_MAX+1)/2)=1073741824
capacity=7, size=7 : 1 2 3 4 5 6 7
capacity=14, size=9 : 1 2 3 4 5 6 7 8 9
capacity=28, size=15 : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Здесь видно достаточно интересное поведение вектора (в этом и его смысл): как только при добавлении очередного элемента вектора его ёмкости становится недостаточно для ещё одного элемента, делается новое размещение вектора, резервируя для него удвоенную ёмкость (с запасом, чтобы следующее же добавление нового элемента не потребовало тут же нового переразмещения).
Примечание: Показанное выше удвоение ёмкости вектора при переразмещении — это характерное поведение для реализации библиотек компилятора GCC. Но точный алгоритм резервирования ёмкости под будущие элементы стандарт оставляет на волю реализатора, поэтому на него нельзя рассчитывать, и описан он здесь только для качественного понимания картины (реализации Visual Studio ведут себя по-другому, резервируя только небольшой избыток… это вы изучите сами).
Отметим на дальнейшее, пока без комментариев, то важное обстоятельство, что операции помещения элементов в контейнер выполняет копирование элемента, что влечёт за собой а).требование наличия копирующего конструктора для типа элементов и б).для структурных элементов это может привести к заметным затратам производительности.
Таким образом мы получили эквивалент массива C++, размер которого (size()) динамически меняется в произвольных пределах от нескольких единиц до миллионов элементов. Обратим внимание (это очень важно), что увеличение размера вектора достигается ни в коем случае не индексацией за пределы его текущего размера, а «заталкиванием» (метод push_back()) нового элемента в конец вектора (симметрично, метод pop_back() выталкивает последний элемент из массива и уменьшает его size()). Другой способ изменить размер вектора — это сразу вызвать методы resize() под нужный размер. Именно потому, что размер вектора, в отличие от массива, может динамически меняться, для вектора предусмотрено 2 разных способа индексации: как операция [ i ] и как метод-функция at( i ). Они различаются: метод at() проверяет текущий размер вектора size(), и при индексации за его границу возбуждает исключение. Напротив, операция индексации не проверяет границу, что небезопасно, но зато это быстрее. Метод at() позволяет нам контролировать выход за границы вектора и либо квалифицировать это как логическую ошибку, либо корректировать текущий размер контейнера под потребность, как в вот таком фрагменте (здесь попыток доступа вдвое больше, чем реально выполненных операций):
int main( void ) {
vector<int> nums;
for( int i = 0; i < 10; ) {
try {
nums.at( i ) = i; // vector::at throws an out-of-range
i++;
}
catch( const out_of_range& ) {
cout << i << " ";
nums.resize( i + 1 );
}
}
cout << endl << nums.size() << endl;
}
$ ./vect7
0 1 2 3 4 5 6 7 8 9
10
Стандарт C++11 привносит дополнительные выразительные средства, такие, например, как списки инициализации и выводимость типов, которые намного упрощают работу с контейнерами (и даже делают ненужными старые привычные приёмы записи). Вот как может описываться матрица, когда одновременно описываются её а). конфигурация (квадратная, хотя может быть прямоугольная и даже треугольная), b). размерность (3х3) и c). инициализирующие значения:
void print( const vector< vector<float> >& m ) {
for( auto &row : m ) {
for( auto x : row )
cout << x << ' ';
cout << endl;
}
}
void trans( vector< vector<float> >& m ) {
for( unsigned i = 0; i < m.size(); i++ )
for( unsigned j = i + 1; j < m[ i ].size(); j++ ) {
float tmp = m[ i ][ j ];
m[ i ][ j ] = m[ j ][ i ];
m[ j ][ i ] = tmp;
}
}
int main( void ) {
vector< vector<float> > matrix = {
{ 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 9 }
};
print( matrix );
cout << "---------" << endl;
trans( matrix );
print( matrix );
}
А заодно, здесь же показана работа с векторами (транспонирование квадратной матрицы и вывод в выходной поток) как с псевдо-массивами (пользуясь только индексированием), чем вектора, по существу, и являются (в частности, показано как тип элемента вектор определяется на основании выводимого типа по стандарту C++11):
$ ./vect6
1 2 3
4 5 6
7 8 9
---------
1 4 7
2 5 8
3 6 9
Примечание: В рамках того, что мы уже знаем о векторах, возникает иногда вопрос: а как строго должен определяться тип возвращаемого size() результата (чтобы избежать зависимости от платформы) и, соответственно, любых переменных циклов, оперирующих с размером вектора? Временами от блюстителей чистоты синтаксиса следует ответ, что это должен быть size_t, и этот ответ — неверный (тем более, что для многих платформ size_t и определяется как unsigned int). Если вы захотите записать абсолютно строгого определение типа size() вектора, то строку в примере выше следует записать вот так:
for( vector<float>::size_type j = i + 1; j < m[ i ].size(); j++ ) { ...
Или, полагаясь на выводимость типов C++11, вот так:
for( auto j = i + 1; j < m[ i ].size(); j++ ) { ...
Отметив здесь этот тонкий нюанс (приняв к сведению), мы не станем его применять далее, во избежания лишней громоздкости примеров, а будем использовать для размерностей просто unsigned.
P.S. Кого это, возможно, заинтересует, архив всех примеров кода для проверки и дальнейших экспериментов (как предыдущей и этой частей, так и всех последующих) можно взять здесь или здесь, чтобы не колотить всё это вручную.
