std :: map insert lub std :: map find?

Zakładając mapę, na której chcesz zachować istniejące wpisy. W 20% przypadków wpis, który wstawiasz, to nowe dane. Czy jest korzyść z robienia std :: map :: find then std :: map :: insert przy użyciu tego zwróconego iteratora? A może szybciej jest próba wstawienia, a następnie działanie w oparciu o to, czy iterator wskazuje, czy rekord został wstawiony, czy nie?

Odpowiedź brzmi: ty też nie. Zamiast tego chcesz zrobić coś, co sugeruje pozycja 24 efektywnego STL autorstwa Scotta Meyersa :

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
}

Odpowiedź na to pytanie zależy również od tego, jak kosztowne jest utworzenie typu wartości, który przechowujesz na mapie:

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.first->second = v;
  }
}

W przypadku typu wartości, takiego jak int, powyższe będzie bardziej wydajne niż wyszukiwanie, po którym następuje wstawienie (w przypadku braku optymalizacji kompilatora). Jak wspomniano powyżej, dzieje się tak, ponieważ przeszukiwanie mapy odbywa się tylko raz.

Jednak wywołanie wstawiania wymaga, aby masz już skonstruowaną nową „wartość”:

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.first->second = v;
  }
}

Aby wywołać „wstaw”, płacimy za drogie wywołanie w celu skonstruowania naszego typu wartości - iz tego, co powiedziałeś w pytaniu, nie będziesz używać tej nowej wartości w 20% przypadków. W powyższym przypadku, jeśli zmiana typu wartości mapy nie jest opcją, bardziej efektywne jest wykonanie najpierw polecenia „znajdź”, aby sprawdzić, czy musimy skonstruować element.

Alternatywnie, typ wartości mapy można zmienić, aby przechowywać uchwyty do danych przy użyciu ulubionego typu inteligentnego wskaźnika. Wywołanie wstawiania używa pustego wskaźnika (bardzo tanie w budowie) i tylko w razie potrzeby konstruowany jest nowy typ danych.

Nie będzie prawie żadnej różnicy w szybkości między 2, find zwróci iterator, insert robi to samo i i tak przeszuka mapę, aby określić, czy wpis już istnieje.

Więc… to zależy od osobistych preferencji. Zawsze próbuję wstawić, a następnie zaktualizować, jeśli to konieczne, ale niektórzy ludzie nie lubią obsługiwać zwracanej pary.

Pomyślałbym, że jeśli zrobisz znajdź, a potem włóż, dodatkowy koszt byłby wtedy, gdy nie znajdziesz klucza i nie wykonasz wstawiania po. To trochę tak, jakby przeglądać książki w porządku alfabetycznym i nie znajdować książki, a następnie ponownie przeglądać książki, aby zobaczyć, gdzie ją wstawić. Sprowadza się to do tego, jak będziesz obsługiwać klucze i czy ciągle się zmieniają. Teraz jest pewna elastyczność w tym, że jeśli jej nie znajdziesz, możesz rejestrować, robić wyjątki, robić, co chcesz ...

Jeśli martwisz się o wydajność, możesz sprawdzić hash_map <> .

Zwykle map <> jest implementowane jako drzewo binarne. W zależności od Twoich potrzeb, hash_map może być bardziej wydajna.

Wydaje mi się, że nie mam wystarczającej liczby punktów, aby zostawić komentarz, ale zaznaczona odpowiedź wydaje mi się długa - jeśli weźmiesz pod uwagę, że ta wstawka i tak zwraca iterator, po co szukać lower_bound, kiedy możesz po prostu użyć iteratora zwróconego. Dziwne.

Wszelkie odpowiedzi dotyczące wydajności będą zależeć od dokładnej implementacji twojego STL. Jedynym sposobem, aby mieć pewność, jest porównanie obu stron. Domyślam się, że różnica raczej nie będzie znacząca, więc zdecyduj w oparciu o preferowany styl.

map [klucz] - niech stl to załatwi. To najskuteczniejsze przekazywanie intencji.

Tak, w porządku.

Jeśli wykonasz wyszukiwanie, a następnie wstawisz, wykonujesz 2 x O (log N), gdy dostaniesz chybienie, ponieważ funkcja wyszukiwania pozwala tylko wiedzieć, czy musisz wstawić, a nie tam, gdzie wstawka powinna się znaleźć (lower_bound może ci tam pomóc) . Wystarczy prosta wkładka, a następnie zbadanie wyniku jest drogą, którą bym poszedł.