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()) или удаления элемента. Так же, как и для массива, мы можем обратиться к произвольному элементу вектора операцией индексации [n]. Это уже и есть первый, поверхностный слой познаний о vector, который позволяет нам начать с ним работать:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | #include <iostream> #include <vector> #include <climits> using namespace std; // вывод на экран значений ёмкости вектора // его размера и элементов void put(const vector<float>& v) { cout << "capacity=" << v.capacity() << ", size=" << v.size() << " : "; for (int i = 0; i < v.size(); i++) cout << v[i] << " "; cout << endl; } // перегруженный оператор, добавляющий к вектору ещё n // последовательных значений натуральных чисел vector<float>& operator +=(vector<float>& v, int n) { float last = v[v.size() - 1]; for (int 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)=" << ((int)INT_MAX + 1) / 2 << endl; put(array); put(array += 2); put(array += 6); return 0; } |
Описание vector<float> (это и есть упоминавшийся ранее template в описании класса) объявляет в коде объект array: вектор элементов типа float.
Далее мы видим такие методы класса vector<float>, как max_size() — максимально возможная длина векторов вообще (константа реализации); size() — текущий размер (число элементов) вектора; capacity() — текущая ёмкость вектора (максимальное число элементов, которое может быть помещено в вектор в текущем его размещении). Выполнение этого фрагмента даст что-то примерно следующее (детали могут различаться в зависимости от реализации):
Здесь видно достаточно интересное поведение вектора (в этом и его смысл): как только при добавлении очередного элемента, ёмкости вектора становится недостаточно, делается новое размещение вектора, резервируя для него удвоенную ёмкость (с запасом, чтобы следующее же добавление нового элемента не потребовало сразу же нового переразмещения).
Таким образом мы получили эквивалент массива C++, размер которого (size()) меняется в произвольных пределах от нескольких единиц до миллионов элементов. Обратим внимание (это очень важно), что увеличение размера вектора достигается не индексацией за пределы его текущего размера, а «заталкиванием» (метод push_back()) нового элемента в конец вектора. Другой способ изменить размер вектора — это вызвать методы resize(). Именно поэтому, для вектора предусмотрено 2 разных способа индексации: операция [n] и метод-функция at(n). Метод at() проверяет текущий размер вектора size(), и при индексации за его границу срабатывает исключение (это ошибка!). Напротив, операция индексации не проверяет границу, что небезопасно, но зато это быстрее.