СТД::карта вставить или std::карта найти?

предполагая, что карта, где вы хотите сохранить существующие записи. В 20% случаев вводимые данные являются новыми. Есть ли преимущество в выполнении std::map::find затем std::map:: insert с помощью этого возвращенного итератора? Или быстрее попытаться вставить, а затем действовать на основе того, указывает ли итератор, что запись была или не была вставлена?

9 81
c++ castle-windsor optimization stdmap

9 ответов:

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

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
}
132

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

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

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

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;
  }
}

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

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

10

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

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

8

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

5

Я потерялся на верхнем ответе.

найти карту возвращает.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

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

2

Если вы обеспокоены эффективностью, вы можете проверить обработчик действия hash_map.

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

1

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

1

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

0

карта[ ключ] - пусть stl разобраться. Это наиболее эффективно передает ваше намерение.

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

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

-2