Вставка unordered_map в последний итератор - PullRequest
Новая
       47

Вставка unordered_map в последний итератор

0 голосов
/ 12 июня 2019

Это определенное и допустимое поведение, которое вставляется через сквозной итератор, возвращаемый find, когда ключ не найден: 

auto it = m.find(key);
if (it == m.end()) {
    m.insert(it, make_pair(key, value));
}

, потому что это сохранит дополнительный поиск по сравнению с использованием: 

m[key] = value;

1 Ответ

2 голосов
/ 12 июня 2019

Хотя безопасно передать конечный итератор в качестве подсказки для unordered_map::insert, на самом деле он ничего не выполняет.

Из трех основных реализаций стандартной библиотеки только libstdc ++ делает что-либо с этой подсказкой,и даже тогда он будет использовать его только в том случае, если будет указывать на действительную запись.

Если вы хотите избежать двух поисков (один для определения наличия элемента, а другой для его вставки), вам следуетпросто попробуйте вставить его.insert возвращает и bool, обозначающий, был ли вставлен новый элемент, и итератор либо вновь вставленному элементу, либо существующему элементу, который препятствовал вставке.Это означает, что наиболее эффективный способ вставить элемент, если он не существует, и получить итератор для элемента, это сделать что-то вроде этого: 

decltype(m)::iterator it;
bool inserted;
std::tie(it, inserted) = m.insert(std::make_pair(key, value));
if (inserted) {
    // ...
}

Если ваш mapped_type дорогой для создания, выможно избежать его построения с помощью try_emplace (доступно только в C ++ 17 или более поздней версии): 

auto [it, inserted] = m.try_emplace(key, args, to, value, constructor);
if (inserted) {
    // ...
}

Pre C ++ 17, вы можете просто позволить operator[] default-построить элемент и сравнитьРазмер контейнера, чтобы определить, был ли добавлен новый элемент: 

size_t size_before = m.size();
ValueType& element = m[key];
size_t size_after = m.size();
if (size_before != size_after) {
    element = ValueType{args, to, value, constructor};
    // ...
}

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

...