Джесс Либерти - Освой самостоятельно С++ за 21 день.

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

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

Подобно классу stack, класс queue реализован как класс оболочки контейнера. Контейнер должен поддерживать такие функции, как front(), back(), push_back() и pop_front().

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

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

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

Листинг 19.10. Класс-контейнер map

1: #include

2: #include

3: #include

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

75: void ShowMap(const map& v); // отображает свойства карты

76:

77: typedef map 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 old\n";

97:

98: return 0;

99: }

100:

101: //

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

103: //

104: template

105: void ShowMap(const map& v)

106: {

107: for (map::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. Для отображения элементов карты определяется шаблонная функция 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"].

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

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

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

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