Просмотр исходного текста страницы Ассоциативные контейнеры

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

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

К ассоциативным контейнерам относят:
* map
* multimap
* set
* multiset

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

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

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

  using std::set;

  set<int> s;
  s.insert(10);    // добавление элемента в множество
  s.insert(20);
  s.insert(10);    // еще одно значение 10 в множество добавлено не будет
  s.size();        // вернет 2
</source>
Методы set, которые можно реализовать, чтобы улучшить время работы:
* insert возвращает пару <source lang="cpp">std::pair<iterator, bool> </source>(работает за log(n))
<source lang="cpp">  
  pair<iterator,bool> insert ( const value_type& x );
</source>
Элементу pair::first присваивается итератор, указывающий либо на позицию нового элемента, либо на позицию уже существующего элемента set с тем же значением. Элемент pair::second имеет значение true, если новый элемент был добавлен, и false, если элемент с таким значением уже существует в контейнере.

* find  - ищет элемент, если элемент не найден, то возвращает set::end (работает за время log(n))
<source lang="cpp">
  iterator find ( const key_type& x ) const;
</source>
* count - возвращает количество вхождений элемента, для set возвращаемое значение может быть либо 1, либо 0 (работает за log(n))
<source lang="cpp">
  size_type count ( cont key_type& x ) const;
</source>
* lower_bound - возвращает итератор, указывающий на первое вхождение элемента (или итератор на первый элемент контейнера, который не меньше х) (log(n))
<source lang="cpp">
  iterator lower_bound ( const key_type& x ) const;
</source>
* upper_bound - возвращает итератор на последнее вхождение элемента (или итератор на первый элемент, который больше х) (log(n))
<source lang="cpp">
  iterator upper_bound ( const key_type& x ) const;
</source>
В множестве 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.
<source lang="cpp">
  template < class Key, class T, class Compare = less<Key>,  class Allocator = allocator<pair<const Key,T> > > class map;
</source>
Где 
* Key - тип ключа для элементов map, 
* Т - тип ассоциированных значений value,
* остальные параметры шаблона map имеют тот же смысл, что и у шаблона контейнера set.

Итераторы к элементам map предоставляют доступ к значениям и key, и value:
<source lang="cpp">
  typedef pair<const Key, T> value_type;
</source>
<source lang="cpp">
  #include<map>

  std::map<string, int> m;
  m.insert(std::pair<string, int>("Bob", 35));
</source>
std::make_pair - функция, которая создает пару, типы выводятся из переданных аргументов. Объект pair может быть создан конструктором копирования от другого объекта pair, заданного другими типами, если соответствующие типы приводимы.

Данная функция определяется:
<source lang="cpp">
  template <class T1,class T2>
  pair<T1,T2> make_pair (T1 x, T2 y)
  {
    return ( pair<T1,T2>(x,y) );
  }
</source>
Строка "Bob" по умолчанию имеет тип char*, а не std::string, но при создании экземпляра std::pair<string, int> производится приведение типов передаваемых параметров, если это необходимо и возможно.

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

map - единственный среди ассоциативных массивов, к элементам которого можно обращаться напрямую по ключу: 
<source lang="cpp">
  m["John"] = 22; 
</source>

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

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

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

Если необходимо, чтобы элементы типа А были упорядочены особым образом, нужно реализовать компаратор:
<source lang="cpp">
  #include<set>
  struct MyComp{
    bool operator()(A const &a, A const &b) const {
      return a.size() < b.size();
    }
  };

  set<A, MyComp> ss; // явно указываем, что элементы А нужно сравнивать, как реализовано в переданном шаблону компараторе
</source>
Замечание: для map нужно реализовать функтор, который сравнивает только значения Key.
<source lang="cpp">
  template<typename T>
  struct less{
    bool operator()(T const &a, T const &b) const {
      return a < b;
    }
  };
</source>
Замечания:
* less можно использовать как заглушку для вызова оператора <, если реализация сравнения для типа Т нелогична.
* вместо < нельзя использовать оператор <=, так как:
  1. Нарушается логика !(a < b) && !(b < a) => a = b.
  2. Не будет работать метод find.
  3. В какой-то момент элементы контейнера не будут отсортированы. 
  4. Компилятор не может проверить(обнаружить) такую ошибку.

=====proxy-объекты=====

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

Замечания:
* Стандартом никак не гарантирован размер элементов типа bool(может быть как и 1 байт, так и 4);
* Не является контейнером с точки зрения требований, предъявляемых стандартом к контейнерам.
<source lang="cpp">
  &v[0]; // поведение не определено
</source>
Использование proxy-объектов:
<source lang="cpp">
  bool b = v[i];
</source> происходит приведение к типу bool (operator=), для вычисления нужного значения сначала вычисляется индекс целого числа (i/32), а потом номер бита в этом числе (i%32), который отвечает за значение v[i]

<source lang="cpp"> 
  v[i] = b;
</source>
Для доступа создается временный(proxy) объект, который знает о внутреннем устройстве vector<bool> и используется для приведения к типу bool.

Замечания:
* Вместо vector<bool>, который обеспечивает эффективное использование памяти, но содержит много нетривиальных операций, можно использовать vector<char>. В таком случае мы точно знаем, что на каждый элемент отводится 1 байт памяти, и методы работать будут быстрее.
* bitset<16> bs; - set битов, используется, чтобы не было явных битовых операций. Количество битов должно быть известно на момент компиляции. Например, bitset можно использовать для работы с маской сети. bitset не является контейнером.
<source lang="cpp">
  bs.set(7); // устанавливает значение 7-ого бита в 1
  bs.flip(5); // инвертирует значение 5-ого бита
</source>
stack, queue, priority_queue называют контейнерными адаптерами, так как для этих типов нет ограничений на способ хранения элементов. Тип контейнера, который будет использоваться для хранения элементов, можно указать явно. Ограничения накладываются только на интерфейс.
<source lang="cpp">
  template < class T, class Container = deque<T> > class stack;
</source>
Обязательные для стека методы:
* back()	
* push_back()
* pop_back()