Czy w mapach STL lepiej jest używać map :: insert niż []?

201

Jakiś czas temu rozmawiałem z kolegą o tym, jak wstawiać wartości do map STL . Wolałem, map[key] = value; ponieważ wydaje się to naturalne i czytelne, podczas gdy on wolał map.insert(std::make_pair(key, value))

Właśnie go zapytałem i żadne z nas nie pamięta, dlaczego wkładka jest lepsza, ale jestem pewien, że nie była to tylko preferencja stylowa, a raczej powód techniczny, taki jak wydajność. Odniesienia SGI STL po prostu mówi „Ściśle mówiąc, ta funkcja jest niepotrzebna członkiem. Istnieje tylko dla wygody”

Czy ktoś może mi powiedzieć ten powód, czy tylko marzę, że jest taki powód?

Danio
źródło
2
Dzięki za wszystkie świetne odpowiedzi - były bardzo pomocne. To świetna wersja demonstracyjna przepełnienia stosu w najlepszym wydaniu. Byłem rozdarty co do tego, która odpowiedź powinna być zaakceptowana: netjeff jest bardziej jednoznaczny na temat różnych zachowań, Greg Rogers wspomniał o problemach z wydajnością. Chciałbym móc zaznaczyć oba.
danio,
6
W rzeczywistości w przypadku C ++ 11 najlepiej jest użyć mapy :: Situace, która pozwala uniknąć podwójnej konstrukcji
einpoklum
@einpoklum: W rzeczywistości Scott Meyers sugeruje coś innego w swoim przemówieniu „Ewoluujące poszukiwanie skutecznego C ++”.
Thomas Eding,
3
@einpoklum: Tak jest w przypadku umieszczania w nowo zbudowanej pamięci. Ale ze względu na niektóre wymagania norm dla mapy istnieją techniczne powody, dla których położenie może być wolniejsze niż wstawianie. Dyskusja jest dostępna bezpłatnie na youtube, na przykład ten link youtube.com/watch?v=smqT9Io_bKo @ ~ 38-40 min. Aby uzyskać link SO, oto stackoverflow.com/questions/26446352/…
Thomas Eding,
1
Naprawdę spierałbym się z niektórymi prezentacjami Meyersa, ale to wykracza poza zakres tego wątku komentarza, a zresztą chyba muszę wycofać mój wcześniejszy komentarz.
einpoklum,

Odpowiedzi:

240

Kiedy piszesz

map[key] = value;

nie ma sposobu, aby stwierdzić, czy otrzymuje się valueza keylub jeśli utworzony nowy keyz value.

map::insert() utworzy tylko:

using std::cout; using std::endl;
typedef std::map<int, std::string> MyMap;
MyMap map;
// ...
std::pair<MyMap::iterator, bool> res = map.insert(MyMap::value_type(key,value));
if ( ! res.second ) {
    cout << "key " <<  key << " already exists "
         << " with value " << (res.first)->second << endl;
} else {
    cout << "created key " << key << " with value " << value << endl;
}

W przypadku większości moich aplikacji zwykle nie dbam o to, czy tworzę, czy wymieniam, więc używam łatwiejszego do odczytania map[key] = value.

netjeff
źródło
16
Należy zauważyć, że map :: insert nigdy nie zastępuje wartości. I w ogólnym przypadku powiedziałbym, że lepiej jest używać (res.first)->secondzamiast valuew drugim przypadku.
dalle
1
Zaktualizowałem, aby było bardziej jasne, że map :: insert nigdy nie zastępuje. Zostawiłem, elseponieważ myślę, że używanie valuejest bardziej przejrzyste niż iterator. Tylko jeśli typ wartości miałby nietypowy egzemplarz ctor lub op ==, byłby inny, a ten typ spowodowałby inne problemy z użyciem kontenerów STL, takich jak map.
netjeff
1
map.insert(std::make_pair(key,value))powinno być map.insert(MyMap::value_type(key,value)). Typ zwracany z make_pairnie jest zgodny z typem pobranym, inserta obecne rozwiązanie wymaga konwersji
David Rodríguez - dribeas
1
istnieje sposób, aby stwierdzić, czy wstawiłeś lub po prostu przypisałeś operator[], po prostu porównaj rozmiar przed i po. Imho może wywoływać map::operator[]tylko domyślne typy konstrukcyjne, jest o wiele ważniejsze.
idclev 463035818
@ DavidRodríguez-dribeas: Dobra sugestia, zaktualizowałem kod w odpowiedzi.
netjeff
53

Obie mają różną semantykę, jeśli chodzi o klucz już istniejący na mapie. Więc nie są tak naprawdę bezpośrednio porównywalne.

Ale wersja operatora [] wymaga domyślnego skonstruowania wartości, a następnie przypisania, więc jeśli jest to droższe niż konstrukcja kopiowania, to będzie droższe. Czasami domyślna konstrukcja nie ma sensu, a wtedy korzystanie z wersji operator [] byłoby niemożliwe.

Greg Rogers
źródło
1
make_pair może wymagać konstruktora kopiowania - byłoby to gorsze niż domyślny. W każdym razie +1.
1
Najważniejsze jest, jak powiedziałeś, że mają różną semantykę. Więc żadne nie jest lepsze od drugiego, wystarczy użyć tego, który robi to, czego potrzebujesz.
lipiec
Dlaczego konstruktor kopiowania byłby gorszy od domyślnego konstruktora, po którym następowałby przypisanie? Jeśli tak, to osoba, która napisała klasę, coś przeoczyła, ponieważ cokolwiek operator = robi, powinna była zrobić to samo w konstruktorze kopiowania.
Steve Jessop
1
Czasami domyślne budowanie jest tak samo drogie jak samo zadanie. Oczywiście przypisanie i wykonanie kopii będzie równoważne.
Greg Rogers,
@Arkadiy W zoptymalizowanej wersji kompilator często usuwa wiele niepotrzebnych wywołań konstruktora kopiowania.
antred 17.07.15
35

Kolejna rzecz, na którą warto zwrócić uwagę std::map:

myMap[nonExistingKey];utworzy nowy wpis na mapie, kluczowany do nonExistingKeyzainicjowania na wartość domyślną.

To mnie przeraziło, gdy zobaczyłem to po raz pierwszy (uderzając głową o paskudnego robaka). Nie spodziewałbym się tego. Dla mnie wygląda to na operację get i nie spodziewałem się „efektu ubocznego”. Wolę, map.find()gdy wychodzisz z mapy.

Hawkeye Parker
źródło
3
To przyzwoity widok, chociaż mapy skrótów są dość uniwersalne dla tego formatu. Może to być jedna z tych „osobliwości, o których nikt nie myśli, że jest dziwna” tylko z powodu tego, jak powszechne są te same konwencje
Stephen J
19

Jeśli hit wydajności domyślnego konstruktora nie stanowi problemu, proszę, na miłość boską, przejdź do bardziej czytelnej wersji.

:)

Torlack
źródło
5
Druga! Musisz to zaznaczyć. Zbyt wielu ludzi zamienia tępotę na przyspieszenie w ciągu sekundy. Zmiłuj się nad nami, biedne dusze, które musimy zachować takie okrucieństwa!
Mr.Ree
6
Jak napisał Greg Rogers: „Obaj mają inną semantykę, jeśli chodzi o klucz już istniejący na mapie. Nie są więc tak naprawdę bezpośrednio porównywalni”.
dalle
To jest stare pytanie i odpowiedź. Ale „bardziej czytelna wersja” to głupi powód. Ponieważ to, co jest najbardziej czytelne, zależy od osoby.
vallentin
14

insert jest lepszy z punktu widzenia bezpieczeństwa wyjątkowego.

Wyrażenie map[key] = valueto tak naprawdę dwie operacje:

  1. map[key] - tworzenie elementu mapy z wartością domyślną.
  2. = value - kopiowanie wartości do tego elementu.

Wyjątek może wystąpić na drugim etapie. W rezultacie operacja zostanie wykonana tylko częściowo (nowy element został dodany do mapy, ale tego elementu nie zainicjowano value). Sytuacja, w której operacja nie jest zakończona, ale stan systemu jest zmodyfikowany, nazywana jest operacją z „efektem ubocznym”.

insertoperacja daje silną gwarancję, oznacza, że ​​nie ma skutków ubocznych ( https://en.wikipedia.org/wiki/Exception_safety ). insertjest całkowicie gotowy lub pozostawia mapę w niezmodyfikowanym stanie.

http://www.cplusplus.com/reference/map/map/insert/ :

Jeśli ma zostać wstawiony pojedynczy element, nie ma zmian w pojemniku w przypadku wyjątku (silna gwarancja).

anton_rh
źródło
1
co ważniejsze, insert nie wymaga domyślnej wartości do zbudowania.
UmNyobe 27.04.17
13

Jeśli twoja aplikacja jest krytyczna pod względem szybkości, doradzę za pomocą operatora [], ponieważ tworzy ona w sumie 3 kopie oryginalnego obiektu, z których 2 są obiektami tymczasowymi i prędzej czy później zniszczonymi jako.

Ale w insert () tworzone są 4 kopie oryginalnego obiektu, z czego 3 są obiektami tymczasowymi (niekoniecznie „tymczasowymi”) i są niszczone.

Co oznacza dodatkowy czas na: 1. Przydział pamięci jednego obiektu 2. Jedno dodatkowe wywołanie konstruktora 3. Jedno dodatkowe wywołanie destruktora 4. Deallokacja pamięci jednego obiektu

Jeśli twoje obiekty są duże, konstruktory są typowe, destruktory uwalniają wiele zasobów, powyżej punktów liczy się jeszcze więcej. Jeśli chodzi o czytelność, uważam, że oba są wystarczająco uczciwe.

To samo pytanie przyszło mi do głowy, ale nie z powodu czytelności, ale szybkości. Oto przykładowy kod, dzięki któremu dowiedziałem się o punkcie, o którym wspomniałem.

class Sample
{
    static int _noOfObjects;

    int _objectNo;
public:
    Sample() :
        _objectNo( _noOfObjects++ )
    {
        std::cout<<"Inside default constructor of object "<<_objectNo<<std::endl;
    }

    Sample( const Sample& sample) :
    _objectNo( _noOfObjects++ )
    {
        std::cout<<"Inside copy constructor of object "<<_objectNo<<std::endl;
    }

    ~Sample()
    {
        std::cout<<"Destroying object "<<_objectNo<<std::endl;
    }
};
int Sample::_noOfObjects = 0;


int main(int argc, char* argv[])
{
    Sample sample;
    std::map<int,Sample> map;

    map.insert( std::make_pair<int,Sample>( 1, sample) );
    //map[1] = sample;
    return 0;
}

Wyprowadzane, gdy używana jest funkcja insert () Wyprowadzane, gdy używany jest operator []

Rampal Chaudhary
źródło
4
Teraz uruchom ten test ponownie z włączonymi pełnymi optymalizacjami.
antred 17.07.15
2
Zastanów się także, co faktycznie robi operator []. Najpierw przeszukuje mapę w poszukiwaniu wpisu, który pasuje do określonego klucza. Jeśli znajdzie taki, wówczas nadpisuje wartość tego wpisu określonym. Jeśli nie, wstawia nowy wpis z określonym kluczem i wartością. Im większa twoja mapa, tym dłużej operator [] przeszukuje mapę. W pewnym momencie zrekompensuje to dodatkowe wywołanie c'tor lub kopiowanie (jeśli pozostanie nawet w końcowym programie po tym, jak kompilator wykona magię optymalizacji).
antred
1
@antred, insertmusi przeprowadzić to samo wyszukiwanie, więc nie ma w tym różnicy [](ponieważ klucze map są unikalne).
Sz.
Ładna ilustracja tego, co się dzieje z wydrukami - ale co właściwie robią te 2 bity kodu? Dlaczego w ogóle potrzebne są 3 kopie oryginalnego obiektu?
rbennett485
1. musi zaimplementować operator przypisania, inaczej dostaniesz nieprawidłowe liczby w destruktorze 2. użyj std :: move podczas konstruowania pary, aby uniknąć nadmiaru tworzenia kopii "map.insert (std :: make_pair <int, Sample> (1, std: : move (sample))); "
Fl0,
10

Teraz w c ++ 11 Myślę, że najlepszym sposobem wstawienia pary do mapy STL jest:

typedef std::map<int, std::string> MyMap;
MyMap map;

auto& result = map.emplace(3,"Hello");

Wynik będzie para z:

  • Pierwszy element (score.first) wskazuje na wstawioną parę lub wskaż parę za pomocą tego klucza, jeśli klucz już istnieje.

  • Drugi element (wynik. Drugi), prawda, jeśli wstawienie było prawidłowe lub fałszywe, coś poszło nie tak.

PS: Jeśli nie masz wątpliwości co do kolejności, możesz użyć std :: unordered_map;)

Dzięki!

GutiMac
źródło
9

Gotcha z map :: insert () polega na tym, że nie zastąpi wartości, jeśli klucz już istnieje na mapie. Widziałem kod C ++ napisany przez programistów Java, w których spodziewali się, że insert () będzie zachowywać się tak samo jak Map.put () w Javie, gdzie wartości są zamieniane.

Anthony Cramp
źródło
2

Jedna uwaga jest taka, że ​​możesz także użyć funkcji Boost .

using namespace std;
using namespace boost::assign; // bring 'map_list_of()' into scope

void something()
{
    map<int,int> my_map = map_list_of(1,2)(2,3)(3,4)(4,5)(5,6);
}
rlbond
źródło
1

Oto kolejny przykład pokazujący, że operator[] nadpisuje wartość klucza, jeśli istnieje, ale .insert nie nadpisuje wartości, jeśli istnieje.

void mapTest()
{
  map<int,float> m;


  for( int i = 0 ; i  <=  2 ; i++ )
  {
    pair<map<int,float>::iterator,bool> result = m.insert( make_pair( 5, (float)i ) ) ;

    if( result.second )
      printf( "%d=>value %f successfully inserted as brand new value\n", result.first->first, result.first->second ) ;
    else
      printf( "! The map already contained %d=>value %f, nothing changed\n", result.first->first, result.first->second ) ;
  }

  puts( "All map values:" ) ;
  for( map<int,float>::iterator iter = m.begin() ; iter !=m.end() ; ++iter )
    printf( "%d=>%f\n", iter->first, iter->second ) ;

  /// now watch this.. 
  m[5]=900.f ; //using operator[] OVERWRITES map values
  puts( "All map values:" ) ;
  for( map<int,float>::iterator iter = m.begin() ; iter !=m.end() ; ++iter )
    printf( "%d=>%f\n", iter->first, iter->second ) ;

}
Bobobobo
źródło
1

Jest to raczej ograniczony przypadek, ale sądząc z otrzymanych komentarzy, myślę, że warto to zauważyć.

W przeszłości widziałem ludzi używających map w formie

map< const key, const val> Map;

aby uniknąć przypadków przypadkowego zastąpienia wartości, ale pisz dalej w kilku innych fragmentach kodu:

const_cast< T >Map[]=val;

Powodem, dla którego to zrobiłem, jak pamiętam, było to, że byli pewni, że w tych określonych fragmentach kodu nie zamierzają nadpisywać wartości map; stąd kontynuacja bardziej „czytelnej” metody[] .

Tak naprawdę nigdy nie miałem bezpośrednich problemów z kodem napisanym przez tych ludzi, ale do tej pory mocno odczuwam, że ryzyko - jakkolwiek małe - nie powinno być podejmowane, gdy można go łatwo uniknąć.

W przypadkach, gdy masz do czynienia z wartościami mapy, których absolutnie nie wolno nadpisywać, użyj insert. Nie rób wyjątków tylko dla czytelności.

dk123
źródło
Czy napisało to wiele osób? Z pewnością użyj insert(nie input), ponieważ const_castspowoduje to zastąpienie dowolnej poprzedniej wartości, co jest bardzo niestałe. Lub nie oznaczaj typu wartości jako const. (Tego rodzaju rzeczy są zwykle ostatecznym rezultatem const_cast, więc prawie zawsze jest to czerwona flaga wskazująca błąd gdzie indziej.)
Potatoswatter 27.12.12
@Potatoswatter Masz rację. Widzę tylko, że const_cast [] jest używany przez niektóre osoby z mapami const, gdy są pewni, że nie zastąpią starej wartości w niektórych bitach kodu; ponieważ sam [] jest bardziej czytelny. Jak wspomniałem w ostatnim fragmencie mojej odpowiedzi, zalecam stosowanie insertw przypadkach, w których chcesz zapobiec zastąpieniu wartości. (Właśnie zmienił inputsię insert- dzięki)
dk123
@Potatoswatter Jeśli dobrze pamiętam, główne powody, dla których ludzie wydają się używać, const_cast<T>(map[key])to: 1. [] jest bardziej czytelny, 2. są pewni pewnych fragmentów kodu, że nie będą nadpisywać wartości, i 3. nie chcą, aby inne fragmenty nieświadomego kodu nadpisały swoje wartości - stąd const value.
dk123
2
Nigdy nie słyszałem o tym; gdzie to widziałeś Pisanie const_castwydaje się bardziej niż negować dodatkową „czytelność” [], a tego rodzaju pewność jest prawie wystarczającą podstawą do zwolnienia programisty. Trudne warunki działania rozwiązują kuloodporne konstrukcje, a nie przeczucia.
Potatoswatter
@Potatoswatter Pamiętam, że podczas jednej z moich ostatnich prac zajmowałem się tworzeniem gier edukacyjnych. Nigdy nie mogłem zmusić ludzi do pisania kodu, aby zmienił ich nawyki. Masz absolutną rację i zdecydowanie się z tobą zgadzam. Na podstawie twoich komentarzy zdecydowałem, że jest to chyba bardziej warte odnotowania niż moja pierwotna odpowiedź i dlatego zaktualizowałem ją, aby to odzwierciedlić. Dzięki!
dk123
1

Fakt, że insert()funkcja std :: map nie zastępuje wartości powiązanej z kluczem, pozwala nam napisać kod wyliczenia obiektu w następujący sposób:

string word;
map<string, size_t> dict;
while(getline(cin, word)) {
    dict.insert(make_pair(word, dict.size()));
}

Jest to dość powszechny problem, gdy musimy mapować różne nieunikalne obiekty na niektóre identyfikatory w zakresie 0..N. Te identyfikatory można później wykorzystać na przykład w algorytmach graficznych. operator[]Moim zdaniem alternatywa z wyglądałaby mniej czytelnie:

string word;
map<string, size_t> dict;
while(getline(cin, word)) {
    size_t sz = dict.size();
    if (!dict.count(word))
        dict[word] = sz; 
} 
mechatroner
źródło