Данная статья определяет основные понятия стандартной библиотеки С++. Она приводится для того чтобы на неё ссылаться в дальнейшем.

Наибольшей частью стандартной библиотеки С++ является библиотека STL (Standard Template Library – Стандартная Библиотека Шаблонов). Библиотека STL содержит пять основных видов компонентов:

• контейнер (container): управляет набором объектов в памяти.
• итератор (iterator): обеспечивает для алгоритма средство доступа к содержимому контейнера.
• алгоритм (algorithm): определяет вычислительную процедуру.
• функциональный объект (function object): инкапсулирует функцию в объекте для использования другими компонентами.
• адаптер (adaptor): адаптирует компонент для обеспечения различного интерфейса.

Все компоненты удовлетворяют ряду требований, поэтому хорошо согласуются друг с другом.

Из определения контейнера следует, что любая пользовательская структура данных является контейнером. В нашем случае контейнеры есть стандартные структуры данных, такие как список (list), вектор (vector), словарь (map) и многие другие. Формальные требования к контейнерам довольно обширны, но основным является правило доступа к элементам. Доступ к элементам контейнера осуществляется через специальные объекты — итераторы (см. ниже). Вы можете не знать, как располагаются элементы контейнера в памяти, однако вы точно знаете, что итераторы можно перебрать последовательно, и каждый из них предоставит доступ к элементу. Итератор, указывающий на первый элемент, можно получить при помощи метода iterator begin(); контейнера. Итератор, указывающий за последний элемент, можно получить при помощи метода iterator end(); контейнера. Другими словами, итераторы располагаются в полуинтервале (или полуотрезке), что можно формально записать как [begin, end). Пример объявления контейнера:

struct a_container {
    struct an_iterator;

    an_iterator begin();
    an_iterator end();
};

В ожидаемом стандарте С++20 предложено использовать структуру, инкапсулирующую полуинтервалы — ranges

Итератор — объект, предоставляющий доступ к элементам контейнера и позволяющий их перебирать. Итератор является свойством контейнера. В первых реализациях стандартной библиотеки С++ итератор реализовывался как указатель на элемент контейнера. В современных реализациях это класс, инкапсулирующий указатель на объект контейнера.

Основные требования к итераторам — наличие операторов разыменования и инкремента. Ниже объявление контейнера с итератором.

template<typename TYPE>
struct a_container {

    struct an_iterator {
        void operator++();
        TYPE& operator*();
    };

    an_iterator begin();
    an_iterator end();
};

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

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

template<typename ITERATOR, typename RESULT>
RESULT an_algorithm(ITERATOR first, ITERATOR last, ...);

В объявлении класса можно переопределить оператор (). Если этот оператор в классе переопределен, то объекты этого класса получают свойства функций (их можно использовать как функции). Такие объекты называются функциональными или функторами. Функторы удобно использовать, когда функция должна обладать «памятью», а также, как замена указателей на функции.

Начиная со стандарта С++11 существует возможность краткой записи функторов — лямбда-функции.

Каких-либо специальных требований к функторам нет. Разве что иногда может требоваться наследование от функтора function (до стандарта С++11 — unary_function или binary_function). Небольшой пример реализации функтора:

template<typename TYPE>
struct plus{
    TYPE operator ()(const TYPE& p1, const TYPE& p2) const{
        return p1 + p2;
    }
};

Также STL предлагает ряд классов и функций (фукнторов), которые преобразуют интерфейс к нужному. В частности, есть адаптер stack, который на основе контейнеров реализует, соответственно, стэк. В качестве примера можно рассмотреть адаптер бинарной функции к унарной (на данный момент эта функция объявлена в стандарте С++ устаревшей):

template<typename BIDIRECTIONAL_FUNCTION, typename TYPE>
class bind1st {
    BIDIRECTIONAL_FUNCTION _bf;
    TYPE _first;
public:

    bind1st(BIDIRECTIONAL_FUNCTION bf, TYPE first): _bf(bf), _first(first) {}
    TYPE operator()(const TYPE& p) const {
        return _bf(_first, p);
    }
};

Для самостоятельного чтения

1. Драфт стандарта С++20 на гитхабе
2. C++ Reference
3. Разработка приложений на С++
4. Range-v3, предложение для стандарта