15

哪种给地图赋值的方法最有效？还是它们都针对相同的代码进行了优化（在大多数现代编译器上）？

   // 1) Assignment using array index notation
   Foo["Bar"] = 12345;

   // 2) Assignment using member function insert() and STL pair
   Foo.insert(std::pair<string,int>("Bar", 12345));

   // 3) Assignment using member function insert() and "value_type()"
   Foo.insert(map<string,int>::value_type("Bar", 12345));

   // 4) Assignment using member function insert() and "make_pair()"
   Foo.insert(std::make_pair("Bar", 12345));

（我知道我可以对编译器输出进行基准测试和检查，但是现在出现了这个问题，我手边唯一的东西就是我的手机......呵呵）

4

6 回答 6

30

[]首先，和之间存在语义差异insert：

  • []将替换旧值（如果有）
  • insert将忽略新值（如果旧值已经存在）

因此，将两者进行比较通常是没有用的。

关于插入版本：

  • std::map<std::string, int>::value_type 3和4之间 std::pair<std::string const, int>没有（重要的）区别
  • std::make_pair("Bar", 12345)比std::pair<std::string, int>("Bar", 12345)因为该std::string类型是一个完整的类，具有要在复制上执行的操作并且"Bar"只是一个字符串文字（因此只是一个指针副本）而便宜；但是，由于最后您确实需要创建std::string... 这将取决于您的编译器的质量

一般来说，我会推荐：

  • []用于更新
  • insert(std::make_pair())用于忽略重复

std::make_pair不仅更短，而且还尊重 DRY 准则：不要重复自己。

不过，为了完整起见，最快（也是最简单的）将是emplace（启用 C++11）：

map.emplace("Bar", 12345);

它的行为是 的insert，但它就地构造新元素。

于 2013-01-08T15:20:53.743 回答
2

1) 可能比其他方法稍慢，因为std::map::operator[]首先默认创建对象，如果它不存在，然后返回一个引用，您可以使用operator=它来设置所需的值，即两个操作。

2-4) 应该是等价的，因为map::value_type它是相同类型的 typedef std::pair，因此make_pair也是等价的。编译器应该同样对待这些。

另请注意，如果您需要检查是否存在（例如，根据它是否存在执行特殊逻辑）然后还插入它，则可以进一步提高性能，方法map::lower_bound是首先获得元素应该在哪里的提示，所以map::insert不必map再次搜索整个：

 // get the iterator to where the key *should* be if it existed:
 std::map::iterator hint = mymap.lower_bound(key);

 if (hint == mymap.end() || mymap.key_comp()(key, hint->first)) {
     // key didn't exist in map
     // special logic A here...

     // insert at the correct location
     mymap.insert(hint, make_pair(key, new_value));
 } else { 
     // key exists in map already
     // special logic B here...

     // just update value
     hint->second = new_value;
 }
于 2013-01-08T15:21:08.657 回答
1

您的第一种可能性：Foo["Bar"] = 12345;与其他人的语义有些不同——如果不存在（与其他人一样），它将插入一个新对象，但如果不存在则覆盖当前内容（insert如果该密钥已经存在，其他人使用将失败） .

就速度而言，它有可能比其他速度慢。当您插入一个新对象时，它会创建一个具有指定键和默认构造的 value_type 的对，然后分配正确的 value_type。其他人都构造了正确的键和值对并插入该对象。然而，公平地说，我的经验是差异很少显着（对于较旧的编译器，它更重要，但对于较新的编译器则非常小）。

接下来的两个是等价的。您只是使用两种不同的方式来命名同一类型。在运行时，它们之间根本没有区别。

第四个使用模板函数（make_pair），理论上可能涉及额外级别的函数调用。不过，如果您仔细确保编译器完全没有进行任何优化（尤其是内联）（可能），我会很惊讶地看到与此有真正的区别。

底线：第一个通常会比其他的慢一点（但并非总是如此，也不会慢很多）。其他三个几乎总是相等的（例如：通常期望任何合理的编译器为所有三个生成相同的代码），即使第四个速度较慢有理论上的理由。

于 2013-01-08T15:24:54.047 回答
1

尽管已经有几个很好的答案，但我认为我不妨做一个快速基准测试。每个运行 500 万次，并使用 c++11 的 chrono 来测量它所花费的时间。

继承人的代码：

#include <string>
#include <map>
#include <chrono>
#include <cstdio>

// 5 million
#define times 5000000

int main()
{
    std::map<std::string, int> foo1, foo2, foo3, foo4, foo5;
    std::chrono::steady_clock::time_point timeStart, timeEnd;
    int x = 0;

    // 1) Assignment using array index notation
    timeStart = std::chrono::steady_clock::now();
    for (x = 0; x <= times; x++)
    {
        foo1[std::to_string(x)] = 12345;
    }
    timeEnd = std::chrono::steady_clock::now();
    printf("1) took %i milliseconds\n", (unsigned long long)std::chrono::duration_cast<std::chrono::milliseconds>(timeEnd-timeStart).count());

    // 2) Assignment using member function insert() and STL pair
    timeStart = std::chrono::steady_clock::now();
    for (x = 0; x <= times; x++)
    {
        foo2.insert(std::pair<std::string, int>(std::to_string(x), 12345));
    }
    timeEnd = std::chrono::steady_clock::now();
    printf("2) took %i milliseconds\n", (unsigned long long)std::chrono::duration_cast<std::chrono::milliseconds>(timeEnd-timeStart).count());

    // 3) Assignment using member function insert() and "value_type()"
    timeStart = std::chrono::steady_clock::now();
    for (x = 0; x <= times; x++)
    {
        foo3.insert(std::map<std::string, int>::value_type(std::to_string(x), 12345));
    }
    timeEnd = std::chrono::steady_clock::now();
    printf("3) took %i milliseconds\n", (unsigned long long)std::chrono::duration_cast<std::chrono::milliseconds>(timeEnd-timeStart).count());

    // 4) Assignment using member function insert() and "make_pair()"
    timeStart = std::chrono::steady_clock::now();
    for (x = 0; x <= times; x++)
    {
        foo4.insert(std::make_pair(std::to_string(x), 12345));
    }
    timeEnd = std::chrono::steady_clock::now();
    printf("4) took %i milliseconds\n", (unsigned long long)std::chrono::duration_cast<std::chrono::milliseconds>(timeEnd-timeStart).count());

    // 5) Matthieu M.'s suggestion of C++11's emplace
    timeStart = std::chrono::steady_clock::now();
    for (x = 0; x <= times; x++)
    {
        foo5.emplace(std::to_string(x), 12345);
    }
    timeEnd = std::chrono::steady_clock::now();
    printf("5) took %i milliseconds\n", (unsigned long long)std::chrono::duration_cast<std::chrono::milliseconds>(timeEnd-timeStart).count());

    return 0;
}

500 万次迭代的输出为：

1) took 23448 milliseconds
2) took 22854 milliseconds
3) took 22372 milliseconds
4) took 22988 milliseconds
5) took 21356 milliseconds

海合会版本：

g++ (Built by MinGW-builds project) 4.8.0 20121225 (experimental)

我的机器：

Intel i5-3570k overclocked at 4.6 GHz

EDIT1：修复了代码并重新进行了基准测试。

EDIT2：添加了 Matthieu M. 对 C++11 的 emplace 的建议，他是对的，emplace 是最快的

于 2013-01-08T15:47:10.097 回答
0

第三个是最佳选择（恕我直言），但 2、3 和 4 是相等的。

// 3) Assignment using member function insert() and "value_type()"
Foo.insert(map<string,int>::value_type("Bar", 12345));

为什么我认为第三个是最佳选择：您只执行一个操作来插入值：只需插入（好吧，也有搜索），您可以知道值是否被插入，检查second返回值的成员并且实现授权不覆盖该值。

的使用value_type也有好处：您不需要知道映射类型或键类型，因此对模板编程很有用。

最糟糕的（恕我直言）是第一个：

// 1) Assignment using array index notation
Foo["Bar"] = 12345;

您正在调用std::map::operator[]wich 创建一个对象并返回对它的引用，然后operator =调用映射的对象。您正在为插入执行两项操作：首先是插入，其次是分配。

它还有另一个问题：你不知道值是被插入还是被覆盖。

于 2013-01-08T15:21:04.653 回答
0

如果该关键位置没有对象，则：

std::map::emplace是最有效的。 insert是第二个（但会非常接近）。 []效率最低。

[]，如果那里没有对象，平凡的构造一。然后它调用operator=.

insert对std::pair参数进行复制构造函数调用。

但是，在地图的情况下，map.insert( make_pair( std::move(key), std::move(value) ) )将接近map.emplace( std::move(key), std::move(value) ).

如果关键位置有对象，则[]调用operator=，而insert/emplace将销毁旧对象并创建一个新对象。 []在这种情况下很容易便宜。

最后，这取决于operator=您的密钥和价值与复制构造、微不足道的构造与析构函数的成本是多少。

在树形结构中查找事物的实际工作std::map将非常接近相同，这并不好笑。

于 2013-01-08T15:27:24.157 回答