В чем разница между set <pair>и map в C ++?

Question

Есть два способа, которыми я могу легко создать ключ, атрибуцию значения в C ++ STL: карты и наборы пар. Например, у меня может быть

map<key_class,value_class>

или

set<pair<key_class,value_class> >

С точки зрения сложности алгоритма и стиля кодирования, каковы различия между этими использованиями?

Answer 1

Они семантически разные.Рассмотрим:

#include <set>
#include <map>
#include <utility>
#include <iostream>

using namespace std;

int main() {
  pair<int, int> p1(1, 1);
  pair<int, int> p2(1, 2);
  set< pair<int, int> > s;
  s.insert(p1);
  s.insert(p2);
  map<int, int> m;
  m.insert(p1);
  m.insert(p2);
  cout << "Set size = " << s.size() << endl;
  cout << "Map size = " << m.size() << endl;
}

http://ideone.com/cZ8Vjr

Вывод:

Установить размер = 2
Размер карты = 1

Answer 2

Элементы набора не могут быть изменены, пока они находятся в наборе. set iterator и const_iterator эквивалентны. Следовательно, с set<pair<key_class,value_class> > вы не можете изменить value_class на месте. Вы должны удалить старое значение из набора и добавить новое значение. Однако, если value_class является указателем, это не мешает вам изменять объект, на который он указывает.

С помощью map<key_class,value_class> вы можете изменить value_class на месте, если у вас есть неконстантная ссылка на карту.

Answer 3

map<key_class,value_class> будет сортировать по key_class и не допускать дублирования key_class.
set<pair<key_class,value_class> > будет сортировать по key_class, а затем по value_class, если экземпляры key_class равны, и разрешит несколько значений для key_class

Answer 4

Основным отличием является то, что для набора ключом является пара, а для карты ключом является key_class - это затрудняет поиск объектов с помощью key_class, а это то, что вы хотите делать с картами, для набора трудно.

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

Answer 5

std::map действует как ассоциативная структура данных.Другими словами, он позволяет запрашивать и изменять значения, используя связанный ключ.

A std::set<pair<K,V> > можно заставить работать таким образом, но вы должны написать дополнительный код для запроса, используя ключ и больше кода для изменения значения (т.е. удалить старую пару и вставить другую с тем жеключ и другое значение).Вы также должны убедиться, что не более двух значений с одним и тем же ключом (как вы уже догадались, больше кода).

Другими словами, вы можете попытаться подковать std::set такstd::map, но для этого нет никаких оснований.

Answer 6

Визуализируя это семантическое различие, которое Филипп упомянул после пошагового выполнения кода, обратите внимание, что ключ карты является const int и как p2 не был вставлен в m :

Answer 7

Чтобы понять алгоритмическую сложность, сначала необходимо понять реализацию.

std :: map реализован с использованием RB-дерева, где в качестве hash_map реализованы массивы связанного списка.std :: map предоставляет O (log (n)) для операции вставки / удаления / поиска, hash_map - это O (1) в лучшем случае и o (n) в худшем случае в зависимости от коллизий хешей.