std:: вставка карты или std:: поиск по карте?

StackOverflow https://stackoverflow.com/questions/97050

  •  01-07-2019
  •  | 
  •  

Вопрос

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

Это было полезно?

Решение

Ответ в том, что вы не делаете ни того, ни другого.Вместо этого вы хотите сделать что-то, предложенное пунктом 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
}

Другие советы

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

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

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

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

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

Я запутался в главном ответе.

Find возвращает 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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top