Какая разница между установкой <pair> и map в С++?

Ответ 1

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

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

Ответ 2

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

#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

Ответ 3

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

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

Ответ 4

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

Ответ 5

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

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

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

Ответ 6

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

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

Ответ 7

Визуализируя, что семантическая разница Филипп упомянул после прохождения кода, обратите внимание, как ключ карты является константой int и как p2 не был вставлен в m: