Другие ассоциативные контейнеры

Класс-контейнер мультикарты — это класс карты, не ограниченный уникальностью ключей. Это значит, что одно и то же ключевое значение могут иметь не один, а несколько элементов.

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

Наконец, класс-контейнер мультимножества — это класс множества, который позволяет иметь несколько ключевых значений.

Классы алгоритмов

Контейнер — это удобное место для хранения последовательности элементов. Все стандартные контейнеры содержат методы управления контейнерами и их элементами. Однако манипулирование собственными данными в программах с помощью этих методов может потребовать от программиста написания обширного программного кода, что чревато появлением ошибок. Но поскольку большинство операций, выполняемых над данными, рутинны и повторяются от программы к программе, то подборка универсальных алгоритмов может существенно облегчить написание программ обработки данных контейнера. Стандартная библиотека предоставляет около 60 стандартных алгоритмов, которые выполняют большинство базовых и часто используемых операций, характерных для контейнеров.

Стандартные алгоритмы определены в файле <algorithm> в пространстве имен std.

Чтобы понять, как работают стандартные алгоритмы, необходимо познакомиться с понятием объектов функций. Объект функции — это экземпляр класса, в котором определен перегруженный оператор вызова функции(). В результате этот класс может вызываться как функция. Использование объекта функции показано в листинге 19.11.

Листинг 19.11. объект функции

1: #include <iostream>

2: using namespace std;

3:

4: template<class T>

5: class Print {

6: public:

7: void operator()(const T& t)

8: {

9: cout << t << " ";

10: }

11: };

12:

13: int main()

14: {

15: Print<int> DoPrint;

16: for (int i = 0; i < 5; ++i)

17: DoPrint(i);

18: return 0;

19: }

Результат: 0 1 2 3 4

Анализ: В строках 4—11 определяется шаблонный класс Print. Перегруженный в строках 7—10 оператор вызова функции () принимает объект и перенаправляет его в стандартный поток вывода. В строке 15 определяется объект DoPrint как экземпляр класса Print. После этого, чтобы вывести на печать любые целочисленные значения, объект DoPrint можно использовать подобно обычной функции, как показано в строке 17.

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

Операции, не изменяющие последовательность данных в структуре, реализуются с помощью таких функций, как for_each() и find(), search(), count() и т.д. В листинге 19.12 показан пример использования объекта функции и алгоритм for_each, предназначенный для печати элементов вектора.

Листинг 18.12. Использование алгоритма for_each()

1: #include <iostream>

2: #include <vector>

3: #include <algorithm>

4: using namespace std;

5:

6: template<class T>

7: class Print

8: {

9: public:

10: void operator()(const T& t)

11: {

12: cout << t << " ";

13: }

14: };

15:

16: int main()

17: {

18: Print<int> DoPrint;

19: vector<int> vInt(5);

20:

21: for (int i = 0; i < 5; ++i)

22: vInt[i] = i * 3;

23:

24: cout << "for_each()\n";

25: for_each(vInt.begin(), vInt.end(), DoPrint);

26: cout << "\n";

27:

28: return 0;

29: }

Результат:

for_each()

0 3 6 9 12

Анализ: Обратите внимание, что все стандартные алгоритмы C++ определены в файле заголовка <algorithm>, поэтому следует включить его в нашу программу. Большая часть программы не должна вызывать никаких трудностей. В строке 25 вызывается функция for_each(), чтобы опросить каждый элемент в векторе vInt. Для каждого элемента она вызывает объект функции DoPrint и передает этот элемент оператору DoPrint.operator(), что приводит к выводу на экран значения данного элемента.

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

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

Листинг 19.13. Алгоритм изменения последовательности

1: #include <iostream>

2: #include <vector>

3: #include <algorithm>

4: using namespace std;

5:

6: template<class T>

7: class Print

8: {

9: public:

10: void operator()(const T& t)

11: {

12: cout << t << " ";

13: }

14: };

15:

16: int main()

17: {

18: Print<int> DoPrint;

19: vector<int> vInt(10);

20:

21: fill(vInt.begin(), vInt.begin()+5, 1);

22: fill(vInt.begin() + 5, vInt.end(), 2);

23:

24: for_each(vInt.begin(), vInt.end(), DoPrint);

25: cout << "\n\n";

26:

27: return 0;

28: }

Результат: 1 1 1 1 1 2 2 2 2 2

Анализ: Единственная новая деталь в этом листинге содержится в строках 21 и 22, где используется алгоритм fill(). Алгоритм заполнения предназначен для заполнения элементов последовательности заданным значением. В строке 21 целое значение 1 присваивается первым пяти элементам в векторе vInt. А последним пяти элементам вектора vInt присваивается целое число 2 (в строке 22).

Резюме

Сегодня вы узнали, как создавать и использовать шаблоны — встроенное средство языка C++, используемое для создания параметризованных типов, т.е. типов, которые изменяют свое выполнение в зависимости от параметров, переданных при создании класса. Таким образом, шаблоны - это возможность многократного использования программного кода, причем безопасным и эффективным способом,

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

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

Если нужно специализировать выполнение функции шаблона в зависимости от типа, то ее можно замещать для разных типов.

Вопросы и ответы

Чем использование шаблонов лучше использования макросов?

Шаблоны обеспечивают более безопасное использование разных типов и встроены в язык.

Какова разница между параметризованным типом функции шаблона и параметрами обычной функции?

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

Когда следует использовать шаблоны, а когда наследование?

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

Когда использовать дружественные шаблонные классы и функции?

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

Когда использовать дружественные шаблонные классы или функции, специализированные по типу?

Когда между двумя классами нужно установить отношения по типу один-к-одному. Например, массив array<lnt> должен соответствовать итератору iterator<int>, но не iterator<Animal>.

Каковы два типа стандартных контейнеров?

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

Какими атрибутами должен обладать класс, чтобы его можно было использовать со стандартными контейнерами?

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

Коллоквиум

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

Контрольные вопросы

1. Какова разница между шаблоном и макросом?

2. В чем состоит отличие параметра шаблона от параметра функции?

3. Чем отличается обычный дружественный шаблонный класс от дружественного шаблонного класса, специализированного по типу?

4. Можно ли обеспечить особое выполнение для определенного экземпляра шаблона?

5. Сколько статических переменных-членов будет создано, если в определение класса шаблона поместить один статический член?

6. Что представляют собой итераторы?

7. Что такое объект функции?

Упражнения

1. Создайте шаблон на основе данного класса List:

class List

{

public:

List():head(0),tail(0),theCount(0) { }

virtual ~List();

void insert( int value );

void append( int value );

int is_present( int value ) const;

int is_empty() const { return head == 0; }

int count() const { return theCount; }

private:

class ListCell

{

public:

ListCell(int value, ListCell *cell = ):val(value),next(cell){ }

int val;

ListCell *next;

};

ListCell *head;

ListCell *tail;

int theCount;

};

2. Напишите выполнение обычной (не шаблонной) версии класса List.

3. Напишите шаблонный вариант выполнения.

4. Объявите три списка объектов: типа Strings, типа Cat и типа int.

5. Жучки: что неправильно в приведенном ниже программном коде? (Предположите, что определяется шаблон класса List, а Cat — это класс, определенный на одном из предыдущих занятий.)

List<Cat> Cat_List;

Cat Felix;

CatList.append( Felix );

cout << "Felix is " << ( Cat_List.is_present( Felix ) ) ? "" : "not " << "present\n";

6. ПОДСКАЗКА (поскольку задание не из самых легких): подумайте, чем тип Cat отличается от типа int?

7. Объявите дружественный оператор operator== для класса List.

8. Напишите выполнение дружественного оператора operator== для класса List.

9. Грешит ли оператор operator== той же проблемой, которая существует в упражнении 5?

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

11. Напишите выполнение класса SchoolClass, показанного в листинге 19.8, как списка. Для добавления в список четырех студентов используйте функцию push_back(). Затем пройдитесь по полученному списку и увеличьте возраст каждого студента на один год.

12. Измените код из упражнения 10 таким образом, чтобы для отображения данных о каждом студенте использовался объект функции.