Что такое STL (стандартная библиотека шаблонов) для С++ и ее основные компоненты

STL на C++ воплощает принципы универсального программирования. Библиотека шаблонов содержит набор алгоритмов, контейнеров, итераторов и функциональных объектов. Они позволяют разработчикам писать код, который легко работает с различными типами данных.  STL состоит из различных компонентов, которые гармонично работают вместе. В этой статье подробно рассмотрим все компоненты Standard Template Library, структуру библиотеки и примеры использования STL в реальных проектах.

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

Универсальное программирование — это парадигма программирования, которая делает упор на написание кода таким образом, чтобы он не зависел от конкретных типов данных. Это позволяет писать повторно используемый код, который работает с различными типами данных. Что помогает создавать гибкие и эффективные алгоритмы. Идея универсального программирования состоит в возможности отделить алгоритмы от структур данных, с которыми они работают. Это приводит к созданию «многоразового» и модульного кода.

К универсальному программированию относится STL (стандартная библиотека шаблонов). Она считается частью стандартной библиотеки C++. Standard Template Library появилась в середине 90-х годов прошлого века. Она предоставила большой набор алгоритмов и шаблонов контейнеров. Он же позволил эффективно манипулировать данными и создал основу для написания кода многократного использования. 

STL предоставляет набор общих классов для C++ — это контейнеры и ассоциативные массивы. Их можно использовать с любым встроенным типом и с любым определяемым пользователем типом, поддерживающим элементарные операции (например, копирование и присваивание). Алгоритмы STL не зависят от контейнеров — это снижает сложность библиотеки.

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

Компоненты STL 

STL состоит из пяти основных компонентов:

• итераторы;
• функциональные объекты;
• контейнеры;
• алгоритмы;
• адаптеры.

Операторы 

Есть разные типы операторов. Перегруженные операторы, которые являются функциями-членами, могут быть объявлены статическими. Однако это разрешено только для operator() и operator[].

Такие операторы могут вызываться с использованием функциональной нотации. Однако, когда эти операторы появляются в выражениях, для них по-прежнему требуется объект типа class.

struct SwapThem {
    template <typename T>
    static void operator()(T& lhs, T& rhs) 
    {
        std::ranges::swap(lhs, rhs);
    }
    template <typename T>
    static void operator[](T& lhs, T& rhs)
    {
        std::ranges::swap(lhs, rhs);
    } 
};
inline constexpr SwapThem swap_them {};
 
void foo()
{
    int a = 1, b = 2;
 
    swap_them(a, b); // OK
    swap_them[a, b]; // OK
 
    SwapThem{}(a, b); // OK
    SwapThem{}[a, b]; // OK
 
    SwapThem::operator()(a, b); // OK
    SwapThem::operator[](a, b); // OK
 
    SwapThem(a, b); // error, invalid construction
    SwapThem[a, b]; // error
}

В библиотеке есть реляционные операторы для сравнения операндов одного типа.  Операндами называют значения, которые участвуют в операции. Рассмотрим операторы >, <, ==, <=, >=, !=. для STL-массивов в C++. Два основных оператора, используемые в массивах STL — это сравнение на равенство (==) и сравнение на меньшую величину (<) между двумя контейнерами массива.

При сравнении на равенство (==) элементы обоих массивов сравниваются с обеих сторон. Начиная с первых элементов обоих массивов в L.H.S и R.H.S оператора ==, сравнение останавливается при первом несоответствии.

Сравнение меньше, чем (<), выполняется лексикографическим способом. Алгоритм работает аналогично алгоритму std::lexicographic_compare. Сравнение выполняется последовательно, используя оператор(<) во взаимной последовательности. Лексикографический порядок используется в словарях для сортировки слов по алфавиту, начиная с первой буквы и до конца. Другие операторы используют == и <:

• a!=b is equivalent to !(a==b)
• a>b is equivalent to (b<a)
• a<=b is equivalent to !(b<a)
• a>=b is equivalent to !(a<b)

Эти операторы перегружены в массиве <header>.

Оба STL-массива в L.H.S. и R.H.S. должны иметь одинаковые параметры <Type,Length>.

Пары 

Пары используются для объединения двух значений, которые могут относиться к разным типам данных. Pair предоставляет способ хранения двух разнородных объектов как единого целого. В основном они используются, если мы хотим сохранить кортежи. Парный контейнер — это простой контейнер, определенный в заголовке <utility>, состоящий из двух элементов данных или объектов. 

На первый элемент ссылаются как на «first», а на второй — как на «second». Порядок следования фиксирован (первый, второй). Пару можно назначить, скопировать и сравнить. Массив объектов, выделенных на карте или hash_map, по умолчанию имеет тип «пара», в котором все «первые» элементы — уникальные ключи. Они связаны с их «вторыми» объектами-значениями.

Чтобы получить доступ к элементам, мы используем имя переменной, за которым следует оператор с точкой. За ним идет ключевое слово first или second. 

// CPP program to illustrate Pair in STL
#include <iostream>
#include <utility>
using namespace std;
 
// Driver Code
int main()
{
    // defining a pair
    pair<int, char> PAIR1;
 
    // first part of the pair
    PAIR1.first = 100;
    // second part of the pair
    PAIR1.second = 'G';
 
    cout << PAIR1.first << " ";
    cout << PAIR1.second << endl;
 
    return 0;

Итераторы

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

Итераторы действуют как мост, который соединяет алгоритмы с контейнерами STL и позволяет изменять данные, находящиеся внутри контейнера. Они помогают выполнять итерацию по контейнеру, получать доступ к значениям и присваивать им значения, а также запускать над ними различные операторы для получения желаемого результата.

Итераторы в C++ подразделяются на пять основных категорий в зависимости от их функциональности:

• итератор ввода;
• итератор вывода;
• последовательный итератор;
• двунаправленный итератор;
• итератор произвольного доступа.

Итераторы ввода 

Итератор ввода — самый простой из всех в C++. Он используется для чтения значений из контейнера. Это односторонний итератор. После того как вы прочитали значение, вам разрешено только увеличивать итератор. Его нельзя уменьшить.

Пример:

#include<iostream>
#include<vector>
using namespace std;

int main() {
  vector < int > v = {  1, 2, 3, 4, 5 };
  vector < int > ::iterator itr;

  for (itr = v.begin(); itr != v.end(); ++itr) {
    cout << ( * itr) << " ";
  }
  return 0;
}

Итераторы вывода 

Итераторы вывода C++ могут записывать некоторые значения при выполнении итерации в прямом направлении.

Можно выполнять итерацию в прямом направлении, используя ++, и записывать значения с использованием *. Для записи значений можно использовать оператор =.

Пример:

#include<iostream>
#include<vector>
using namespace std;

int main() {
  vector < int > v = { 1, 2, 3, 4, 5 };
  vector < int > ::iterator itr;

  for (itr = v.begin(); itr != v.end(); ++itr) {
    * itr = 100;
  }
  return 0;
}

Последовательные итераторы

Они служат как для входных, так и для выходных итераторов. Вот почему последовательные называются комбинацией операторов ввода и вывода. Вы можете получать доступ к значениям (функциональность входных итераторов), а также назначать значения (функциональность выходных итераторов). Эти iterators односторонние. Можно перемещаться только в прямом направлении. Кроме того, двунаправленные итераторы и итераторы с произвольным доступом считаются допустимыми прямыми итераторами.

#include <iostream>
#include <vector>
using namespace std;

int main() {
  vector < int > v = { 1, 2, 3, 4, 5 };
  vector < int > ::iterator itr;
  for (itr = v.begin(); itr != v.end(); ++itr) {
    * itr = * itr + 10;
  }
  for (itr = v.begin(); itr != v.end(); ++itr) {
    cout << ( * itr) << " ";
  }
  return 0;
}

Двунаправленные итераторы

Двунаправленные итераторы могут выполнять итерации в любом направлении. Они считаются прямыми итераторами с двумя операторами уменьшения. Они обладают той же функциональностью, что и последовательные итераторы. Отличие только в том, что они могут перемещаться в обоих направлениях. Такие контейнеры, как list, set и multimap, поддерживают двунаправленные iterators. 

#include<iostream>
#include<list>
using namespace std;

int main() {
  list < int > l = { 1, 2, 3, 4, 5 };
  list < int > ::iterator itr;
  for (itr = l.end(); itr != l.begin(); --itr) {
    if (itr != l.end()) {
      cout << ( * itr) << " ";
    }
  }
  cout << ( * itr);
  return 0;
}

Итераторы произвольного доступа 

Они предоставляют произвольный доступ к элементам контейнера. Их также называют двунаправленными с произвольным доступом. Двунаправленные итераторы разыменовываются как на r-значение, так и на lvalue. Следовательно, итераторы произвольного доступа также могут использоваться для той же цели. Iterators произвольного доступа могут как увеличиваться, так и уменьшаться, поскольку они разнонаправленные.

#include<iostream>
#include<vector>
using namespace std;

int main() {
  vector < int > v = { 1, 2, 3, 4, 5 };
  vector < int > ::iterator itr1;
  vector < int > ::iterator itr2;
  itr1 = v.begin();
  itr2 = v.end();
  if (itr1 < itr2) {
    cout << "Moving from begin to end\n";
    cout << "The number of elements are " << itr2 - itr1;
  }
  return 0;
}

Теги итераторов 

Функции тегов итератора — это метод доступа к информации, связанной с итераторами.  Иногда важно, чтобы алгоритм, параметризованный типом iterator, мог определять тип расстояния и тип значения. Теги итератора также позволяют алгоритмам определять категорию. Они могут выполнять различные действия в зависимости от типа.

Функции тега iterator distance_type, value_type и iterator_category более старые методы доступа к информации о типе, связанной с итераторами. Они были определены в исходном STL. Проект стандарта C++ определяет другой и более удобный механизм: iterator_traits. 

В примере ниже используется функция тега value_type для объявления временной переменной типа значения итератора. Здесь также используется вспомогательная функция _iter_swap. Это распространенная практика: в большинстве случаев теги-итераторы используют вспомогательные функции:

template <class ForwardIterator1, class ForwardIterator2, class ValueType>
    inline void __iter_swap(ForwardIterator1 a, ForwardIterator2 b, ValueType*) {
	ValueType tmp = *a;
	*a = *b;
	*b = tmp;
    }

    template <class ForwardIterator1, class ForwardIterator2>
    inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b) {
	__iter_swap(a, b, value_type(a));
    }

Операции с итераторами 

begin(). Возвращает двунаправленный итератор, указывающий на первый элемент контейнера. 

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

advance().Используется для увеличения итератора с его текущей позиции. В качестве аргумента он принимает целое число. Метод advance() увеличивает указатель до этой целочисленной позиции. 

next(itr, value). Возвращает новый итератор, на который iterator будет указывать после многократного увеличения значения.

Параметры: iterator, значение которого необходимо увеличить, целочисленное значение, указывающее, на сколько шагов должен быть увеличен итератор.

prev(). Противоположен методу next(). Он возвращает указатель, направленный на элемент, который вы получаете после уменьшения iterator от текущего элемента.

inserter(). Используется для вставки элементов в указанную позицию в контейнере. Если в этой позиции уже есть элемент, то он также может перезаписать элементы в контейнере, чтобы вставить новые элементы.

Функциональные объекты 

Функциональный объект (или функтор) — это просто объект класса, который предоставляет, по крайней мере, одно определение для operator(). Этот оператор называется оператором вызова или иногда оператором приложения. Стандартная библиотека C++ использует функциональные объекты в основном в качестве критериев сортировки контейнеров и в алгоритмах.

Функциональные объекты обладают двумя основными преимуществами по сравнению с прямым вызовом функции. Первое заключается в том, что функциональный объект может содержать состояние. Второе — функциональный объект считается типом. Он может использоваться в качестве параметра шаблона.

Базовые классы 

Функциональный объект имеет ограничения на тип своего аргумента. Но ограничения по типу не обязательно должны быть простыми: operator() может быть перегружен, или может быть шаблоном-членом. Аналогично у программы не должно быть способа определить, каковы эти ограничения. Однако адаптируемый объект function указывает, каковы типы аргументов и возвращаемых значений. 

STL предоставляет базовые классы unary_function и binary_function для упрощения определения адаптируемых унарных функций и адаптируемых двоичных функций.

Арифметические операции 

Эти типы операций позволяют работать функциональными объектами для разных арифметических операторов. Пример:

const int N = 1000;
vector<double> V1(N);
vector<double> V2(N);
vector<double> V3(N);

iota(V1.begin(), V1.end(), 1);
fill(V2.begin(), V2.end(), 75);

assert(V2.size() >= V1.size() && V3.size() >= V1.size());
transform(V1.begin(), V1.end(), V2.begin(), V3.begin(),
          multiplies<double>());

Сравнения 

Библиотека дает возможность работать с операторами сравнения. Equal_to<T> — это функциональный объект. Это адаптируемый бинарный предикат или функциональный объект, который проверяет истинность или ложность некоторого условия. Если f — объект класса equal_to<T>, а x и y — объекты класса T, то f(x,y) возвращает значение true, если x == y, и значение false в противном случае.

vector<int> V;
...
partition(V.begin(), V.end(), bind2nd(equal_to<int>(), 0));

Контейнеры

Контейнеры в C++ STL — это универсальные классы, которые предоставляют различные способы хранения коллекций объектов и управления ими. Доступно несколько классов контейнеров. Это векторы, списки, очереди, стеки, наборы, карты(map). Каждый контейнер имеет свои собственные характеристики и сценарии использования. Рассмотрим последовательные и ассоциативные контейнеры.

Последовательности 

Последовательные контейнеры позволяют нам хранить элементы, к которым можно обращаться в последовательном порядке.

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

Типы последовательных контейнеров:

• массив;
• вектор;
• очередь;
• список;
• список пересылки.

Использование класса vector для демонстрации работы последовательного контейнера:

А#include <iostream>
#include <vector>
using namespace std;

int main() {

  // initialize a vector of int type
  vector<int> numbers = {1, 100, 10, 70, 100};

  // print the vector
  cout << "Numbers are: ";
  for(auto &num: numbers) {
    cout << num << ", ";
  }

  return 0;
}

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

Ассоциативные контейнеры позволяют хранить элементы в отсортированном порядке. Порядок не зависит от того, когда элемент был вставлен. Внутри они реализованы в виде структур данных в виде двоичного дерева.

Типы ассоциативных контейнеров:

• набор;
• карта;
• мультисеть;
• мультикарта.

Пример использования набора:

#include <iostream>
#include <set>
using namespace std;

int main() {

  // initialize a set of int type
  set<int> numbers = {1, 100, 10, 70, 100};

  // print the set
  cout << "Numbers are: ";
  for(auto &num: numbers) {
    cout << num << ", ";
  }

  return 0;
}

Алгоритмы 

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

Не меняющие последовательность операции 

Non-modifying algorithms в Standard Template:

• count
• equal
• mismatch
• search
• search_n

Меняющие последовательность операции

Алгоритмы модификации стандартной библиотеки шаблонов:

• copy and copy_n
• fill and fill_n
• move
• transform
• generate
• swap
• swap_ranges
• reverse
• reverse_copy
• rotate
• unique

Операции сортировки и отношения 

Sorting Algorithms или алгоритмы сортировки:

• sort — сортирует содержимое заданного диапазона;
• is_sorted — возвращает значение true, если заданный диапазон отсортирован;
• partial_sort — сортирует первую половину элементов в заданном диапазоне. Остальные половины элементов остаются такими, какими они были изначально.

Численные операции 

Числовые алгоритмы в стандартной библиотеке шаблонов:

• iota Method — присваивает всем последовательным элементам в диапазоне [first, last] возрастающее значение самого элемента;
• accumulate Method — выполняет операцию op над всеми элементами в диапазоне [first, last] и сохраняет результат в контейнере result;
• partial_sum Method — присваивает каждому элементу в диапазоне, начиная с результата итератора операции op в последовательном диапазоне в [first, last]. 

Адаптеры

Адаптер действует как оболочка между двумя объектами. Он перехватывает вызовы для одного объекта и преобразует их в формат и интерфейс, распознаваемые вторым объектом.

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

Библиотека реализует шаблоны классов, такие как stack, queue и priority_queue, в виде контейнера, который накладывает ограничения на процесс хранения и извлечения элементов. Адаптер контейнеров не обеспечивает реальной реализации структуры данных, в которой элементы сохраняются просто для хранения и извлечения. Он не поддерживает итераторы. 

Адаптеры итераторов 

Они упрощают работу с контейнерами. Адаптеры итераторов полезны в стандартных алгоритмах.

В каждом контейнере, который допускает обратную итерацию по элементам, уже есть нестатические функции-члены. Они возвращают обратные итераторы в начало и в конец — 'rbegin()' и 'rend()'. Программа, реализующая обратную итерацию по элементам:

#include <iostream>
#include <list>

int main()
{
  std::list<int> list { 1, 2, 3, 4, 5 };
  
  for (std::list<int>::reverse_iterator rIt = list.rbegin();
       rIt != list.rend();
       ++rIt)
  {
    std::cout << *rIt << " ";
  }

  return 0;
}

// output: 5 4 3 2 1

Адаптеры функций

Это функция стандартной библиотеки C++, которая позволяет изменять функциональные объекты. Она создает новые функции, которые, например, принимают меньше аргументов или изменяют свои аргументы.

С момента появления C++14 функциональные адаптеры часто заменялись на лямбда-выражения из-за их повышенной гибкости и лаконичности. Но функциональные адаптеры по-прежнему остаются актуальными в тех случаях, когда использование лямбда-выражения привело бы к созданию сложного или менее читаемого кода. Лямбда-выражения предлагают мощные и лаконичные решения, функциональный адаптер может обеспечить более структурированный подход. Он особенно полезен в более крупных и сложных программных системах.

Примеры применения STL 

Пример программы-шаблона функций на C++

Компилятор: Visual C++ Express Edition 2005

Скомпилирован на платформе: Windows XP Pro с пакетом обновления 2

Заголовочный файл: Стандартный

Дополнительная библиотека: отсутствует/по умолчанию

#include <iostream>
using namespace std;
 
// function template declaration and definition
template <class any_data_type>
any_data_type MyMax(any_data_type Var1, any_data_type Var2)
{
return Var1> Var2 ? Var1:Var2;
}
 
int main(void)
{
cout<<"MyMax(10,20) = "<<MyMax(10,20)<<endl;
cout<<"MyMax('Z','p') = "<<MyMax('Z','p')<<endl;
cout<<"MyMax(1.234,2.345) = "<<MyMax(1.234,2.345)<<endl;
 
// some logical error here?
cout<<"\nLogical error, comparing pointers instead of string..."<<endl;
char* p = "Function";
char* q = "Template";
cout<<"Address of *p = "<<&p<<endl;
cout<<"Address of *q = "<<&q<<endl;
cout<<"MyMax(\"Function\",\"Template\") = "<<MyMax(p,q)<<endl;
cout<<"Should use Specialization, shown later..."<<endl;
return 0;
}
 
Output examples:
 
MyMax(10,20) = 20
MyMax('Z','p') = p
MyMax(1.234,2.345) = 2.345
Logical error, comparing pointers instead of string...
Address of *p = 0012FF60
Address of *q = 0012FF54
MyMax("Function","Template") = Function
Should use Specialization, shown later...
Press any key to continue . . .