Какой способ вставки на карту является предпочтительным / идиоматическим?

113

Я выделил четыре разных способа вставки элементов в 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));

Какой из них предпочтительный / идиоматический? (А есть ли другой способ, о котором я не подумал?)

fredoverflow
источник
26
Ваша карта должна называться «ответы», а не «функция»
Винсент Роберт
2
@ Винсент: Хм? Функция - это в основном карта между двумя наборами.
fredoverflow
7
@FredOverflow: кажется, комментарий Винсента - своего рода шутка о какой-то книге ...
Виктор Сорокин,
1
Кажется, что это противоречит оригиналу - 42 не могут одновременно быть ответом на (а) жизнь, вселенную и все остальное и (б) ничто. Но как тогда выразить жизнь, вселенную и все остальное как целое?
Стюарт Голодец
19
@sgolodetz Все можно выразить с помощью достаточно большого int.
Яков Галка

Ответы:

90

Прежде всего, operator[]и insertфункции-члены функционально не эквивалентны:

  • operator[]Будет искать для ключа, вставьте по умолчанию строится значение , если не найдено, и возвращает ссылку на который вы присвоить значение. Очевидно, что это может быть неэффективным, если mapped_typeможет быть выгодна прямая инициализация вместо создания и назначения по умолчанию. Этот метод также делает невозможным определить, действительно ли произошла вставка или вы только перезаписали значение для ранее вставленного ключа.
  • Функция- insertчлен не будет иметь никакого эффекта, если ключ уже присутствует на карте и, хотя о нем часто забывают, возвращает значение, std::pair<iterator, bool>которое может представлять интерес (в первую очередь, чтобы определить, действительно ли была произведена вставка).

Из всех перечисленных возможностей вызова insertвсе три почти эквивалентны. Напоминаем, что давайте посмотрим на insertподпись в стандарте:

typedef pair<const Key, T> value_type;

  /* ... */

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

Так чем же отличаются эти три вызова?

  • std::make_pairполагается на вывод аргументов шаблона и может (и в этом случае будет ) создавать что-то другого типа, чем фактическая value_typeкарта, что потребует дополнительного вызова std::pairконструктора шаблона для преобразования в value_type(то есть: добавления constв first_type)
  • std::pair<int, int>также потребуется дополнительный вызов конструктора шаблона std::pair, чтобы преобразовать параметр в value_type(то есть: добавить constв first_type)
  • std::map<int, int>::value_typeне оставляет абсолютно никаких сомнений, поскольку это непосредственно тип параметра, ожидаемый insertфункцией-членом.

В конце концов, я бы избегал использования, operator[]когда целью является вставка, если только нет дополнительных затрат на построение по умолчанию и назначение mapped_type, и что меня не волнует определение того, действительно ли новый ключ вставлен. При использовании insert, value_typeвероятно, лучше всего построить a .

ледовое преступление
источник
действительно ли преобразование Key в const Key в make_pair () требует вызова другой функции? Кажется, что неявного приведения будет достаточно, какой компилятор должен это сделать.
galactica
100

Начиная с C ++ 11, у вас есть два основных дополнительных параметра. Во-первых, вы можете использовать insert()синтаксис инициализации списка:

function.insert({0, 42});

Это функционально эквивалентно

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

но гораздо более лаконичный и читаемый. Как отмечали другие ответы, это имеет несколько преимуществ по сравнению с другими формами:

  • operator[]Подход требует отображенный типа быть назначаемыми, это не всегда так.
  • Такой operator[]подход может перезаписать существующие элементы и не дает возможности узнать, произошло ли это.
  • Другие формы, insertкоторые вы перечисляете, включают неявное преобразование типов, которое может замедлить ваш код.

Главный недостаток в том, что эта форма требовала, чтобы ключ и значение были копируемыми, поэтому она не работала, например, с картой со unique_ptrзначениями. Это было исправлено в стандарте, но исправление, возможно, еще не достигло вашей стандартной реализации библиотеки.

Во-вторых, вы можете использовать emplace()метод:

function.emplace(0, 42);

Это более лаконично, чем любая из форм insert(), отлично работает с типами, предназначенными только для перемещения unique_ptr, и теоретически может быть немного более эффективным (хотя приличный компилятор должен оптимизировать разницу). Единственный серьезный недостаток заключается в том, что это может немного удивить ваших читателей, поскольку emplaceметоды обычно так не используются.

Джефф Ромер
источник
8
есть также новые insert_or_assign и try_emplace
sp2danny
12

Первая версия:

function[0] = 42; // version 1

может или не может вставить значение 42 в карту. Если ключ 0существует, то он назначит ему 42, перезаписав любое значение, которое было у этого ключа. В противном случае он вставляет пару ключ / значение.

Функции вставки:

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

с другой стороны, ничего не делайте, если ключ 0уже существует на карте. Если ключ не существует, вставляется пара ключ / значение.

Три функции вставки практически идентичны. std::map<int, int>::value_typeявляется typedeffor std::pair<const int, int>и, std::make_pair()очевидно, производит std::pair<>магию вывода через шаблон. Однако конечный результат должен быть таким же для версий 2, 3 и 4.

Какой бы я использовал? Я лично предпочитаю версию 1; это лаконично и «естественно». Конечно, если его поведение перезаписи нежелательно, я бы предпочел версию 4, поскольку она требует меньше ввода, чем версии 2 и 3. Я не знаю, существует ли де-факто единственный способ вставки пар ключ / значение в std::map.

Другой способ вставить значения в карту через один из ее конструкторов:

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
источник
5

Если вы хотите перезаписать элемент с помощью ключа 0

function[0] = 42;

В противном случае:

function.insert(std::make_pair(0, 42));
Виктор Зер
источник
5

Поскольку C ++ 17 std::map предлагает два новых метода вставки: insert_or_assign()и try_emplace(), как также упоминалось в комментарии sp2danny .

insert_or_assign()

По сути, insert_or_assign()это «улучшенная» версия operator[]. В отличие от operator[], insert_or_assign()не требует, чтобы тип значения карты был конструктивным по умолчанию. Например, следующий код не компилируется, потому MyClassчто не имеет конструктора по умолчанию:

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

Однако, если вы замените myMap[0] = MyClass(1);следующую строку, тогда код компилируется и вставка происходит, как задумано:

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

Более того, как и insert(), insert_or_assign()возвращает pair<iterator, bool>. Логическое значение - trueесли произошла вставка и было falseли выполнено присвоение. Итератор указывает на элемент, который был вставлен или обновлен.

try_emplace()

Подобно вышесказанному, try_emplace()это «улучшение» emplace(). В отличие от emplace(), try_emplace()не изменяет свои аргументы, если вставка не удалась из-за ключа, уже существующего на карте. Например, следующий код пытается разместить элемент с ключом, который уже хранится на карте (см. *):

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

Вывод (по крайней мере, для VS2017 и Coliru):

pMyObj не был вставлен
pMyObj все равно был изменен

Как видите, pMyObjбольше не указывает на исходный объект. Однако, если вы замените auto [it, b] = myMap2.emplace(0, std::move(pMyObj));следующий код, результат будет выглядеть иначе, потому что pMyObjостанется неизменным:

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

Вывод:

pMyObj не был вставлен
pMyObj pMyObj.m_i = 2

Код на Колиру

Обратите внимание: я старался, чтобы мои объяснения были как можно короче и просты, чтобы уместить их в этот ответ. Для более точного и исчерпывающего описания я рекомендую прочитать эту статью о Fluent C ++ .

гудок
источник
3

Я провел некоторое время для сравнения вышеупомянутых версий:

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

Оказывается, разница во времени между версиями вставок очень мала.

#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");
}

Это дает соответственно для версий (я запускал файл 3 раза, отсюда 3 последовательных разницы во времени для каждой):

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

2198 мс, 2078 мс, 2072 мс

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

2290 мс, 2037 мс, 2046 мс

 map_W_3[it] = Widget(2.0);

2592 мс, 2278 мс, 2296 мс

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

2234 мс, 2031 мс, 2027 мс

Следовательно, результатами между разными версиями вставок можно пренебречь (хотя проверка гипотез не проводилась)!

map_W_3[it] = Widget(2.0);Версия занимает около 10-15% больше времени для этого примера из - за инициализации с помощью конструктора по умолчанию для виджета.

user3116431
источник
2

Короче говоря, []оператор более эффективен для обновления значений, поскольку он включает вызов конструктора по умолчанию для типа значения и последующее присвоение ему нового значения, в то время как insert()он более эффективен для добавления значений.

Цитируемый отрывок из книги «Эффективный STL: 50 конкретных способов улучшить использование стандартной библиотеки шаблонов » Скотта Мейерса, пункт 24 может помочь.

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

Вы можете выбрать версию без общего программирования, но дело в том, что я считаю эту парадигму (разграничение «добавления» и «обновления») чрезвычайно полезной.

галактика
источник
1

Если вы хотите вставить элемент в std :: map - используйте функцию insert (), а если вы хотите найти элемент (по ключу) и назначить ему какой-то - используйте оператор [].

Для упрощения вставки используйте библиотеку boost :: assign, например:

using namespace boost::assign;

// For inserting one element:

insert( function )( 0, 41 );

// For inserting several elements:

insert( function )( 0, 41 )( 0, 42 )( 0, 43 );
Денис Шевченко
источник
1

Я просто немного изменил задачу (карту строк), чтобы показать другой интерес вставки:

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

тот факт, что компилятор не показывает ошибки при "rancking [1] = 42;" может иметь разрушительные последствия!

Джо_
источник
Компиляторы не показывают ошибку для первого, потому что std::string::operator=(char)существует, но они показывают ошибку для последнего, потому что конструктор std::string::string(char)не существует. Это не должно вызывать ошибки, потому что C ++ всегда свободно интерпретирует любой литерал целочисленного стиля как char, так что это не ошибка компилятора, а ошибка программиста. По сути, я просто говорю, что независимо от того, приведет ли это к ошибке в вашем коде, вы должны сами следить за собой. Кстати, вы можете распечатать, rancking[0]и компилятор, использующий ASCII, выведет *, что есть (char)(42).
Keith M