​​Double lookup
#опытным

Решил сделать небольшое дополнение к предыдущему посту по результатам дискуссии в комментариях.

Не нужно использовать методы count(key) и contains(key), если вы потом собираетесь работать с этим ключом в ассоциативном контейнере(например изменять объект по ключу). Это может привести к так называемому double lookup. То есть двойной поиск по контейнеру.

Возьмем для примера std::map для показательности. И вот такой код:

std::map<std::string, std::string> map;

std::string get_value(const std::string& key) {
  if (!map.contains(key)) {
    std::string value = longCalculations(key);
    map[key] = value;
    return value;
  } else {
    return map[key];
  }
}

Здесь мы по ключу key выдаем какое-то значение value. Эти значения вычисляются при помощи долгой функции longCalculations, поэтому было решено закэшировать все уже вычисленные значения в мапе. Так мы сможем обойти долгие вычисления и быстро дать ответ в случае, если уже искали это значение.

Только вот в чем проблема. Поиск по мапе - логарифмическая по времени операция. И в этом примере мы всегда делаем 2 поиска: первый раз на contains(мы должны пройтись по контейнеру, чтобы понять, есть ли элемент) и второй раз на operator[](нужно пройтись по контейнеру, чтобы вставить в него элемент/получить к нему доступ). Долговато как-то. Может можно получше?

В случае, если ключ есть в мапе, то мы можем делать всего 1 поиск! С помощью метода find и итератора на элемент.

std::string get_value(const std::string& key) {
  auto it = map.find(key);
  if (it == map.end()) {
    std::string value = longCalculations(key);
    map[key] = value;
    return value;
  } else {
    return it->second;
  }
}

Мы в начале попытались найти конкретный элемент мапы по ключу. И если его нет, то нам все-таки придется выполнить второй поиск, чтобы найти подходящее место для элемента. Но вот если ключ есть, тогда мы можем использовать сам итератор для возврата значения и второго поиска не будет!


Методы count и contains нужно использовать только тогда, когда у вас нет надобности в получении доступа к элементам контейнера. Find в этом случае, по моему мнению, немного синтаксически избыточен. А вот говорящие методы - самая тема. Например, у вас есть множество, в котором хранятся какие-то поля джейсона. И вам нужно как-то трансформировать только те значения, ключи которых находятся во множестве.

std::set<std::string> tokens;
std::string json_token;
Json json;
if (tokens.contains(json_token)) {
  transformJson(json, json_token);
}

Все прекрасно читается и никакого двойного поиска!

Don't do the same work twice. Stay cool.

#cppcore #goodpractice