Std:: map insert или std:: map find?

Ответ 1

Ответ: вы тоже. Вместо этого вы хотите сделать что-то, предложенное в пункте 24 Эффективный STL, Скотт Мейерс:

typedef map<int, int> MapType;    // Your map type may vary, just change the typedef

MapType mymap;
// Add elements to map here
int k = 4;   // assume we're searching for keys equal to 4
int v = 0;   // assume we want the value 0 associated with the key of 4

MapType::iterator lb = mymap.lower_bound(k);

if(lb != mymap.end() && !(mymap.key_comp()(k, lb->first)))
{
    // key already exists
    // update lb->second if you care to
}
else
{
    // the key does not exist in the map
    // add it to the map
    mymap.insert(lb, MapType::value_type(k, v));    // Use lb as a hint to insert,
                                                    // so it can avoid another lookup
}

Ответ 2

Ответ на этот вопрос также зависит от того, насколько дорого стоит создать тип значения, который вы храните на карте:

typedef std::map <int, int> MapOfInts;
typedef std::pair <MapOfInts::iterator, bool> IResult;

void foo (MapOfInts & m, int k, int v) {
  IResult ir = m.insert (std::make_pair (k, v));
  if (ir.second) {
    // insertion took place (ie. new entry)
  }
  else if ( replaceEntry ( ir.first->first ) ) {
    ir.second->second = v;
  }
}

Для типа значения, такого как int, выше будет более эффективным, чем поиск, за которым следует вставка (в отсутствие оптимизации компилятора). Как указано выше, это происходит потому, что поиск по карте происходит только один раз.

Однако вызов для вставки требует, чтобы вы уже создали новое значение:

class LargeDataType { /* ... */ };
typedef std::map <int, LargeDataType> MapOfLargeDataType;
typedef std::pair <MapOfLargeDataType::iterator, bool> IResult;

void foo (MapOfLargeDataType & m, int k) {

  // This call is more expensive than a find through the map:
  LargeDataType const & v = VeryExpensiveCall ( /* ... */ );

  IResult ir = m.insert (std::make_pair (k, v));
  if (ir.second) {
    // insertion took place (ie. new entry)
  }
  else if ( replaceEntry ( ir.first->first ) ) {
    ir.second->second = v;
  }
}

Чтобы позвонить "вставить", мы платим за дорогостоящий вызов, чтобы построить наш тип значения - и из того, что вы сказали в вопросе, вы не будете использовать это новое значение в 20% случаев. В приведенном выше случае, если изменение типа значения карты не является опцией, тогда более эффективно сначала выполнить "найти", чтобы проверить, нужно ли нам создавать элемент.

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

Ответ 3

Не будет никакой разницы в скорости между 2, find вернет итератор, вставка сделает то же самое и будет искать карту в любом случае, чтобы определить, существует ли запись.

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

Ответ 4

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

Ответ 5

Я потерял верхний ответ.

Найти возвращает map.end(), если он не находит ничего, что означает, если вы добавляете новые вещи, тогда

iter = map.find();
if (iter == map.end()) {
  map.insert(..) or map[key] = value
} else {
  // do nothing. You said you did not want to effect existing stuff.
}

в два раза медленнее, чем

map.insert

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

Ответ 6

Если вас беспокоит эффективность, вы можете проверить hash_map < > .

Обычно map < > реализуется как двоичное дерево. В зависимости от ваших потребностей, hash_map может быть более эффективным.

Ответ 7

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

Ответ 8

Любые ответы об эффективности будут зависеть от точной реализации вашего STL. Единственный способ узнать наверняка - сравнить его в обоих направлениях. Я предполагаю, что разница вряд ли будет значительной, поэтому решите, основываясь на стиле, который вы предпочитаете.

Ответ 9

map [key] - пусть stl сортирует его. Это наиболее эффективно связывает ваше намерение.

Да, справедливо.

Если вы выполните поиск, а затем вставку, вы выполняете 2 x O (log N), когда вы получаете пропуски, поскольку поиск только позволяет вам знать, нужно ли вставлять не туда, куда должна идти вставка (lower_bound может помочь вы там). Просто прямая вставка, а затем изучение результата - это то, как я пойду.