Я хочу хранить большое количество пар (около 10^7 пар) в каком-то контейнере. Операции, которые я хочу выполнить, insert и find.Какая разница в производительности std :: set <pair> и std :: map <int,int>
Как мы можем использовать std::set и std::map для хранения пар, я хочу знать, какой контейнер лучше с точки зрения скорости. Я искал похожие вопросы, но не нашел ответа. поэтому, пожалуйста, кто-нибудь ответить на мой вопрос ......
std::pair<int, int> имеет оператор меньше, что делает разницу между вторым значениями, тоже (так он будет использоваться в std::set<std::pair<int, int>>), а std::map ничего не делает со вторым значением. В результате это означает:
std::map<int, int> m;
std::set<std::pair<int, int> > s;
m.insert(std::make_pair(0, 0));
m.insert(std::make_pair(0, 1)); // it won't be inserted as key is duplicated
s.insert(std::make_pair(0, 0));
s.insert(std::make_pair(0, 1)); // it will be inserted
Update: В большинстве реализаций STL set и map реализации одинаковы (балансный RB дерево, как правило, set и map приходят из того же шаблона базового класса), в вашем случае именно так, разница в использовании оператора меньше.
Правда, но не отвечает на вопрос. – juanchopanza
@juanchopanza правда, обновлено. – Naszta
Ваше изменение не изменяет тот факт, что это не отвечает на заданный вопрос. И вы можете использовать различные критерии сравнения для набора. – juanchopanza
Если производительность, если ваша цель, и это единственные операции, которые вы выполняете, и вы * не * рассматриваете [** 'unordered_map' **] (http://en.cppreference.com/w/cpp/container/unordered_map), я смиренно предлагаю вам пересмотреть, так как это, скорее всего, превзойдет * любые другие варианты. – WhozCraig
Если вы заботитесь о производительности, вы должны измерить. И подумайте над дополнительным кодом, который должен быть написан и сохранен, чтобы заставить набор вести себя как карта. – juanchopanza
Карта чего? 'map'? Этот контейнер будет служить совершенно другой цели для 'set >'. –