Ассоциативные контейнеры — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
(Новая страница: «====Ассоциативные контейнеры==== Ассоциативные контейнеры специально разработаны для эффе…»)
 
(Ассоциативные контейнеры)
 
(не показана одна промежуточная версия этого же участника)
Строка 17: Строка 17:
  
 
В реализации STL контейнер set определяется тремя шаблонными параметрами:
 
В реализации STL контейнер set определяется тремя шаблонными параметрами:
 
+
<source lang="cpp">
 
   template < class Key, class Compare = less<Key>, class Allocator = allocator<Key> > class set;
 
   template < class Key, class Compare = less<Key>, class Allocator = allocator<Key> > class set;
 
+
</source>
 
Где  
 
Где  
 
* Key - тип элементов, хранимых в контейнере.
 
* Key - тип элементов, хранимых в контейнере.
 
* Compare - Comparison class - класс, который по двум аргументам того же типа, что и тип элементов контейнера возвращает bool значение: comp(a,b) возвращает true, если элемент контейнера а меньше элемента b (comp - объект класса Comparison). Значение по умолчанию less<Key>, который возвращает то же самое, что и (a<b). Объекты set используют compare для определения позиции элемента в контейнере. Все элементы отсортированы в контейнере по этому принципу.
 
* Compare - Comparison class - класс, который по двум аргументам того же типа, что и тип элементов контейнера возвращает bool значение: comp(a,b) возвращает true, если элемент контейнера а меньше элемента b (comp - объект класса Comparison). Значение по умолчанию less<Key>, который возвращает то же самое, что и (a<b). Объекты set используют compare для определения позиции элемента в контейнере. Все элементы отсортированы в контейнере по этому принципу.
* Allocator - Тип объекта, который управляет модель распределения памяти. Шаблонный класс для типа Key, указанный по умолчанию,определяет модель самого простого управления памятью.
+
* Allocator - Тип объекта, который управляет моделью распределения памяти. Шаблонный класс для типа Key, указанный по умолчанию, определяет модель самого простого управления памятью.
 
+
  
 +
<source lang="cpp">
 
   #include<set>    // в этом файле определены set и multiset
 
   #include<set>    // в этом файле определены set и multiset
  
Строка 35: Строка 35:
 
   s.insert(10);    // еще одно значение 10 в множество добавлено не будет
 
   s.insert(10);    // еще одно значение 10 в множество добавлено не будет
 
   s.size();        // вернет 2
 
   s.size();        // вернет 2
 
+
</source>
 
Методы set, которые можно реализовать, чтобы улучшить время работы:
 
Методы set, которые можно реализовать, чтобы улучшить время работы:
* insert возвращает пару std::pair<iterator, bool> (работает за log(n))
+
* insert возвращает пару <source lang="cpp">std::pair<iterator, bool> </source>(работает за log(n))
 
+
<source lang="cpp"> 
 
   pair<iterator,bool> insert ( const value_type& x );
 
   pair<iterator,bool> insert ( const value_type& x );
 +
</source>
 
Элементу pair::first присваивается итератор, указывающий либо на позицию нового элемента, либо на позицию уже существующего элемента set с тем же значением. Элемент pair::second имеет значение true, если новый элемент был добавлен, и false, если элемент с таким значением уже существует в контейнере.
 
Элементу pair::first присваивается итератор, указывающий либо на позицию нового элемента, либо на позицию уже существующего элемента set с тем же значением. Элемент pair::second имеет значение true, если новый элемент был добавлен, и false, если элемент с таким значением уже существует в контейнере.
  
 
* find  - ищет элемент, если элемент не найден, то возвращает set::end (работает за время log(n))
 
* find  - ищет элемент, если элемент не найден, то возвращает set::end (работает за время log(n))
 
+
<source lang="cpp">
 
   iterator find ( const key_type& x ) const;
 
   iterator find ( const key_type& x ) const;
 
+
</source>
 
* count - возвращает количество вхождений элемента, для set возвращаемое значение может быть либо 1, либо 0 (работает за log(n))
 
* count - возвращает количество вхождений элемента, для set возвращаемое значение может быть либо 1, либо 0 (работает за log(n))
 
+
<source lang="cpp">
 
   size_type count ( cont key_type& x ) const;
 
   size_type count ( cont key_type& x ) const;
 
+
</source>
 
* lower_bound - возвращает итератор, указывающий на первое вхождение элемента (или итератор на первый элемент контейнера, который не меньше х) (log(n))
 
* lower_bound - возвращает итератор, указывающий на первое вхождение элемента (или итератор на первый элемент контейнера, который не меньше х) (log(n))
 
+
<source lang="cpp">
 
   iterator lower_bound ( const key_type& x ) const;
 
   iterator lower_bound ( const key_type& x ) const;
 
+
</source>
 
* upper_bound - возвращает итератор на последнее вхождение элемента (или итератор на первый элемент, который больше х) (log(n))
 
* upper_bound - возвращает итератор на последнее вхождение элемента (или итератор на первый элемент, который больше х) (log(n))
 
+
<source lang="cpp">
 
   iterator upper_bound ( const key_type& x ) const;
 
   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.
 
В множестве multiset из элементов {5, 3, 3, 3, 7, 4} lower_bound(3) вернет итератор, указывающий на позицию между 5 и первой 3, а upper_bound(3)  - на позицию между последней 3 и 7.
  
При использовании контейнера set(multiset) на каждый элемент выделяется дополнительная память для указателей(с точностью до константы).
+
При использовании контейнера set(multiset) на каждый элемент выделяется дополнительная память(с точностью до константы).
  
 
=====map=====
 
=====map=====
map - ассоциативный контейнер для хранения элементов, организованных в пары key-value. key каждого элемента в map уникален, value - значение элемента, ассоциированного с ключом key. Типы key могут не совпадать value, например, для телефонной книги key - имя контакта, value - номер телефона.
+
map - ассоциативный контейнер для хранения элементов, организованных в пары key-value. key каждого элемента в map уникален, value - значение элемента, ассоциированного с ключом key. Типы key и value могут не совпадать, например, для телефонной книги key - имя контакта, value - номер телефона.
 
+
Внутри map элементы отсортированы по значениям key.
+
  
 
Основные свойства map как ассоциативного контейнера:
 
Основные свойства map как ассоциативного контейнера:
 
* уникальность ключей: никакие два элемента в map не эквивалентны. multimap позволяет добавлять элементы с эквивалентными ключами;
 
* уникальность ключей: никакие два элемента в map не эквивалентны. multimap позволяет добавлять элементы с эквивалентными ключами;
 
* каждый элемент представляет собой пару key-value;
 
* каждый элемент представляет собой пару key-value;
* в каждый момент времени элементы map отсортированы.
+
* в каждый момент времени элементы map отсортированы по значениям key.
 
+
<source lang="cpp">
 
   template < class Key, class T, class Compare = less<Key>,  class Allocator = allocator<pair<const Key,T> > > class map;
 
   template < class Key, class T, class Compare = less<Key>,  class Allocator = allocator<pair<const Key,T> > > class map;
 
+
</source>
 
Где  
 
Где  
 
* Key - тип ключа для элементов map,  
 
* Key - тип ключа для элементов map,  
Строка 80: Строка 79:
  
 
Итераторы к элементам map предоставляют доступ к значениям и key, и value:
 
Итераторы к элементам map предоставляют доступ к значениям и key, и value:
 +
<source lang="cpp">
 
   typedef pair<const Key, T> value_type;
 
   typedef pair<const Key, T> value_type;
 
+
</source>
 
+
<source lang="cpp">
 
   #include<map>
 
   #include<map>
  
 
   std::map<string, int> m;
 
   std::map<string, int> m;
 
   m.insert(std::pair<string, int>("Bob", 35));
 
   m.insert(std::pair<string, int>("Bob", 35));
 
+
</source>
 
std::make_pair - функция, которая создает пару, типы выводятся из переданных аргументов. Объект pair может быть создан конструктором копирования от другого объекта pair, заданного другими типами, если соответствующие типы приводимы.
 
std::make_pair - функция, которая создает пару, типы выводятся из переданных аргументов. Объект pair может быть создан конструктором копирования от другого объекта pair, заданного другими типами, если соответствующие типы приводимы.
  
 
Данная функция определяется:
 
Данная функция определяется:
 +
<source lang="cpp">
 
   template <class T1,class T2>
 
   template <class T1,class T2>
 
   pair<T1,T2> make_pair (T1 x, T2 y)
 
   pair<T1,T2> make_pair (T1 x, T2 y)
Строка 96: Строка 97:
 
     return ( pair<T1,T2>(x,y) );
 
     return ( pair<T1,T2>(x,y) );
 
   }
 
   }
 
+
</source>
 
Строка "Bob" по умолчанию имеет тип char*, а не std::string, но при создании экземпляра std::pair<string, int> производится приведение типов передаваемых параметров, если это необходимо и возможно.
 
Строка "Bob" по умолчанию имеет тип char*, а не std::string, но при создании экземпляра std::pair<string, int> производится приведение типов передаваемых параметров, если это необходимо и возможно.
  
Строка 102: Строка 103:
  
 
map - единственный среди ассоциативных массивов, к элементам которого можно обращаться напрямую по ключу:  
 
map - единственный среди ассоциативных массивов, к элементам которого можно обращаться напрямую по ключу:  
 +
<source lang="cpp">
 
   m["John"] = 22;  
 
   m["John"] = 22;  
 +
</source>
  
 
Замечания:
 
Замечания:
Строка 114: Строка 117:
  
 
Если необходимо, чтобы элементы типа А были упорядочены особым образом, нужно реализовать компаратор:
 
Если необходимо, чтобы элементы типа А были упорядочены особым образом, нужно реализовать компаратор:
 +
<source lang="cpp">
 
   #include<set>
 
   #include<set>
 
   struct MyComp{
 
   struct MyComp{
Строка 122: Строка 126:
  
 
   set<A, MyComp> ss; // явно указываем, что элементы А нужно сравнивать, как реализовано в переданном шаблону компараторе
 
   set<A, MyComp> ss; // явно указываем, что элементы А нужно сравнивать, как реализовано в переданном шаблону компараторе
 
+
</source>
 
Замечание: для map нужно реализовать функтор, который сравнивает только значения Key.
 
Замечание: для map нужно реализовать функтор, который сравнивает только значения Key.
 
+
<source lang="cpp">
 
   template<typename T>
 
   template<typename T>
 
   struct less{
 
   struct less{
Строка 131: Строка 135:
 
     }
 
     }
 
   };
 
   };
 
+
</source>
 
Замечания:
 
Замечания:
 
* less можно использовать как заглушку для вызова оператора <, если реализация сравнения для типа Т нелогична.
 
* less можно использовать как заглушку для вызова оператора <, если реализация сравнения для типа Т нелогична.
Строка 140: Строка 144:
 
   4. Компилятор не может проверить(обнаружить) такую ошибку.
 
   4. Компилятор не может проверить(обнаружить) такую ошибку.
  
 +
=====proxy-объекты=====
  
 
vector<bool> v; специализированный шаблон - внутри хранятся элементы типа int, биты которых используют в качестве значений bool.
 
vector<bool> v; специализированный шаблон - внутри хранятся элементы типа int, биты которых используют в качестве значений bool.
Строка 146: Строка 151:
 
* Стандартом никак не гарантирован размер элементов типа bool(может быть как и 1 байт, так и 4);
 
* Стандартом никак не гарантирован размер элементов типа bool(может быть как и 1 байт, так и 4);
 
* Не является контейнером с точки зрения требований, предъявляемых стандартом к контейнерам.
 
* Не является контейнером с точки зрения требований, предъявляемых стандартом к контейнерам.
 +
<source lang="cpp">
 
   &v[0]; // поведение не определено
 
   &v[0]; // поведение не определено
 
+
</source>
 
Использование proxy-объектов:
 
Использование proxy-объектов:
   bool b = v[i]; //происходит приведение к типу bool (operator=), для вычисления нужного значения сначала вычисляется индекс целого числа (i/32), а потом номер бита в этом числе (i%32), который отвечает за значение v[i]
+
<source lang="cpp">
 
+
   bool b = v[i];
   v[i] = b; // для доступа создается временный(proxy) объект, который знает о внутреннем устройстве vector<bool> и используется для приведения к типу bool и приравнивания к типу bool.
+
</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 байт памяти, и методы работать будут быстрее.
 
* Вместо vector<bool>, который обеспечивает эффективное использование памяти, но содержит много нетривиальных операций, можно использовать vector<char>. В таком случае мы точно знаем, что на каждый элемент отводится 1 байт памяти, и методы работать будут быстрее.
 
* bitset<16> bs; - set битов, используется, чтобы не было явных битовых операций. Количество битов должно быть известно на момент компиляции. Например, bitset можно использовать для работы с маской сети. bitset не является контейнером.
 
* bitset<16> bs; - set битов, используется, чтобы не было явных битовых операций. Количество битов должно быть известно на момент компиляции. Например, bitset можно использовать для работы с маской сети. bitset не является контейнером.
 +
<source lang="cpp">
 
   bs.set(7); // устанавливает значение 7-ого бита в 1
 
   bs.set(7); // устанавливает значение 7-ого бита в 1
 
   bs.flip(5); // инвертирует значение 5-ого бита
 
   bs.flip(5); // инвертирует значение 5-ого бита
 
+
</source>
stack, queue, priority_queue называют контейнерными адаптерами, так как для этих типов нет ограничений на способ хранения элементов, тип контейнера, который будет использоваться для хранения элементов, можно указать явно. Ограничения накладываются только на интерфейс.
+
stack, queue, priority_queue называют контейнерными адаптерами, так как для этих типов нет ограничений на способ хранения элементов. Тип контейнера, который будет использоваться для хранения элементов, можно указать явно. Ограничения накладываются только на интерфейс.
 +
<source lang="cpp">
 
   template < class T, class Container = deque<T> > class stack;
 
   template < class T, class Container = deque<T> > class stack;
 
+
</source>
 
Обязательные для стека методы:
 
Обязательные для стека методы:
 
* back()
 
* back()
 
* push_back()
 
* push_back()
 
* pop_back()
 
* pop_back()

Текущая версия на 07:51, 18 мая 2011

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

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

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

  • 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()