Стандартная библиотека шаблонов

 

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

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

 

Контейнеры

 

Контейнер — это объект, который содержит другие объекты. Стандартная библиотека C++ предоставляет ряд классов-контейнеров, являющихся мощными инструментальными средствами, которые помогают разработчикам C++ решать наиболее общие задачи программирования. Среди классов контейнеров стандартной библиотеки шаблонов (STL) различаются два типа: последовательные и ассоциативные. Последовательные контейнеры предназначены для обеспечения последовательного или произвольного доступа к своим членам, или элементам. Ассоциативные контейнеры оптимизированы таким образом, чтобы получать доступ к своим элементам по ключевым значениям. Подобно другим компонентам стандартной библиотеки C++, библиотека STL совместима с различными операционными системами. Все классы-контейнеры библиотеки STL определены в пространстве имен std.

 

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

 

Такие контейнеры стандартной библиотеки шаблонов обеспечивают эффективный последовательный доступ к списку объектов. Стандартная библиотека C++ предоставляет три вида последовательных контейнеров: векторы, списки и двухсторонние очереди.

Вектор

 

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

Вектор — это контейнер, оптимизированный таким образом, чтобы обеспечить быстрый доступ к его элементам по индексу. Класс-контейнер vector определен в файле заголовка <vector> в пространстве имен std (подробнее об использовании пространств имен см. главу 17). Вектор можно наращивать по мере необходимости. Предположим, был создан вектор для 10 элементов. После того как в вектор поместили 10 объектов, он оказался целиком заполненным. Если затем к вектору добавить еще один объект, он автоматически увеличит свою вместимость так, что сможет разместить одиннадцатый объект. Вот как выглядит определение класса vector:

template <class T, class А = allocator<T>> class vector

{

// члены класса

};

Первый аргумент (class T) означает тип элементов в векторе. Второй аргумент (class А) — это класс распределения, который берет на себя функции диспетчера памяти, ответственного за распределение и освобождение памяти для элементов контейнеров. Принципы построения и выполнения классов распределения затрагивают более сложные темы, которые выходят за рамки этой книги.

По умолчанию элементы создаются с помощью оператора new() и освобождаются с помощью оператора delete(), т.е. для создания нового элемента вызывается стандартный конструктор класса Т. Это служит еще одним аргументом в пользу явного определения стандартного конструктора для ваших собственных классов. Если этого не сделать, то нельзя будет использовать стандартный векторный контейнер для хранения объектов пользовательского класса.

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

vector<int> vInts; // вектор для хранения целых элементов

vector<float> vFloats; // вектор для хранения вещественных элементов

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

vector<Student> MathClass(50);

Компилятор автоматически выделит достаточный объем памяти для хранения записей о 50 студентах. Каждый элемент вектора создается с использованием стандартного конструктора Student::Student().

Количество элементов в векторе можно узнать с помощью функции-члена size(). В данном примере функция-член vStudent.size() возвратит значение 50.

Другая функция-член, capacity(), сообщает, сколько в точности элементов может принять вектор, прежде чем потребуется увеличение его размера. Но об этом речь впереди.

Вектор называется пустым, если он не содержит ни одного элемента, т.е. если его размер равен нулю. Чтобы определить, не является ли вектор пустым, в классе вектора предусмотрена функция-член empty(), которая принимает значение, равное истине, если вектор пустой.

Чтобы записать студента Гарри на курс прикладной математики, т.е. (говоря языком программирования) чтобы назначить объект Harry класса Student вектору MathClass, можно использовать оператор индексирования ([]):

MathClass[5] = Harry;

Индексы начинаются с нуля. Для назначения объекта Harry шестым элементом вектора MathClass здесь используется перегруженный оператор присваивания класса Student. Аналогично, чтобы определить возраст объекта Harry, можно получить доступ к соответствующей записи, используя следующее выражение:

MathClass[5].GetAge();

Как упоминалось выше, при добавлении в вектор большего числа элементов, чем было указано при создании вектора, дополнительное место для нового элемента будет добавлено автоматически. Предположим, курс прикладной математики стал таким популярным, что количество принятых студентов превысило число 50. Возможно, за 51- го студента кто-то замолвил словечко, и декану не осталось ничего другого, как увеличить число студентов на курсе. Так вот, если на курс (в вектор MathClass) захочет записаться 51-я студентка Салли (объект Sally), компилятор спокойно расширит пределы вектора, чтобы "впустить" новое молодое дарование.

Добавлять элемент в вектор можно различными способами. Один из них — с помощью функции-члена push_back():

MathClass.push_back(Sally);

Эта функция-член добавляет новый объект Sally класса Student в конец вектора MathClass. И теперь в векторе MathClass содержится уже 51 элемент, причем к объекту Sally можно обратиться по индексу MathClass[50].

Чтобы функция push_back() была работоспособной, в классе Student нужно определить конструктор-копировщик. В противном случае эта функция не сможет создать копию объекта Sally.

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

В листинге 19.8 демонстрируется использование векторного класса. Вы увидите, что для упрощения обработки строк в этом листинге используется стандартный класс string. Для получения более подробной информации о классе string обратитесь к документации, прилагаемой к вашему компилятору.

Листинг 13.8. Создание вектора и обеспечение доступа к его элементам

1: #include <iostream>

2: #include <string>

3: #include <vector>

4: using namespace std;

5:

6: class Student

7: {

8: public:

9: Student();

10: Student(const string& name, const int аде);

11: Student(const Student& rhs);

12: ~Student();

13:

14: void SetName(const string& name);

15: string GetName() const;

16: void SetAge(const int age);

17: int GetAge() const;

18:

19: Student& operator=(const Student& rhs);

20:

21: private:

22: string itsName;

23: int itsAge;

24: };

25:

26: Student::Student()

27:: itsName("New Student"), itsAge(16)

28: { }

29:

30: Student::Student(const string& name, const int agе)

31:: itsName(name), itsAge(age)

32: { }

33:

34: Student::Student(const Student& rhs)

35:: itsName(rhs.GetName()), itsAge(rhs.GetAge())

36: { }

37:

38: Student::~Student()

39: { }

40:

41: void Student::SetName(const string& name)

42: {

43: itsName = name;

44: }

45:

46: string Student::GetName() const

47: {

48: return itsName;

49: }

50:

51: void Student::SetAge(const int age)

52: {

53: itsAge = age;

54: }

55:

56: int Studsnt::GitAge() const

57: {

58: return itsAge;

59: }

60:

61: Student& Student::operator=(const Student& rhs)

62: {

63: itsName = rhs,GetName();

64: itsAge = rhs.GetAge();

65: return *this;

66: }

67:

68: stream& operator<<(ostream& os, const Student& rhs)

69: {

70: os << rhs.GetName() << " is " << rhs.GetAge() << " years old";

71: return os;

72: }

73:

74: template<class T>

75: void ShowVector(const vector<T>& v); // Отображает свойства вектора

76:

77: typedef vector<Student> SchoolClass;

78:

79: int main()

80: {

81: Student Harry;

82: Student Sally("Sally", 15);

83: Student Bill("Bill", 17);

84: Student Peter("Peter", 16);

85:

86: SchoolClass EmptyClass;

87: cout << "EmptyClass:\n";

88: ShowVector(EmptyClass);

89:

90: SchoolClass GrowingClass(3);

91: cout << "GrowingClass(3):\n";

92: ShowVector(GrowingClass);

93:

94: GrowingClass[0] = Harry;

95: GrowingClass[1] = Sally;

96: GrowingClass[2] = Bill;

97: cout << "GrowingClass(3) after assigning students:\n";

98: ShowVector(GrowingClass);

99:

100: GrowingClass.push_back(Peter);

101: cout << "GrowingClass() after added 4th student:\n";

102: ShowVector(GrowingClass);

103:

104: GrowingClass[0].SetName("Harry");

105: GrowingClass[0].SetAge(18);

106: cout << "GrowingClass() after Set\n:";

107: ShowVector(GrowingClass);

108:

109: return 0;

110: }

111:

112: //

113: // Отображает свойства вектора

114: //

115: template<class T>

116: void ShowVector(const vector<T>& v)

117: {

118: cout << "max_size() = " << v,max_size();

119: cout << "\tsize() = " << v,size();

120: cout << "\tcapaeity() = " << v,capacity();

121: cout << "\t" << (v.empty()? "empty": "not empty");

122: cout << "\n";

123:

124: for (int i = 0; i < v.size(); ++i)

125: cout << v[i] << "\n";

126:

127: cout << endl;

128: }

129:

 

Результат:

EmptyClass:

max_size() = 214748364 size() capacity() = 0 empty

GrowingClass(3):

max_size() = 214748364 size() capacity() = 3 not empty

New Student is 16 years old

New Student is 16 years old

New Student is 16 years old

GrowingClass(3) after assigning students:

max_size() = 214748364 size() = 3 capacity() = 3 not empty

New Student is 16 years old

Sally is 15 years old

Bill is 17 years old

GrowingClass() after added 4th student:

max_size() = 214748364 size() = 4 capacity() = 6 not empty

New Student is 16 years old

Sally is 15 years old

Bill is 17 years old

Peter is 16 years old

GrowingClass() after Set:

max_size() = 214748364 size() = 4 capacity() = 6 not empty

Harry is 18 years old

Sally is 15 years old

Bill is 17 years old

Peter is 16 years old

 

Анализ: Определение класса Student занимает строки 6—24, а выполнение его функций-членов показано в строках 26—66. Структура этого класса проста и дружественна по отношению к классу vector. По рассмотренным ранее причинам были определены стандартный конструктор, конструктор-копировщик и перегруженный оператор присваивания. Обратите внимание, что переменная-член itsName определена как экземпляр базового строкового класса C++ string. Как видите, со строками в C++ намного проще работать, подобное было в языке С (с типом char>>).

Функция шаблона ShowVector() объявлена в строках 74—75 и определена в строках 115-128. Она используется для вызова функций-членов вектора, отображающих его свойства: max_size(), size(), capacity() и empty(). Насколько можно судить по результатам работы этой программы, максимальное число объектов класса Student, которое может принять этот вектор, в Visual C++ составляет 214 748 364. Для других типов элементов это число может быть другим. Например, вектор целых чисел может вместить до 1 073 741 823 элементов. Если же вы используете другие компиляторы, то максимальное число элементов у вас может отличаться от приведенных здесь значений.

В строках 124 и 125 выполняется цикл, опрашивающий все элементы вектора и отображающий их значения, используя оператор вывода (<<), который перегружен в строках 68—72.

В строках 81—84 создаются четыре объекта класса Student. В строке 86 с помощью стандартного конструктора векторного класса определяется пустой вектор с именем EmptyClass. Когда вектор создается таким способом, то компилятор для него совсем не выделяет места в памяти. Как видно по результатам работы функции ShowVector(EmptyClass), как размер, так и вместимость этого вектора равны нулю.

Строка 90 содержит определение вектора для включения трех объектов класса Student. Размер и вместимость этого вектора, как и ожидалось, равны трем. В строках 94—96 с помощью оператора индексирования ([]) элементы вектора GrowingClass заполняются объектами класса Student.

В строке 100 к вектору добавляется четвертый студент (Peter). Это увеличивает размер вектора до четырех элементов. Интересно, что его вместимость теперь установлена равной шести. Это означает, что компилятор автоматически выделил достаточно пространства, которого хватит даже для шести объектов класса Student. Поскольку векторам должен быть выделен непрерывный блок памяти, для их расширения требуется выполнить целый ряд операций. Сначала выделяется новый блок памяти, достаточно большой для всех четырех объектов класса Student. Затем в только что выделенную память копируются эти три элемента, а четвертый добавляется после третьего элемента. И наконец, исходный блок памяти возвращается в область динамического обмена. При большом количестве элементов в векторе процесс перераспределения и освобождения памяти может оказаться весьма длительным. Поэтому в целях сокращения вероятности выполнения таких дорогих (по времени) операций компилятор использует стратегию оптимизации. В данном примере, если сразу добавить к вектору еще один или два объекта, отпадает необходимость в дополнительных операциях, связанных с освобождением и перераспределением памяти.

В строках 104 и 105 вновь используется оператор индексирования ([]), чтобы изменить переменные-члены первого объекта в векторе GrowingClass.

 

Рекомендуется: Определяйте стандартный конструктор для класса, если его объекты будут содержаться в векторе. Определяйте конструктор-копировщик для такого класса. Определяйте для такого класса перегруженный оператор присваивания.

 

Класс-контейнер вектора имеет и другие функции-члены. Функция front() возвращает ссылку на первый элемент в списке, а функция back() — на последний. Функция at() работает подобно оператору индексирования ([]). Она более безопасна, поскольку проверяет, попадает ли переданный ей индекс в диапазон доступных элементов. Если адрес оказывается вне диапазона, эта функция генерирует исключение out_of_range. (Исключительные ситуации рассматриваются на следующем занятии.)

Функция insert() вставляет один или несколько узлов (элементов) в текущую позицию вектора. Функция Pop_back() удаляет из вектора последний элемент. Наконец, функция remove() удаляет из вектора один или несколько элементов.

 

Список

 

Список — это контейнер, разработанный для обеспечения оптимального выполнения частых вставок и удалений элементов.

Класс-контейнер библиотеки STL list определен в файле заголовка <list> в пространстве имен std. Класс list выполнен как двунаправленный связанный список, в котором каждый узел содержит указатели как на предыдущий, так и на последующий узел списка.

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

Итератор — это обобщение указателя. Чтобы отыскать узел, на который указывает итератор, его нужно разыменовывать. Использование итераторов для доступа к узлам списка демонстрируется в листинге 19.9.

Листинг 19.9. Навигация по списку с ппмощью итератора

1: #include <iostream>

2: #include <list>

3: using namespace std;

4:

5: typedef list<int> IntegerList;

6:

7: int main()

8: {

9: IntegerList intList;

10:

11: for (int i = 1; i <= 10; ++i)

12: intList.push_back(i * 2);

13:

14: for (IntegerList::const_iterator ci = intList.begin();

15: ci!= intList.end(); ++ci)

16: cout << *ci << " ";

17:

18: return 0;

19: }

 

Результат:

2 4 6 8 10 12 14 16 18 20

 

Анализ: В строке 9 объект intList определен как список целых чисел. В строках 11 и 12 с помощью функции push_back() в список добавляются первые 10 положительных четных чисел.

В строках 14-16 мы обращаемся к каждому узлу в списке, используя константный итератор. Константность указывает, что мы не собираемся изменять узлы с помощью этого итератора. Если бы мы хотели изменить узел, на который указывает итератор, пришлось бы использовать переменный итератор:

intList::iterator

Функция-член begin() возвращает итератор на первый узел списка. Оператор инкремента (++) можно использовать для перехода к итератору следующего узла. Функция-член end(), что может показаться странным, возвращает итератор на узел, расположенный за последним узлом списка. Часто метод end() используют для определения допустимых границ списка.

Разыменование итератора (для возвращения связанного с ним узла) происходит аналогично разыменованию указателя, как показано в строке 16.

Хотя понятие итератора было введено только при рассмотрении класса list, итераторы можно использовать и с векторными классами. В дополнение к функциям-членам, с которыми вы познакомились в векторном классе, базовый класс списка тоже представляет функции push_front() и pop_front(), которые работают точно так же, как и функции push_back() и pop_back(). Но вместо добавления и удаления элементов в конце списка, они добавляют и удаляют элементы в его начале.