Программирование. Принципы и практика использования C++ Исправленное издание - Бьёрн Страуструп

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

В узле могут храниться дополнительные данные, которые контейнер может использовать для поддержки баланса. Дерево считается сбалансированным, если каждый узел имеет примерно одинаковое количество наследников как слева, так и справа. Если дерево, состоящее из N узлов, сбалансировано, то для обнаружения узла необходимо просмотреть не больше log2N узлов. Это намного лучше, чем N/2 узлов в среднем, которые мы должны были бы просмотреть, если бы ключи хранились в списке, а поиск выполнялся с начала (в худшем случае линейного поиска нам пришлось бы просмотреть N узлов). (См. также раздел 21.6.4.)

Для примера покажем, как выглядит несбалансированное дерево.

Это дерево по-прежнему удовлетворяет критерию, требующему, чтобы ключ каждого узла был больше ключа левого подузла и меньше ключа правого.

left–>first<first && first<right–>first

И все же это дерево является несбалансированным, поэтому нам придется совершить три перехода, чтобы найти узлы Apple и Kiwi, вместо двух, как в сбалансированном дереве. Для деревьев, содержащих много узлов, эта разница может оказаться существенной, поэтому для реализации контейнеров map используются сбалансированные деревья.

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

template<class Key, class Value, class Cmp = less<Key> > class map

{

  // ...

  typedef pair<Key,Value> value_type; // контейнер map хранит

                                      // пары (Key,Value)

  typedef sometype1 iterator;         // указатель на узел дерева

  typedef sometype2 const_iterator;

  iterator begin();      // указывает на первый элемент

  iterator end();        // указывает на следующий за последним

                         // элемент

  Value& operator[](const Key& k); // индексирование

                                   // по переменной k

  iterator find(const Key& k);     // поиск по ключу k

  void erase(iterator p);          // удаление элемента, на который

                                   // указывает итератор p

  pair<iterator, bool> insert(const value_type&);

  // вставляет пару (key,value)

  // ...

};

Настоящий вариант контейнера определен в заголовке <map>. Можно представить себе итератор в виде указателя Node*, но при реализации итератора нельзя полагаться на какой-то конкретный тип.

Сходство интерфейсов классов vector и list (см. разделы 20.5 и B.4) очевидно. Основное отличие заключается в том, что при перемещении по контейнеру элементами теперь являются пары типа pair<Key,Value>. Этот тип является очень полезным в библиотеке STL.

template<class T1, class T2> struct pair {

  typedef T1 first_type;

  typedef T2 second_type;

  T1 first;

  T2 second;

  pair():first(T1()),second(T2()) { }

  pair(const T1& x,const T2& y):first(x),second(y) { }

  template<class U,class V>

    pair(const pair<U,V>& p):first(p.first), second(p.second) { }

};

template<class T1,class T2> pair<T1,T2> make_pair(T1 x, T2 y)

{

  return pair<T1,T2>(x,y);

}

Мы скопировали полное определение класса pair и его полезную вспомогательную функцию make_pair() из стандарта.

 

 При перемещении по контейнеру map элементы перебираются в порядке, определенном ключом. Например, если мы перемещаемся по контейнеру, описанному в примере, то получим следующий порядок обхода:

(Apple,7) (Grape,2345) (Kiwi,100) (Orange,99) (Plum,8) (Quince,0)

Порядок вставки узлов значения не имеет.

Операция insert() имеет странное возвращаемое значение, которое в простых программах, как правило, мы игнорируем. Это пара, состоящая из итератора, установленного на пару (ключ, значение), и переменной типа bool, принимающей значение true, если данная пара (ключ, значение) была вставлена с помощью вызова функции insert(). Если ключ уже был в контейнере, то вставка игнорируется и значение типа bool принимает значение false.

 

 Мы можем определить порядок обхода ассоциативного массива с помощью третьего аргумента (предикат Cmp в объявлении класса map). Рассмотрим пример.

map<string, double, No_case> m;

Предикат No_case определяет сравнение символов без учета регистра (см. раздел 21.8). По умолчанию порядок обхода определяется предикатом less<Key>, т.е. отношением “меньше”. 

21.6.3. Еще один пример ассоциативного массива

Для того чтобы оценить полезность контейнера map, вернемся к примеру с индексом Доу–Джонс из раздела 21.5.3. Описанный там код работает правильно, только если все веса записаны в объекте класса vector в тех же позициях, что и соответствующие имена. Это требование носит неявный характер и легко может стать источником малопонятных ошибок. Существует много способов решения этой проблемы, но наиболее привлекательным является хранение всех весов вместе с их тикером, например (“AA”,2.4808). Тикер — это аббревиатура названия компании. Аналогично тикер компании можно хранить вместе с ценой ее акции, например (“AA”,34.69). В заключение для людей, редко сталкивающихся с фондовым рынком США, мы можем записывать тикер вместе с названием компании, например (“AA”,“Alcoa Inc.”); иначе говоря, можем хранить три аассоциативных массива соответствующих значений.

Сначала создадим ассоциативный контейнер, содержащий пары (символ,цена).

map<string,double> dow_price;

  // Индекс Доу - Джонса (символ, цена);

  // текущие котировки см. на веб-сайте www.djindexes.com

dow_price["MMM"] = 81.86;

dow_price ["AA"] = 34.69;

dow_price ["MO"] = 54.45;

// ...

Ассоциативный массив, содержащий пары (символ, вес), объявляется так:

map<string,double> dow_weight; // Индекс Доу-Джонса (символ, вес)

dow_weight.insert(make_pair("MMM", 5.8549));

dow_weight.insert(make_pair("AA",2.4808));

dow_weight.insert(make_pair("MO",3.8940));

// ...

Мы использовали функции insert() и make_pair() для того, чтобы показать, что элементами контейнера map действительно являются объекты класса pair. Этот пример также иллюстрирует значение обозначений; мы считаем, что индексирование понятнее и — что менее важно — легче записывается.

Ассоциативный контейнер, содержащий пары (символ, название).

map<string,string> dow_name; // Доу-Джонс (символ, название)

dow_name["MMM"] = "3M Co.";

dow_name["AA"] = "Alcoa Inc.";

dow_name["MO"] = "Altria Group Inc.";

// ...

С помощью этих ассоциативных контейнеров можно легко извлечь любую информацию. Рассмотрим пример.

double alcoa_price = dow_price ["AAA"]; // считываем значения из