Есть два способа, с помощью которых я могу легко сделать ключ, атрибуцию значения в С++ STL: карты и наборы пар. Например, я мог бы
map<key_class,value_class>
или
set<pair<key_class,value_class> >
С точки зрения сложности алгоритма и стиля кодирования, каковы различия между этими обычаями?
Устанавливать элементы нельзя, пока они находятся в наборе. set iterator и const_iterator эквивалентны. Поэтому с set<pair<key_class,value_class> > вы не можете изменить value_class на месте. Вы должны удалить старое значение из набора и добавить новое значение. Однако, если value_class является указателем, это не мешает вам изменять объект, на который он указывает.
С map<key_class,value_class> вы можете изменить value_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 - это делает поиск вещей ключевым классом, что вы хотите делать с картами, сложными для набора.
Оба из них обычно реализуются с той же структурой данных (обычно это сбалансированное двоичное дерево с красным-черным), поэтому сложность для них должна быть одинаковой.
map<key_class,value_class> будет сортировать по key_class и не допускать дубликатов key_class. set<pair<key_class,value_class> > будет сортировать по key_class, а затем value_class, если экземпляры key_class равны и позволят несколько значений для key_class
std::map действует как ассоциативная структура данных. Другими словами, он позволяет запрашивать и изменять значения с помощью связанного с ним ключа.
A std::set<pair<K,V> > может работать так, но вам нужно написать дополнительный код для запроса, используя ключ и еще один код для изменения значения (например, удалить старую пару и вставить другую с тем же ключом и различное значение). Вы также должны убедиться, что имеется не более двух значений с одним и тем же ключом (вы уже догадались, больше кода).
Другими словами, вы можете попытаться обучить a std::set работать как std::map, но нет причин для этого.
Чтобы понять алгоритмическую сложность, вам сначала нужно понять реализацию.
std:: map реализуется с использованием RB-дерева, где hash_map реализуется с использованием массивов связанного списка. std:: map обеспечивает O (log (n)) для операции insert/delete/search, hash_map - это O (1), наилучший случай и o (n) в худшем случае в зависимости от хеш-коллизий.
Визуализируя, что семантическая разница Филипп упомянул после прохождения кода, обратите внимание, как ключ карты является константой int и как p2 не был вставлен в m:
