Ассоциативные контейнеры

Ассоциативные контейнеры

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

К ассоциативным контейнерам относят:

• map
• multimap
• set
• multiset

set

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

• уникальность значений элементов: никакие два элемента в set не эквивалентны по значению. multiset - похожий ассоциативный массив, который позволяет хранить эквивалентные элементы;
• ключом каждого элемента является его же значение;
• в каждый момент времени элементы в set отсортированы.

В реализации STL контейнер set определяется тремя шаблонными параметрами:

  template < class Key, class Compare = less<Key>, class Allocator = allocator<Key> > class set;

Где

• Key - тип элементов, хранимых в контейнере.
• Compare - Comparison class - класс, который по двум аргументам того же типа, что и тип элементов контейнера возвращает bool значение: comp(a,b) возвращает true, если элемент контейнера а меньше элемента b (comp - объект класса Comparison). Значение по умолчанию less<Key>, который возвращает то же самое, что и (a<b). Объекты set используют compare для определения позиции элемента в контейнере. Все элементы отсортированы в контейнере по этому принципу.
• Allocator - Тип объекта, который управляет моделью распределения памяти. Шаблонный класс для типа Key, указанный по умолчанию, определяет модель самого простого управления памятью.

  #include<set>    // в этом файле определены set и multiset

  using std::set;

  set<int> s;
  s.insert(10);    // добавление элемента в множество
  s.insert(20);
  s.insert(10);    // еще одно значение 10 в множество добавлено не будет
  s.size();        // вернет 2

Методы set, которые можно реализовать, чтобы улучшить время работы:

• insert возвращает пару

  std::pair<iterator, bool>
  

  (работает за log(n))

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

Элементу pair::first присваивается итератор, указывающий либо на позицию нового элемента, либо на позицию уже существующего элемента set с тем же значением. Элемент pair::second имеет значение true, если новый элемент был добавлен, и false, если элемент с таким значением уже существует в контейнере.

• find - ищет элемент, если элемент не найден, то возвращает set::end (работает за время log(n))

  iterator find ( const key_type& x ) const;

• count - возвращает количество вхождений элемента, для set возвращаемое значение может быть либо 1, либо 0 (работает за log(n))

  size_type count ( cont key_type& x ) const;

• lower_bound - возвращает итератор, указывающий на первое вхождение элемента (или итератор на первый элемент контейнера, который не меньше х) (log(n))

  iterator lower_bound ( const key_type& x ) const;

• upper_bound - возвращает итератор на последнее вхождение элемента (или итератор на первый элемент, который больше х) (log(n))

  iterator upper_bound ( const key_type& x ) const;

В множестве multiset из элементов {5, 3, 3, 3, 7, 4} lower_bound(3) вернет итератор, указывающий на позицию между 5 и первой 3, а upper_bound(3) - на позицию между последней 3 и 7.

При использовании контейнера set(multiset) на каждый элемент выделяется дополнительная память(с точностью до константы).

map

map - ассоциативный контейнер для хранения элементов, организованных в пары key-value. key каждого элемента в map уникален, value - значение элемента, ассоциированного с ключом key. Типы key и value могут не совпадать, например, для телефонной книги key - имя контакта, value - номер телефона.

Основные свойства map как ассоциативного контейнера:

• уникальность ключей: никакие два элемента в map не эквивалентны. multimap позволяет добавлять элементы с эквивалентными ключами;
• каждый элемент представляет собой пару key-value;
• в каждый момент времени элементы map отсортированы по значениям key.

  template < class Key, class T, class Compare = less<Key>,  class Allocator = allocator<pair<const Key,T> > > class map;

Где

• Key - тип ключа для элементов map,
• Т - тип ассоциированных значений value,
• остальные параметры шаблона map имеют тот же смысл, что и у шаблона контейнера set.

Итераторы к элементам map предоставляют доступ к значениям и key, и value:

  typedef pair<const Key, T> value_type;

  #include<map>

  std::map<string, int> m;
  m.insert(std::pair<string, int>("Bob", 35));

std::make_pair - функция, которая создает пару, типы выводятся из переданных аргументов. Объект pair может быть создан конструктором копирования от другого объекта pair, заданного другими типами, если соответствующие типы приводимы.

Данная функция определяется:

  template <class T1,class T2>
  pair<T1,T2> make_pair (T1 x, T2 y)
  {
    return ( pair<T1,T2>(x,y) );
  }

Строка "Bob" по умолчанию имеет тип char*, а не std::string, но при создании экземпляра std::pair<string, int> производится приведение типов передаваемых параметров, если это необходимо и возможно.

Замечание: нет гарантии, что в multimap элементы с одинаковыми значениями будут отсортированы по порядку добавления.

map - единственный среди ассоциативных массивов, к элементам которого можно обращаться напрямую по ключу:

  m["John"] = 22;

Замечания:

• При этом необходимо отметить, что такое обращение к элементу занимает время log(n) (т.е. время поиска элемента в дереве), а не константное значение, как обращение к элементам обычного массива.
• Класс Value должен иметь конструктор по умолчанию.
• Если в map нет элемента с ключом "John", то такой элемент будет создан.

Если Key - класс, определенный пользователем, то в нем должен быть определен operator<.

Функтор - класс, в котором перегружен оператор ().

Если необходимо, чтобы элементы типа А были упорядочены особым образом, нужно реализовать компаратор:

  #include<set>
  struct MyComp{
    bool operator()(A const &a, A const &b) const {
      return a.size() < b.size();
    }
  };

  set<A, MyComp> ss; // явно указываем, что элементы А нужно сравнивать, как реализовано в переданном шаблону компараторе

Замечание: для map нужно реализовать функтор, который сравнивает только значения Key.

  template<typename T>
  struct less{
    bool operator()(T const &a, T const &b) const {
      return a < b;
    }
  };

Замечания:

• less можно использовать как заглушку для вызова оператора <, если реализация сравнения для типа Т нелогична.
• вместо < нельзя использовать оператор <=, так как:

 1. Нарушается логика !(a < b) && !(b < a) => a = b.
 2. Не будет работать метод find.
 3. В какой-то момент элементы контейнера не будут отсортированы. 
 4. Компилятор не может проверить(обнаружить) такую ошибку.

proxy-объекты

vector<bool> v; специализированный шаблон - внутри хранятся элементы типа int, биты которых используют в качестве значений bool.

Замечания:

• Стандартом никак не гарантирован размер элементов типа bool(может быть как и 1 байт, так и 4);
• Не является контейнером с точки зрения требований, предъявляемых стандартом к контейнерам.

  &v[0]; // поведение не определено

Использование proxy-объектов:

  bool b = v[i];

происходит приведение к типу bool (operator=), для вычисления нужного значения сначала вычисляется индекс целого числа (i/32), а потом номер бита в этом числе (i%32), который отвечает за значение v[i]

 
  v[i] = b;

Для доступа создается временный(proxy) объект, который знает о внутреннем устройстве vector<bool> и используется для приведения к типу bool.

Замечания:

• Вместо vector<bool>, который обеспечивает эффективное использование памяти, но содержит много нетривиальных операций, можно использовать vector<char>. В таком случае мы точно знаем, что на каждый элемент отводится 1 байт памяти, и методы работать будут быстрее.
• bitset<16> bs; - set битов, используется, чтобы не было явных битовых операций. Количество битов должно быть известно на момент компиляции. Например, bitset можно использовать для работы с маской сети. bitset не является контейнером.

  bs.set(7); // устанавливает значение 7-ого бита в 1
  bs.flip(5); // инвертирует значение 5-ого бита

stack, queue, priority_queue называют контейнерными адаптерами, так как для этих типов нет ограничений на способ хранения элементов. Тип контейнера, который будет использоваться для хранения элементов, можно указать явно. Ограничения накладываются только на интерфейс.

  template < class T, class Container = deque<T> > class stack;

Обязательные для стека методы:

• back()
• push_back()
• pop_back()