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

93

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?

Superpolock
źródło
4
Zostałem poprawiony i zamierzałem użyć std :: map :: lower_bound zamiast std :: map :: find.
Superpolock

Odpowiedzi:

148

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
}
Łukasz
źródło
2
Tak właśnie działa funkcja find. Sztuczka polega na tym, że łączy w sobie wyszukiwanie potrzebne przez funkcję znajdź i wstaw. Oczywiście tak samo jest z użyciem wstawiania, a następnie spojrzenia na drugą zwracaną wartość.
puetzk
1
Dwa pytania: 1) Czym różni się metoda lower_bound od funkcji find na mapie? 2) W przypadku „mapy”, czy nie jest tak, że prawa ręka operacja && jest zawsze prawdziwa, gdy „lb! = Mymap.end ()”?
Richard Corden
12
@Richard: find () zwraca end () jeśli klucz nie istnieje, lower_bound zwraca pozycję, w której powinien znajdować się element (co z kolei może służyć jako wskazówka dotycząca wstawiania). @puetzek: Czy „po prostu wstaw” nie nadpisze wartości odniesienia dla istniejących kluczy? Nie jest pewne, czy OP tego chce.
peterchen
2
ktoś wie, czy jest coś podobnego dla unordered_map?
Giovanni Funchal
3
@peterchen map :: insert nie zastępuje istniejącej wartości, jeśli ona istnieje, patrz cplusplus.com/reference/map/map/insert .
Chris Drew
11

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.

Richard Corden
źródło
8

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.

gbjbaanb
źródło
5

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 ...

PiNoYBoY82
źródło
1

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.

Adam Tegen
źródło
Chciałbym. Ale nie ma hash_map w standardowej bibliotece C ++, a PHB nie zezwalają na kod poza tym.
Superpolock,
1
std :: tr1 :: unordered_map to mapa skrótów, która jest proponowana do dodania do następnego standardu i powinna być dostępna w większości aktualnych implementacji STL.
beldaz
1

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.

Stonky
źródło
1
Ponieważ (z pewnością przed C ++ 11) użycie wstawiania oznacza, że ​​nadal musisz utworzyć std::map::value_typeobiekt, zaakceptowana odpowiedź pozwala uniknąć nawet tego.
KillianDS
-1

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.

Mark Okup
źródło
1
To nie do końca prawda. STL różni się od większości innych bibliotek tym, że zapewnia wyraźne wymagania dużego O dla większości swoich operacji. Istnieje gwarantowana różnica między 2 * O (log n) a 1 * O (log n), niezależnie od implementacji używanej przez funkcje do osiągnięcia tego zachowania O (log n). To, czy ta różnica jest znacząca na Twojej platformie, to inna kwestia. Ale różnica zawsze będzie istnieć.
srm
@srm definiowanie wymagań big-O nadal nie mówi, ile czasu zajmie operacja w wartościach bezwzględnych. Gwarantowana różnica, o której mówisz, nie istnieje.
Mark Ransom
-2

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ł.


źródło
Nie, jeśli wpis istnieje, zwraca odwołanie do istniejącego wpisu.
Kris Kumler
2
-1 dla tej odpowiedzi. Jak powiedział Kris K, użycie map [klucz] = wartość nadpisze istniejący wpis, a nie „zachowa” go zgodnie z wymaganiami w pytaniu. Nie możesz przetestować istnienia za pomocą map [klucz], ponieważ zwróci to domyślnie skonstruowany obiekt, jeśli klucz nie istnieje i utworzy go jako wpis dla klucza
netjeff
Chodzi o to, aby sprawdzić, czy mapa jest już wypełniona i dodać / nadpisać tylko wtedy, gdy jej tam nie ma. Użycie mapy [klucz] zakłada, że ​​wartość jest tam zawsze.
srm