Каково различие между набором <пара> и картой в C++?
Существует два пути, которыми я могу легко сделать ключ, атрибуцию значения в C++ STL: карты и наборы пар. Например, я мог бы иметь
map<key_class,value_class>
или
set<pair<key_class,value_class> >
С точки зрения сложности алгоритма и стиля кодирования, каковы различия между этими использованиями?
5 ответов
Элементы набора не могут быть изменены, пока они находятся в наборе. set итератор и const_iterator эквивалентны. Следовательно, если для параметра задано значение <пара , вы не можете изменить value_class на месте. Вы должны удалить старое значение из набора и добавить новое значение. Однако, если value_class является указателем, это не мешает вам изменять объект, на который он указывает.
С помощью map вы можете изменить value_class на месте, предполагая, что у вас есть неконстантная ссылка на карту.
std :: map действует как ассоциативная структура данных. Другими словами, он позволяет запрашивать и изменять значения, используя связанный с ним ключ.
A std :: set можно заставить работать так, но вам нужно написать дополнительный код для запроса, используя ключ и дополнительный код для изменения значения (т.е. удалите старую пару и вставьте другую с тем же ключом и другим значением). Вы также должны убедиться, что существует не более двух значений с одним и тем же ключом (вы догадались, больше кода).
Другими словами, вы можете попробовать настроить std :: set , чтобы он работал как std :: map , но для этого нет причин.
map будет сортировать по key_class и не допускать дублирования key_class.
set будет сортировать по key_class, а затем по value_class, если экземпляры key_class равны, и разрешит несколько значений для key_class
Они семантически разные. Рассмотрим:
#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;
}
Вывод:
Установить размер = 2
Размер карты = 1
Основное отличие состоит в том, что для набора ключом является пара, тогда как для карты ключом является key_class - это заставляет искать вещи по key_class, что вы и хотите делать с картами. , сложный для набора.
Оба типа обычно реализуются с одной и той же структурой данных (обычно это сбалансированное красно-черное двоичное дерево), поэтому их сложность должна быть одинаковой.