Подтвердить что ты не робот

Использование оператора [] эффективно с С++ unordered_map

Во-первых, может кто-то уточнить, использует ли в С++ оператор [] в сочетании с 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;
4b9b3361

ОТВЕТЫ

Ответ 1

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

iterator iter = map.find(key);

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

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- или 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;

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

return value;

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

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

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

Ответ 2

Вы можете проверить, существует ли элемент, и вставить новый элемент, если он не существует, с помощью специальной функции 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 или возвращает итератор, где фактически был элемент, если второй элемент пары является ложным.

Ответ 3

Во-первых, кто-то может уточнить, использует ли в С++ оператор [] в сочетании с 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;