Don't repeat yourself!

Внимание. Приведённый ниже текст является конспектом лекции курса «Лингвистическое и программное обеспечение автоматизированных систем» и не может рассматриваться как самостоятельный учебник. Он служит исключительно для поддержки лекционного курса и без материала, излагаемого на лекции, не имеет самостоятельной ценности. Многие понятия изложены в упрощённой и конспективной форме и не раскрыты в полном объёме. Большая часть связующего материала опущена.

Библиотека STL

Стандартная библиотека шаблонов (Standard Template Library - STL) языка С++ объединяет в себе контейнерные типы данных, алгоритмы для их обработки данных, итераторы для обращения к элементам или последовательностям в контейнера. STL также содержит набор шаблонов для обеспечения стандартного ввода-вывода.

Слово «стандартная» обозначает, что данная библиотека является частью стандарта языка С++ и должна рассматриваться, как первая альтернатива при выборе методов и средств работы с данными и потоками ввода-вывода.

Слово «шаблонов» обозначает, что вся библиотека построена на шаблонах классов и функций, что обеспечивает возможность унифицированной работы с различными типами данных. Использование шаблонов в библиотеке позволяет не только одинаково обрабатывать встроенные типы С++, но и работать с пользовательскими типами данных, которые не были известны в момент разработки библиотеки.

STL обладает рядом преимуществ:

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

К недостаткам STL можно отнести:

• Неприспособленность к работе со структурными типами данных.
• Низкая эффективность (быстродействие, память) при решении частных задач, где возможны целевые оптимизации кода.
• Неадекватный интерфейс шаблона для работы со строками.
• Сложность управления пулом памяти при работе с контейнерами STL.

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

Контейнеры

Библиотека STL представляет ряд контейнеров для хранения данных, которые условно можно разделить на контейнеры с произвольным доступом, последовательные контейнеры и ассоциативные контейнеры

Контейнерами с произвольным доступом являются vector и deque. Оба контейнера обеспечивают произвольный доступ к элементам (как к элементам обычных массивов C++). Основное отличие vector и deque состоит в том, что vector обеспечивает добавление новых элементов в конце, а deque – в конце и в начале контейнера.

Пример использования контейнера vector

1
2
3
4
5
6
7
8
9
10
11
12
13

#include 
#include 

int main( )
{
   using namespace std;  
   vector  v1;
   
   v1.push_back( 10 );
   v1.push_back( 20 );
   
   cout << "The second integer of v1 is " << v1[1] << endl;
}

Контейнеры с произвольным доступом позволяют обращаться к элементу с помощью оператора []. Добавление элементов в vector производится с помощью метода push_back, добавляющего новый элемент в вектор. Использование элемента до его добавления (или резервирования) недопустимо.

Контейнером с последовательным доступом является list (связанный список).

Также есть контейнеры, определяющие приоритетную очередь (priority_queue) и стек (stack).

Ассоциативные контейнеры представлены словарём (map, multimap) и набором (set, multiset), а также их аналогами, реализованным с использованием хеш-таблиц.

Ассоциативные контейнеры позволяют хранить данные в упорядоченном виде и обеспечивают быстрый поиск нужных значений по ключу. К примеру, set позволяет хранить наборы уникальных (по значению) объектов. А multiset позволяет хранить повторяющиеся объекты. Контейнер map позволяет хранить словарь пар ключ-значение и осуществлять быстрый поиск нужного элемента по ключу.

Строки

Шаблон sting реализует функционал, необходимый для работы со строками текста.

В отличии от стандартного представления строки в виде массива символов константной длинны шаблон string динамически распределяет память для строки в пуле и гарантирует достаточный объём памяти при любых операциях со строками: вводе, слиянии строк и т.д.

Шаблон обеспечивает освобождение памяти, занятого строковым объектом, после того, как он станет не нужен. Методы шаблона обеспечивают все необходимые алгоритмы работы со строками: поиск, замену, вставку, сравнение. Использование шаблона string значительно упрощает работу со строками для начинающего программиста.

Итераторы

Итераторы используются для доступа к элементам контейнеров также, как указатели используются для доступа к элементам массивов в С++. Итератор является «умным» указателем на элемент контейнера. В отличие от обычного указателя он помнит полный тип данных на который ссылается – с учётом типа контейнера, к элементу которого производится обращение.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

struct Circle {
  Circle() : radius(0) {}
  Circle(float radius) : radius(radius) {}
  float radius;
};

int main()
{
  using namespace std;
  
  Circle c1(10),c2(20);
  map circles;
  circles["one"]=c1;
  circles["two"]=c2;
  
  map::iterator it = circles.begin();
  map::const_iterator end = circles.end();
  for ( ; it != end; ++it) {
    cout << "NameIs: " << (it->first) << endl;
    cout << "Radius: " << (it->second).radius << endl;
  }
}

Большинство контейнерных типов предоставляют два специальных метода – begin и end. Метод begin возвращает итератор, указывающий на первый элемент контейнера. Метод end возвращает итератор на элемент контейнера, следующий за последним. Нельзя обращаться к элементу, на который указывает итератор, возвращаемый по end. Он служит лишь для ограничения действия алгоритмов.

Итераторы бывают нескольких типов – входные, выходные, прямые, двунаправленные и произвольного доступа. Тип итератора определяет подмножество операторов, применимых к нему. Например, итератор произвольного доступа поддерживает возможность добавления определённого смещения (i+n), в то время, как другие итераторы позволяют только операции смещения итератора на одну позицию i++ или ++i. Двунаправленные итераторы позволяют перемещаться и в обратном направлении (i-- и --i).

Как и в случае с указателями – основная операция, применяемая к итератору – разыменование. То есть обращение к объекту, на который указывает итератор.

Алгоритмы

Библиотека STL предоставляет основные виды алгоритмов:

• Математические (расчёт сумм, произведений, генерация случайных значений)
• Поиска (минимальное значение, поиск последовательности, подсчёт числа значений)
• Сортировки
• Работы с последовательностями (объединение последовательностей, сравнения, обработки последовательности типовой операцией)

Пример использования алгоритма

1
2
3
4
5
6
7
8
9
10
11
12

#include 
#include 

int main()
{
  using namespace std;
  
  const int n=4;
  int a[n];
  generate(a,a+n,rand);
  copy(a,a+n,ostream_iterator(cout," "));
}

Предикаты, функторы и адаптеры

Функтором (или функциональным объектом) называется любой объект, к которому можно применить оператор вызова функции - operator(). Такой вызов в С++ применим к имени функции, указателю на функцию или объекту класса, который переопределяет operator().

Предикатом называется функция (или функциональный объект), которая в зависимости от значения аргументов может возвращать либо true, либо false.

Пример предиката

1
2
3

bool is_greater_than(int arg1,int arg2) {
  return arg1 > arg2;
}

Используя данный предикат можно переопределять стандартное поведение алгоритмов STL:

Использование предиката

1
2
3
4

  const int n=4;
  int a[n]= {9,7,3,4};
  std::sort(a,a+n, is_greater_than);
  std::copy(a,a+n,std::ostream_iterator(std::cout," "));

Данный код позволяет изменить порядок сортировки с «неубывания» на «невозрастание».

Вместо использования собственного предиката можно воспользоваться стандартным предикатом STL:

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

1
2
3
4

  const int n=4;
  int a[n]= {9,7,3,4};
  std::sort(a,a+n, greater());
  std::copy(a,a+n, std::ostream_iterator( std::cout," "));

В случае поиска необходимого элемента возникает необходимость хранить элемент. Например, частное решение с «прошитым» в коде элементом может выглядеть так:

Предикат сравнения

1
2
3

bool is_greater_than_7(int x) {
  return x > 7;
}

Тогда код вызова STL может выглядеть так:

Использование предиката сравнения

1
2
3
4

const int n=4;
int a[n]= {9,7,3,4};
int* it = std::find_if(a,a+n, is_greater_than_7);
std::cout << *it;

Если мы не хотим «прошивать» значение в классе и хотим предоставить возможность задавать его при вызове алгоритма, то необходимо его запомнить. Для этого делается класс-функтор:

Класс-функтор

1
2
3
4
5
6
7
8

class GreaterThan {
  int limit;
public:
  GreaterThan(int limit) : limit(limit) {}
  bool operator()(int x) {
    return x > limit;
  }
};

Тогда уже возможно задавать искомый лимит при вызове:

Использование класса-функтора

1
2
3
4

const int n=4;
int a[n]= {2,9,7,3};
int* it = std::find_if(a,a+n,GreaterThan(7));
std::cout << *it;

Для решения той же задачи можно было использовать стандартный адаптер STL, позволяющий связывать алгоритм и значение:

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

1
2
3
4

const int n=4;
int a[n]= {2,9,7,3};
int* it = std::find_if(a,a+n,std::bind2nd(std::greater(),7));
cout << *it;

Прочее

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

Это организация ввода-вывода с использованием стандартных потоков, использование числовых типов (например, комплексных), пределов (limits) и т.д.

Рекомендуемая литература

Пример программы с использованием STL

Подсчёт числа слов в тексте

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

#include "stdafx.h"
#include 
#include 
#include 
#include