Стеки
Одной из самых распространенных в программировании структур данных является стек. Однако стек не используется как независимый контейнерный класс, скорее, его можно назвать оболочкой контейнера. Шаблонный класс stack определен в файле заголовка <stack> в пространстве имен std.
Стек — это непрерывный выделенный блок памяти, который может расширяться или сжиматься в хвостовой части, т.е. к элементам стека можно обращаться или удалять только с одного конца. Вы уже видели подобные характеристики в последовательных контейнерах, особенно в классах vector и deque. Фактически для реализации стека можно использовать любой последовательный контейнер, который поддерживает функции back(), push_back() и pop_back(). Большинство других методов контейнеров для работы стека не используются, поэтому они и не предоставляются классом stack.
Базовый шаблонный класс stack библиотеки STL шаблона разработан для поддержания объектов любого типа. Единственное ограничение состоит в том, что все элементы должны иметь один и тот же тип.
Данные в стеке организованы по принципу "последним вошел — первым вышел". Ее можно сравнить с переполненным лифтом: первый человек, вошедший в лифт, припирается к стене, а последний втиснувшийся стоит прямо у двери. Когда лифт поднимается на указанный кем-то из пассажиров этаж, тот, кто зашел последним, должен выйти первым, Если кто-нибудь (из стоящих посередине пассажиров) захочет выйти из лифта раньше других, то все, кто находится между ним и дверью, должны выйти из лифта, выпустив его, а затем вернуться обратно.
Открытый конец стека называется вершиной стека, а действия, выполняемые с элементами стека, — операциями помещения (push) и выталкивания (pop) из стека. Для класса stack эти общепринятые термины остаются в силе.
Примечание:Класс stack из библиотеки STL не соответствует стекам памяти, используемым компиляторами и операционными системами, которые могут содержать объекты различных типов, хотя они работают сходным образом.
Очередь
Очередь — это еще одна распространенная в программировании структура данных. В этом случае элементы добавляются к очереди с одного конца, а вынимаются с другого. Приведем классическую аналогию. Вспомним стек. Его можно сравнить со стопкой тарелок на столе. При добавлении в стек тарелка ставится сверху всей стопки (помещение в стек), и взять тарелку из стопки (стека) можно тоже только сверху (выталкивание из стека), т.е. берется тарелка, которая была положена в стопку самой последней.
Очередь же можно сравнить с любой очередью людей, например при входе в театр. Вы занимаете очередь сзади, а покидаете ее спереди. Конечно, каждому из нас приходилось стоять предпоследним в какой-нибудь очереди (например, в магазине), когда вдруг начинает работать еще одна касса, к которой подбегает стоявший за вами, что скорее напоминает стек, чем очередь. Но в компьютерах такого не случается.
Подобно классу stack, класс queue реализован как класс оболочки контейнера. Контейнер должен поддерживать такие функции, как front(), back(), push_back() и pop_front().
Ассоциативные контейнеры
Тогда как последовательные контейнеры предназначены для последовательного и произвольного доступа к элементам с помощью индексов или итераторов, ассоциативные контейнеры разработаны для быстрого произвольного доступа к элементам с помощью ключей. Стандартная библиотека C++ предоставляет четыре ассоциативных контейнера: карту, мульти карту, множество и мультимножество.
Карта
Вектор можно сравнить с расширенной версией массива. Он имеет все характеристики массива и ряд дополнительных возможностей. К сожалению, вектор также страдает от одного из существенных недостатков массивов: он не предоставляет возможности для произвольного доступа к элементам с помощью ключа, а лишь использует для этого индекс или итератор. Ассоциативные контейнеры как раз обеспечивают быстрый произвольный доступ, основанный на ключевых значениях.
В листинге 19.10 для создания списка студентов, который мы рассматривали в листинге 19.8, используется карта.
Листинг 19.10. Класс-контейнер map
1: #include <iostream>
2: #include <string>
3: #include <map>
4: using namespace std;
5:
6: class Student
7: {
8: public:
9: Student();
10: Student(const string& name, const int age);
11: Student(const Student& rhs);
12: ~Student();
13:
14: void SetName(const string& namе);
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
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 Student::GetAge() 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: ostream& 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, class A>
75: void ShowMap(const map<T, A>& v); // отображает свойства карты
76:
77: typedef map<string, Student> SchoolClass;
78:
79: int main()
80: {
81: Student Harry("Harry", 18);
82: Student Sally("Sally", 15);
83: Student Bill("Bill", 17);
84: Student Peter("Peter", 16);
85:
86: SchoolClassMathClass;
87: MathClass[Harry.GetName() ] = Harry;
88: MathClass[Sally.GetName()] = Sally;
89: MathClass[Bill.GetName() ] = Bill;
90: MathClass[Peter.GetName()] = Peter;
91:
92: cout << "MathClass;n";
93: ShowMap(MathClass);
94:
95: cout << "We know that " << MathClass["Bill"].GetName()
96: << " is " << MathClass["Bill"].GetAge() << "years oldn";
97:
98: return 0;
99: }
100:
101: //
102: // Отображает свойства карты
103: //
104: template<class T, class A>
105: void ShowMap(const map<T, А>& v)
106: {
107: for (map<T, A>::const_iterator ci = v.begin();
108: ci != v.end(); ++ci)
109: cout << ci->first << ": " << ci->second << "n";
110:
111: cout << endl;
112: }
Результат:
MathClass:
Bill: Bill is 17 years old
Harry: Harry is 18 years old
Peter: Peter is 16 years old
Saily: Sally is 15 years old
We know that Bill is 17 years old
Анализ: В строке 3 в программу добавляется файл заголовка <map>, поскольку будет использоваться стандартный класс-контейнер map. Для отображения элементов карты определяется шаблонная функция ShowMap. В строке 77 класс SchoolClass определяется как карта элементов, каждый из которых состоит из пары (ключ, значение). Первая составляющая пары — это значение ключа. В нашем классе SchoolClass имена студентов используются в качестве ключевых значений, которые имеют тип string. Ключевое значение элемента в контейнере карты должно быть уникальным, т.е. никакие два элемента не могут иметь одно и то же ключевое значение. Вторая составляющая пары — фактический объект, в данном примере это объект класса Student. Парный тип данных реализован в библиотеке STL как структура (тип данных struct), состоящая из двух членов, а именно: first и second. Эти члены можно использовать для получения доступа к ключу и значению узла.
Пропустим пока функцию main() и рассмотрим функцию StwtMap, которая открывает доступ к объектам карты с помощью константного итератора. Выражение ci->first (строка 109) указывает на ключ (имя студента), а выражение ci->second — на объект класса Student.
В строках 81-84 создаются четыре объекта класса Student. Класс MathClass определяется как экземпляр класса SchoolClass (строка 86), а в строках 87-90 уже имеющиеся четыре студента добавляются в класс MathClass:
map_object[key_value] = object_value;
Для добавления в карту пары ключ—значение можно было бы также использовать функции push_back() или insert() (за более подробной информацией обратитесь к документации, прилагаемой к вашему компилятору).
После добавления к карте всех объектов класса Student можно обращаться к любому из них, используя их ключевые значения. В строках 95 и 96 для считывания записи, относящейся к студенту Биллу (объекту Bill), используется выражение MathClass["Bill"].
Другие ассоциативные контейнеры
Класс-контейнер мультикарты — это класс карты, не ограниченный уникальностью ключей. Это значит, что одно и то же ключевое значение могут иметь не один, а несколько элементов.
