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

Question

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

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

Answer 1

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

function.insert({0, 42});

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

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

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

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

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

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

function.emplace(0, 42);

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

Answer 2

Прежде всего, функции-члены 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.

Answer 3

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

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 - это typedef для 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());

Answer 4

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

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% больше времени из-за инициализации конструктором по умолчанию для Widget.

Answer 5

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

Цитируемый фрагмент из Effective 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));
    }
}

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

Answer 6

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

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;"может иметь разрушительные последствия!

Answer 7

Если вы хотите вставить элемент в 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 );

Answer 8

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

function[0] = 42;

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

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