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

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?)

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.

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.

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());

Jeśli chcesz nadpisać element kluczem 0

function[0] = 42;

Inaczej:

function.insert(std::make_pair(0, 42));

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

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.

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.

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

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!