Эффективное использование оператора [] с неупорядоченной картой на языке C++

Во-первых, может ли кто-то уточнить, является ли в C++ использование оператора [] в сочетании с unordered_map для поиска обертыванием вызова метода find (), или использование оператора [] быстрее, чем find()?

Во-вторых, в следующем фрагменте кода я подозреваю, что в тех случаях, когда ключ еще не находится в unordered_map, я выполняю второй поиск через строку map[key] = value, чтобы заменить значение по умолчанию, созданное там с помощью оператора [], когда ключ отсутствует.

Верно ли это, и если да, то есть ли способ (возможно, с помощью указателей или чего-то еще), что я мог бы выполнить только один поиск в любом случае (возможно, сохранив адрес, где разместить значение/прочитать значение) и все еще достичь той же функциональности? Очевидно, что это было бы полезным повышением эффективности, если бы это было так.

Вот фрагмент модифицированного кода: 

    int stored_val = map[key]; // first look up. Does this wrap ->find()??

    // return the corresponding value if we find the key in the map - ie != 0
    if (stored_val) return stored_val;

    // if not in map
    map[key] = value; 
       /* second (unnecessary?) look up here to find position for newly 
          added key entry */

   return value;
3 31
c++ unordered-map

3 ответа:

operator[] вставит запись для вас с построенным по умолчанию значением, если его еще нет. Это эквивалентно, но, вероятно, будет реализовано более эффективно, чем: 

iterator iter = map.find(key);

if(iter == map.end())
{
    iter = map.insert(value_type(key, int())).second;
}

return iter;

operator[] может быть быстрее, чем делать работу вручную с помощью find() и еще insert(), потому что это может избавить вас от необходимости повторно хэшировать ключ.

Один из способов обойти наличие нескольких поисков в коде - это взять ссылку на значение: 

int &stored_val = map[key];

// return the corresponding value if we find the key in the map - ie != 0
if (stored_val) return stored_val;

// if not in map
stored_val = value;

return value;

Примечание что если значение не существует в карте, operator[] будет по умолчанию-построить и вставить его. Таким образом, хотя это позволит избежать многократных поисков, на самом деле он может быть медленнее, если используется с типом, который медленнее для default-construct + assign, чем для copy - or move-construct.

С int хотя, который дешево по умолчанию конструирует 0, вы можете рассматривать 0 как магическое число, означающее пустоту. Это выглядит так, как это может быть в вашем примере.

Если у вас нет такого магического числа, у вас есть есть два варианта. То, что вы должны использовать, зависит от того, насколько дорого для вас вычислить значение.

Во-первых, когда хэширование ключа дешево, но вычисление значения дорого, find() может быть лучшим вариантом. Это будет хэшировать дважды, но только вычислить значение, когда это необходимо: 
iterator iter = map.find(key);

// return the corresponding value if we find the key in the map
if(iter != map.end()) return iter->second;

// if not in map
map.insert(value_type(key, value));

return value;

Но если у вас уже есть значение, вы можете сделать это очень эффективно - возможно, slighty более эффективно, чем использование ссылки + магическое число, как указано выше: 

pair<iterator,bool> iter = map.insert(value_type(key, value));
return iter->second;

Если bool возвращается по map.insert(value_type) верно, элемент был вставлен. В остальном он уже существовал и никаких изменений не вносилось. Итератор возвращает точки к вставленному или существующему значению на карте. Для вашего простого примера это может быть лучшим вариантом.

41

Вы можете одновременно проверить, существует ли элемент, и вставить новый элемент, если он не существует, с помощью специальной функции insert, которая возвращает pair<iterator, bool>, в которой булево значение сообщает вам, было ли оно действительно вставлено. Например, код здесь: 

  unordered_map<char, int> mymap;
  pair<unordered_map<char,int>::iterator,bool> ret;

  // first insert function version (single parameter):;
  mymap.insert ( pair<char,int>('z',200) );
  ret=mymap.insert (pair<char,int>('z',500) ); 
  if (ret.second==false)
  {
    cout << "element 'z' already existed";
    cout << " with a value of " << ret.first->second << endl;
  }

Здесь код вставляет пару <'z',200> в карту, если она не существует. Он возвращает итератор, в который он вставляется, если значение второго элемента возвращаемой пары равно true, или возвращает итератор, где элемент действительно был, если второй элемент пары ложен.

9

Во-первых, может ли кто-то уточнить, является ли в C++ использование оператора [] в сочетании с unordered_map для поиска обертыванием вызова метода Find (), или использование оператора [] быстрее, чем Find()?

Для этого нет никаких правил. Реализация [] может использовать find(), она может выполнять поиск самостоятельно или делегировать поиск какому-либо частному методу, который также используется find() внутренне.

Также нет гарантии, на какой из них быстрее. find() включает в себя накладные расходы при построении и возврате итератора, в то время как [], вероятно, будет медленнее, если ключ не существует, так как он вставляет новое значение в этом случае.

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

Если ключ отсутствует в Карте, [] вставит новое значение, построенное по умолчанию, и вернет ссылку. Таким образом, вы можете сохранить эту ссылку чтобы сохранить второй поиск: 

int& stored_val = map[key];  // Note the reference

if (stored_val) return stored_val;

// Use the reference to save a second lookup.
stored_val = value; 

return value;
2