std :: map insert or std :: map find?

Question

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

Answer 1

Ответ вы не делаете. Вместо этого вы хотите сделать что-то предложенное пунктом 24 Effective STL по Scott Meyers:

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 
} 

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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

Answer 5

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

Answer 6

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

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

Answer 7

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

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

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

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

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

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

Answer 8

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

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

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

Answer 9

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