STL: стандартная библиотека шаблонов С++

Механизм шаблонов встроен в компилятор C++, чтобы дать возможность программистам делать свой код короче за счет обобщенного программирования. Естественно, существуют и стандартные библиотеки, реализующие этот механизм. STL является самой эффективной библиотекой C++ на сегодняшний день.

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

Первое знакомство

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

Коллекции

Для использования коллекции в своем коде используйте следующую директиву:

#include <T>,
где T — название коллекции

Итак, наиболее часто используются:

• vector — коллекция элементов, сохраненных в массиве, изменяющегося по мере необходимости размера (обычно, увеличивающегося);
• list — коллекция, хранящая элементы в виде двунаправленного связанного списка;
• map — коллекция, сохраняющая пары вида <const Key, T>, т.е. каждый элемент — это пара вида <ключ, значение>, при этом однозначная (каждому ключу соответствует единственное значение), где ключ — некоторая характеризующая значение величина, для которой применима операция сравнения; пары хранятся в отсортированном виде, что позволяет осуществлять быстрый поиск по ключу, но за это, естественно, придется заплатить: придется так реализовывать вставку, чтобы условие отсортированности не нарушилось;
• set — это отсортированная коллекция одних только ключей, т.е. значений, для которых применима операция сравнения, при этом уникальных — каждый ключ может встретиться во множестве (от англ. set — множество) только один раз;
• multimap — map, в котором отсутствует условие уникальности ключа, т.е. если вы произведете поиск по ключу, то получите не единственное значение, а набор элементов с одинаковым значением ключа; для использования в коде используется #include <map>;
• multiset — коллекция с тем же отличием от set’а, что и multimap от map’а, т.е. с отсутствием условия уникальности ключа; для подключения: #include <set>.

Строки

Любая серьезная библиотека имеет свои классы для представления строк. В STL строки представляются как в формате ASCII, так и Unicode:
string — коллекция однобайтных символов в формате ASCII;
wstring — коллекция двухбайтных символов в формате Unicode; включается командой #include <xstring>.

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

strstream — используются для организации STL-строкового сохранения простых типов данных.
Разбор примеров начнем именно с этого класса.

			//stl.cpp: Defines the entry point for the console application 

#include "stdafx.h" 
#include <iostream> 
#include <strstream> 
#include <string> 
using namespace std;

int _tmain (int argc, _TCHAR* argv []) 
{ 
    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(). Затем “реальная часть” потока копируется в новую строку, и мы получаем распечатку уже без мусора.

Итераторы

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

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

Вот несколько формализованных определений итератора:

• Итераторы обеспечивают доступ к элементам коллекции
• Для каждого конкретного класса STL итераторы определяются отдельно внутри класса этой коллекции.

Существуют три типа итераторов:

• (forward) iterator — для обхода коллекции от меньшего индекса к большему;
• reverse iterator — для обхода коллекции от большего индекс к меньшему;
• random access iterator — для обхода коллекции в любом направлении.

Вот пример использования итераторов для удаления половин элементов коллекции:

			#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void printInt (int number);

int _tmain (int argc, _TCHAR* argv [])
{
    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;
}
		

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

Итерация вперед и аналогично назад происходит так:
for (iterator element = begin (); element < end (); element++) { t = (*element); }

При использовании random access iterator, например, так:
for (iterator element = begin (); element < end (); element+=2) { t = (*element);}

Методы коллекций

Основными методами, присутствующими почти во всех коллекциях являются следующие:

• empty — определяет, пуста ли коллекция;
• size — возвращает размер коллекции;
• begin — возвращает прямой итератор, указывающий на начало коллекции;
• end — возвращает прямой итератор, указывающий на конец коллекции, т.е. на несуществующий элемент, идущий после последнего;
• rbegin — возвращает обратный итератор на начало коллекции;
• rend — возвращает обратный итератор на конец коллекции;
• clear — очищает коллекцию, т.е. удаляет все ее элементы;
• erase — удаляет определенные элементы из коллекции;
• capacity — возвращает вместимость коллекции, т.е. количество элементов, которое может вместить эта коллекция (фактически, сколько памяти под коллекцию выделено);

Вместимость коллекции, как было сказано в начале, меняется по мере надобности, т.е. если вся выделенная под коллекцию память уже заполнена, то при добавлении нового элемента вместимость коллекции будет увеличена, а все значения, бывшие в ней до увеличения, будут скопированы в новую область памяти — это довольно “дорогая” операция. Убедиться в том, что размер и вместимость — разные вещи, можно на следующем примере:

			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.

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

Алгоритмы

Разработчики библиотеки STL ставили перед собой гораздо более серьезную задачу, чем создание библиотеки с набором шаблонных структур данных. 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

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

Предикаты

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

Потокобезопасность

Важно понимать, что STL — не потокобезопасная библиотека. Но решить эту проблему очень просто: если два потока используют одну коллекцию, просто реализуйте критическую секцию и Mutex.

Заключение

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