Jaki jest preferowany / idiomatyczny sposób wstawiania do mapy?

113

Zidentyfikowałem cztery różne sposoby wstawiania elementów do std::map:

std::map<int, int> function;

function[0] = 42;
function.insert(std::map<int, int>::value_type(0, 42));
function.insert(std::pair<int, int>(0, 42));
function.insert(std::make_pair(0, 42));

Który z nich jest preferowany / idiomatyczny? (Czy jest inny sposób, o którym nie pomyślałem?)

fredoverflow
źródło
26
Twoja mapa powinna nazywać się „odpowiedzi”, a nie „funkcja”
Vincent Robert
2
@Vincent: Hm? Funkcja jest w zasadzie mapą między dwoma zbiorami.
fredoverflow
7
@FredOverflow: wydaje się, że komentarz Vincenta jest trochę żartem na temat pewnej książki ...
Victor Sorokin
1
Wydaje się, że zaprzecza oryginałowi - 42 nie może być jednocześnie odpowiedzią na (a) życie, wszechświat i wszystko oraz (b) nic. Ale w takim razie, jak wyrazisz życie, wszechświat i wszystko jako int?
Stuart Golodetz
19
@sgolodetz Możesz wyrazić wszystko za pomocą wystarczająco dużego rozmiaru.
Yakov Galka

Odpowiedzi:

90

Przede wszystkim, operator[]i insertfunkcje składowe nie są funkcjonalnie równoważne:

  • operator[]Będzie szukać klucza, włóż domyślny skonstruowana wartość, jeśli nie znaleziono, i zwraca referencję do których można przypisać wartość. Oczywiście może to być nieefektywne, jeślimapped_type może skorzystać z bezpośredniego zainicjowania zamiast domyślnego konstruowania i przypisywania. Ta metoda uniemożliwia również określenie, czy wstawienie rzeczywiście miało miejsce, czy też nadpisałeś tylko wartość dla wcześniej wstawionego klucza
  • Funkcja insertczłonkowska nie odniesie żadnego skutku, jeśli klucz jest już obecny na mapie i chociaż często o nim zapomina, zwraca wartość, std::pair<iterator, bool>która może być interesująca (przede wszystkim w celu ustalenia, czy wstawienie zostało faktycznie wykonane).

Ze wszystkich wymienionych możliwości dzwonienia insertwszystkie trzy są prawie równoważne. Dla przypomnienia spójrzmy na insertpodpis w standardzie:

typedef pair<const Key, T> value_type;

  /* ... */

pair<iterator, bool> insert(const value_type& x);

Więc czym różnią się te trzy rozmowy?

  • std::make_pairopiera się na dedukcji argumentów szablonu i może (iw tym przypadku będzie ) wytwarzać coś innego typu niż rzeczywista value_typemapa, co będzie wymagało dodatkowego wywołania std::pairkonstruktora szablonu w celu konwersji na value_type(tj: dodawanie constdo first_type)
  • std::pair<int, int>będzie również wymagało dodatkowego wywołania konstruktora szablonu std::pairw celu przekonwertowania parametru na value_type(np .: dodanie constdo first_type)
  • std::map<int, int>::value_typenie pozostawia żadnych wątpliwości, ponieważ jest to bezpośrednio typ parametru oczekiwany przez insertfunkcję składową.

Ostatecznie unikałbym używania, operator[]gdy celem jest wstawienie, chyba że nie ma dodatkowych kosztów w domyślnym konstruowaniu i przypisywaniu mapped_type, oraz że nie obchodzi mnie ustalanie, czy nowy klucz został skutecznie włożony. Podczas używania insert, konstruowanie value_typejest prawdopodobnie najlepszym rozwiązaniem.

przestępczość lodowa
źródło
czy konwersja z Key na const Key w make_pair () naprawdę wymaga innego wywołania funkcji? Wydaje się, że niejawne rzutowanie wystarczyłoby, który kompilator byłby szczęśliwy, aby to zrobić.
galactica
99

Od C ++ 11 masz dwie główne dodatkowe opcje. Po pierwsze, możesz użyć insert()ze składnią inicjalizacji listy:

function.insert({0, 42});

Jest to funkcjonalnie równoważne z

function.insert(std::map<int, int>::value_type(0, 42));

ale o wiele bardziej zwięzłe i czytelne. Jak zauważyły ​​inne odpowiedzi, ma to kilka zalet w porównaniu z innymi formami:

  • Plik operator[]Podejście wymaga rodzaj zmapowanych być przypisane, co nie zawsze jest prawdą.
  • Plik operator[] podejście może nadpisać istniejące elementy i nie daje możliwości stwierdzenia, czy tak się stało.
  • Inne formy tego insert, które wymienisz, obejmują niejawną konwersję typów, która może spowolnić kod.

Główną wadą jest to, że kiedyś ten formularz wymagał kopiowania klucza i wartości, więc nie działałby np. Z mapą z unique_ptrwartościami. Zostało to naprawione w standardzie, ale poprawka może nie dotarła jeszcze do implementacji standardowej biblioteki.

Po drugie, możesz skorzystać z emplace()metody:

function.emplace(0, 42);

Jest to bardziej zwięzłe niż którakolwiek z form programu insert(), działa dobrze z typami tylko do przenoszenia unique_ptr, i teoretycznie może być nieco bardziej wydajne (chociaż przyzwoity kompilator powinien zoptymalizować różnicę). Jedyną poważną wadą jest to, że może to trochę zaskoczyć czytelników, ponieważ emplacemetody nie są zwykle używane w ten sposób.

Geoff Romer
źródło
8
jest też nowy insert_or_ assign i try_emplace
sp2danny
12

Pierwsza wersja:

function[0] = 42; // version 1

może, ale nie musi, wstawić wartość 42 do mapy. Jeśli klucz0 istnieje, przypisze 42 do tego klucza, nadpisując jakąkolwiek wartość, jaką miał ten klucz. W przeciwnym razie wstawia parę klucz / wartość.

Funkcje wstawiania:

function.insert(std::map<int, int>::value_type(0, 42));  // version 2
function.insert(std::pair<int, int>(0, 42));             // version 3
function.insert(std::make_pair(0, 42));                  // version 4

z drugiej strony nie rób nic, jeśli klucz 0 już istnieje na mapie. Jeśli klucz nie istnieje, wstawia parę klucz / wartość.

Trzy funkcje wstawiania są prawie identyczne. std::map<int, int>::value_typejest typedeffor std::pair<const int, int>i std::make_pair()oczywiście produkujestd::pair<> magię dedukcji za pomocą szablonu. Jednak wynik końcowy powinien być taki sam dla wersji 2, 3 i 4.

Którego bym użył? Osobiście wolę wersję 1; jest zwięzła i „naturalna”. Oczywiście, jeśli jego nadpisywanie nie jest pożądane, wolałbym wersję 4, ponieważ wymaga mniej wpisywania niż wersje 2 i 3. Nie wiem, czy istnieje jeden de facto sposób wstawiania par klucz / wartość do std::map.

Inny sposób wstawiania wartości do mapy za pomocą jednego z jej konstruktorów:

std::map<int, int> quadratic_func;

quadratic_func[0] = 0;
quadratic_func[1] = 1;
quadratic_func[2] = 4;
quadratic_func[3] = 9;

std::map<int, int> my_func(quadratic_func.begin(), quadratic_func.end());
In silico
źródło
5

Jeśli chcesz nadpisać element kluczem 0

function[0] = 42;

Inaczej:

function.insert(std::make_pair(0, 42));
Viktor Sehr
źródło
5

Od C ++ 17 std::map oferuje dwie nowe metody wstawiania: insert_or_assign()i try_emplace(), jak również wspomniano w komentarzu sp2danny .

insert_or_assign()

Zasadniczo insert_or_assign()jest to „ulepszona” wersja operator[]. W przeciwieństwie do operator[], insert_or_assign()nie wymaga, aby typ wartości mapy był domyślnym konstruowalnym. Na przykład poniższy kod nie jest kompilowany, ponieważ MyClassnie ma domyślnego konstruktora:

class MyClass {
public:
    MyClass(int i) : m_i(i) {};
    int m_i;
};

int main() {
    std::map<int, MyClass> myMap;

    // VS2017: "C2512: 'MyClass::MyClass' : no appropriate default constructor available"
    // Coliru: "error: no matching function for call to 'MyClass::MyClass()"
    myMap[0] = MyClass(1);

    return 0;
}

Jeśli jednak zastąpisz myMap[0] = MyClass(1);ją następującym wierszem, kod zostanie skompilowany, a wstawienie nastąpi zgodnie z zamierzeniami:

myMap.insert_or_assign(0, MyClass(1));

Ponadto, podobnie jak insert(), insert_or_assign()zwraca pair<iterator, bool>. Wartość logiczna dotyczy truesytuacji, w której nastąpiło wstawienie i falsejeśli przypisanie zostało wykonane. Iterator wskazuje na element, który został wstawiony lub zaktualizowany.

try_emplace()

Podobnie jak powyżej, try_emplace()jest „ulepszeniem” emplace(). W przeciwieństwie do emplace(), try_emplace()nie modyfikuje swoich argumentów, jeśli wstawianie nie powiedzie się z powodu klucza już istniejącego w mapie. Na przykład poniższy kod próbuje umieścić element z kluczem, który jest już przechowywany w mapie (patrz *):

int main() {
    std::map<int, std::unique_ptr<MyClass>> myMap2;
    myMap2.emplace(0, std::make_unique<MyClass>(1));

    auto pMyObj = std::make_unique<MyClass>(2);    
    auto [it, b] = myMap2.emplace(0, std::move(pMyObj));  // *

    if (!b)
        std::cout << "pMyObj was not inserted" << std::endl;

    if (pMyObj == nullptr)
        std::cout << "pMyObj was modified anyway" << std::endl;
    else
        std::cout << "pMyObj.m_i = " << pMyObj->m_i <<  std::endl;

    return 0;
}

Wyjście (przynajmniej dla VS2017 i Coliru):

pMyObj nie został wstawiony
pMyObj i tak został zmodyfikowany

Jak widać, pMyObjnie wskazuje już na oryginalny obiekt. Jeśli jednak zastąpisz auto [it, b] = myMap2.emplace(0, std::move(pMyObj));poniższym kodem, dane wyjściowe będą wyglądać inaczej, ponieważ pMyObjpozostają niezmienione:

auto [it, b] = myMap2.try_emplace(0, std::move(pMyObj));

Wynik:

pMyObj nie został wstawiony
pMyObj pMyObj.m_i = 2

Kod na Coliru

Uwaga: starałem się, aby moje wyjaśnienia były jak najkrótsze i najprostsze, aby dopasować je do tej odpowiedzi. Aby uzyskać bardziej precyzyjny i wyczerpujący opis, polecam przeczytanie tego artykułu na temat Fluent C ++ .

dźwięk klaksonu
źródło
3

Dokonałem porównań czasowych między w / w wersjami:

function[0] = 42;
function.insert(std::map<int, int>::value_type(0, 42));
function.insert(std::pair<int, int>(0, 42));
function.insert(std::make_pair(0, 42));

Okazuje się, że różnice czasowe między wersjami wkładek są niewielkie.

#include <map>
#include <vector>
#include <boost/date_time/posix_time/posix_time.hpp>
using namespace boost::posix_time;
class Widget {
public:
    Widget() {
        m_vec.resize(100);
        for(unsigned long it = 0; it < 100;it++) {
            m_vec[it] = 1.0;
        }
    }
    Widget(double el)   {
        m_vec.resize(100);
        for(unsigned long it = 0; it < 100;it++) {
            m_vec[it] = el;
        }
    }
private:
    std::vector<double> m_vec;
};


int main(int argc, char* argv[]) {



    std::map<int,Widget> map_W;
    ptime t1 = boost::posix_time::microsec_clock::local_time();    
    for(int it = 0; it < 10000;it++) {
        map_W.insert(std::pair<int,Widget>(it,Widget(2.0)));
    }
    ptime t2 = boost::posix_time::microsec_clock::local_time();
    time_duration diff = t2 - t1;
    std::cout << diff.total_milliseconds() << std::endl;

    std::map<int,Widget> map_W_2;
    ptime t1_2 = boost::posix_time::microsec_clock::local_time();    
    for(int it = 0; it < 10000;it++) {
        map_W_2.insert(std::make_pair(it,Widget(2.0)));
    }
    ptime t2_2 = boost::posix_time::microsec_clock::local_time();
    time_duration diff_2 = t2_2 - t1_2;
    std::cout << diff_2.total_milliseconds() << std::endl;

    std::map<int,Widget> map_W_3;
    ptime t1_3 = boost::posix_time::microsec_clock::local_time();    
    for(int it = 0; it < 10000;it++) {
        map_W_3[it] = Widget(2.0);
    }
    ptime t2_3 = boost::posix_time::microsec_clock::local_time();
    time_duration diff_3 = t2_3 - t1_3;
    std::cout << diff_3.total_milliseconds() << std::endl;

    std::map<int,Widget> map_W_0;
    ptime t1_0 = boost::posix_time::microsec_clock::local_time();    
    for(int it = 0; it < 10000;it++) {
        map_W_0.insert(std::map<int,Widget>::value_type(it,Widget(2.0)));
    }
    ptime t2_0 = boost::posix_time::microsec_clock::local_time();
    time_duration diff_0 = t2_0 - t1_0;
    std::cout << diff_0.total_milliseconds() << std::endl;

    system("pause");
}

To daje odpowiednio dla wersji (uruchomiłem plik 3 razy, stąd 3 kolejne różnice czasu dla każdej):

map_W.insert(std::pair<int,Widget>(it,Widget(2.0)));

2198 ms, 2078 ms, 2072 ms

map_W_2.insert(std::make_pair(it,Widget(2.0)));

2290 ms, 2037 ms, 2046 ms

 map_W_3[it] = Widget(2.0);

2592 ms, 2278 ms, 2296 ms

 map_W_0.insert(std::map<int,Widget>::value_type(it,Widget(2.0)));

2234 ms, 2031 ms, 2027 ms

W związku z tym można pominąć wyniki między różnymi wersjami wkładek (chociaż nie przeprowadzono testu hipotezy)!

map_W_3[it] = Widget(2.0);Wersja trwa około 10-15% więcej czasu na ten przykład ze względu na inicjalizacji z konstruktora domyślnego dla widgetu.

user3116431
źródło
2

Krótko mówiąc, []operator jest bardziej wydajny w aktualizowaniu wartości, ponieważ polega na wywołaniu domyślnego konstruktora typu wartości, a następnie przypisaniu mu nowej wartości, podczas gdyinsert() jest bardziej wydajny w dodawaniu wartości.

Cytowany fragment z Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library autorstwa Scotta Meyersa może pomóc.

template<typename MapType, typename KeyArgType, typename ValueArgType>
typename MapType::iterator
insertKeyAndValue(MapType& m, const KeyArgType&k, const ValueArgType& v)
{
    typename MapType::iterator lb = m.lower_bound(k);

    if (lb != m.end() && !(m.key_comp()(k, lb->first))) {
        lb->second = v;
        return lb;
    } else {
        typedef typename MapType::value_type MVT;
        return m.insert(lb, MVT(k, v));
    }
}

Możesz zdecydować się na wybranie wersji wolnej od programowania ogólnego, ale chodzi o to, że uważam ten paradygmat (rozróżnienie „dodaj” i „zaktualizuj”) za niezwykle przydatny.

galactica
źródło
1

Jeśli chcesz wstawić element do std :: map - użyj funkcji insert (), a jeśli chcesz znaleźć element (po klawiszu) i przypisać do niego jakiś - użyj operatora [].

Aby uprościć wstawianie, użyj biblioteki boost :: assign, na przykład:

using namespace boost::assign;

// For inserting one element:

insert( function )( 0, 41 );

// For inserting several elements:

insert( function )( 0, 41 )( 0, 42 )( 0, 43 );
Denisa Szewczenki
źródło
1

Po prostu trochę zmieniam problem (mapa strun), aby pokazać inne zainteresowanie insertem:

std::map<int, std::string> rancking;

rancking[0] = 42;  // << some compilers [gcc] show no error

rancking.insert(std::pair<int, std::string>(0, 42));// always a compile error

fakt, że kompilator nie wyświetla błędu na "rancking [1] = 42;" może mieć niszczycielski wpływ!

jo_
źródło
Kompilatory nie wyświetlają błędu dla pierwszego, ponieważ std::string::operator=(char)istnieje, ale pokazują błąd dla drugiego, ponieważ konstruktor std::string::string(char)nie istnieje. Nie powinno to powodować błędu, ponieważ C ++ zawsze swobodnie interpretuje dowolny literał typu całkowitego jako char, więc nie jest to błąd kompilatora, ale zamiast tego jest to błąd programisty. Zasadniczo mówię tylko, że to, czy powoduje to błąd w kodzie, jest czymś, na co musisz uważać. BTW, możesz drukować, rancking[0]a kompilator używający ASCII wypisze *, czyli (char)(42).
Keith M