C++：探索std::map和std::unordered_map中的添加操作

傷城~ 2022-04-22 07:52 241阅读 0赞

std::map和std::unordered\_map主要提供如下几种添加操作：

1.  try\_emplace ()   (C++17)
2.  emplace ()
3.  insert()
4.  \[\] =

下面给出一段测试代码，观察对象在添加到std::map中时，构造对象过程中会有什么区别：

#include <map>
    #include <iostream>
    #include <tuple>
    #include <exception>
    #include <string>
    #include <memory>
    #include <vector>
    
    using namespace std;
    
    class Kid {
    private:
      static int cnt;
      int id;
    public:
      string name;
      int age;
      Kid() {
        id = ++cnt;
        cout << "Kid()" << id << endl;
      }
      Kid(string _name, int _age) : name(_name), age(_age) {
        id = ++cnt;
        cout << "Kid(string _name, int _age)" << id << endl;
      }
      Kid(const Kid&) {
        id = ++cnt;
        cout << "Kid(const Kid&)" << id << endl;
      }
      Kid(Kid&&) {
        id = ++cnt;
        cout << "Kid(Kid&&)" << id << endl;
      }
      Kid& operator=(const Kid&) {
        cout << "operator=(const Kid&)" << id << endl;
    
        return *this;
      }
      bool operator< (const Kid& rhs) const
      {
        return this->age < rhs.age;
      }
    };
    int Kid::cnt = 0;
    
    class People {
    private:
      static int cnt;
      int id;
    public:
      string name;
      int age;
      People() {
        id = ++cnt;
        cout << "People()" << id << endl;
      }
      People(string _name, int _age) : name(_name), age(_age) {
        id = ++cnt;
        cout << "People(string _name, int _age)" << id << endl;
      }
      People(const People&) {
        id = ++cnt;
        cout << "People(const People&)" << id << endl;
      }
      People(People&&) {
        id = ++cnt;
        cout << "People(People&&)" << id << endl;
      }
      People& operator=(const People&) {
        cout << "operator=(const People&)" << id << endl;
        return *this;
      }
    };
    
    int People::cnt = 0;
    
    int main() {
      map<Kid, People> m;
      cout << "--------------------------------" << endl;
     
      {
        cout << "--------------------------------//(1)" << endl;
        Kid x1("xxl", 1213332);
        m.try_emplace(x1, "xlx", 121);
      }
      {
        cout << "--------------------------------//(2)" << endl;
        m.try_emplace(Kid("xxl", 1213332), "xlx", 121);
      }
      {
        cout << "--------------------------------//(3)" << endl;
        Kid x1("xxl", 1213332);
        People p1("xlx", 121);
        m.emplace(x1, p1);
      }
      {
        cout << "--------------------------------//(4)" << endl;
        m.emplace(Kid("xxl", 1213332), People("aaaa", 121));
      }
      {
        cout << "--------------------------------//(5)" << endl;
        m.emplace(make_pair(Kid("xxl", 1213332), People("aaaa", 121)));
      }
      {
        cout << "--------------------------------//(6)" << endl;
        m.emplace(std::piecewise_construct, std::forward_as_tuple("fffff", 999), std::forward_as_tuple("wwww", 121));
      }
      {
        cout << "--------------------------------//(7)" << endl;
        m.insert(make_pair(Kid("xxl", 1213332), People("aaaa", 121)));
      }
      {
        cout << "--------------------------------//(8)" << endl;
        m[Kid("xxl", 1213332)]= People("aaaa", 121);
      }
    
      cout << "--------------------------------" << endl;
    
      return 1;
    }

VC++2017的运行结果：

> \--------------------------------  
> \--------------------------------//(1)  
> Kid(string \_name, int \_age)3  
> Kid(const Kid&)4  
> People(string \_name, int \_age)3  
> \--------------------------------//(2)  
> Kid(string \_name, int \_age)5  
> Kid(Kid&&)6  
> People(string \_name, int \_age)4  
> \--------------------------------//(3)  
> Kid(string \_name, int \_age)7  
> People(string \_name, int \_age)5  
> Kid(const Kid&)8  
> People(const People&)6  
> \--------------------------------//(4)  
> People(string \_name, int \_age)7  
> Kid(string \_name, int \_age)9  
> Kid(Kid&&)10  
> People(People&&)8  
> \--------------------------------//(5)  
> People(string \_name, int \_age)9  
> Kid(string \_name, int \_age)11  
> Kid(Kid&&)12  
> People(People&&)10  
> Kid(Kid&&)13  
> People(People&&)11  
> \--------------------------------//(6)  
> Kid(string \_name, int \_age)14  
> People(string \_name, int \_age)12  
> \--------------------------------//(7)  
> People(string \_name, int \_age)13  
> Kid(string \_name, int \_age)15  
> Kid(Kid&&)16  
> People(People&&)14  
> Kid(Kid&&)17  
> People(People&&)15  
> \--------------------------------//(8)  
> People(string \_name, int \_age)16  
> Kid(string \_name, int \_age)18  
> Kid(Kid&&)19  
> People()17  
> operator=(const People&)4  
> \--------------------------------

从以上运行结果中可以看到，只讲对象构造效率的话，效率从高到低依次为：

(6) > (2) > (4) > (5) (7) > (1) > (3) > (8)

其中(6)只调用了2次构造函数，(2)调用了2次构造函数和1次转移构造函数，(4)调用了2次构造函数和2次转移构造函数，(5)(7)调用了2次构造函数和4次转移构造函数，(1)调用了2次构造函数和1次拷贝构造函数，(3)调用了2次构造函数和2次拷贝构造函数，(8)调用了3次构造函数、1次拷贝构造函数和1次赋值函数。但对象构造效率高低还不能决定添加操作的效率，即添加操作的效率排名不一定退以上排名一样。

下面对以上几种方式分别进行代码测试，代码如下：

#include <iostream>
    #include <sstream>
    #include <fstream>
    #include <tuple>
    #include <exception>
    #include <string>
    #include <vector>
    #include <functional>
    #include <array>
    #include <chrono>
    #include <unordered_map>
    #include <map>
    #include <cstdlib>
    #include <ctime>
    #include <climits>
    
    using namespace std;
    
    class Kid_ {
    private:
      static int cnt;
      int id;
    public:
      string name;
      int money;
      Kid_() {
        id = ++cnt;
      }
      Kid_(string& _name, int& _money) : name(_name), money(_money) {
        id = ++cnt;
      }
      Kid_(const Kid_& k) : name(k.name), money(k.money) {
        id = ++cnt;
      }
      Kid_(Kid_&& k) : name(move(k.name)), money(move(k.money)) {
        id = ++cnt;
      }
    
      bool operator< (const Kid_& rhs) const {
        return this->name < rhs.name;
      }
    };
    int Kid_::cnt = 0;
    
    class People_ {
    private:
      static int cnt;
      int id;
    public:
      string name;
      int money;
      People_() {
        id = ++cnt;
      }
      People_(string& _name, int& _money) : name(_name), money(_money) {
        id = ++cnt;
      }
      People_(const People_& p) : name(p.name), money(p.money) {
        id = ++cnt;
      }
      People_(People_&& p) : name(move(p.name)), money(move(p.money)) {
        id = ++cnt;
      }
    };
    int People_::cnt = 0;
    
    struct KeyHash {
      std::size_t operator()(const Kid_& k) const
      {
        return std::hash<string>()(k.name) ^ k.money;
      }
    };
    
    struct KeyEqual {
      bool operator()(const Kid_& lhs, const Kid_& rhs) const
      {
        return lhs.name == rhs.name && lhs.money == rhs.money;
      }
    };
    
    string getRandomString(int length) {
      string ret;
    
      for (int i = 0; i < length; i++) {
        int r = std::rand() % 10;
    
        if (i == 0 && r ==0) {  
          i--;
          continue;
        }
    
        ret += to_string(r);
      }
    
      return ret;
    }
    
    void testMapAdd() {
      std::srand(std::time(0));
      int times = 1000000;
    
      cout << "--------------------------------//map" << endl;
    
      {
        long long timeUsed = 0;
        map<Kid_, People_ > m;
    
        cout << "--------------------------------//(1)" << endl;
        for (int i = 0; i < times; i++) {
          string s1 = getRandomString(10);
          int r1 = std::rand();
          string s2 = getRandomString(10);
          int r2 = std::rand();
    
          auto start = std::chrono::system_clock::now();
          Kid_ k(s1, r1);
          m.try_emplace(k, s2, r2);
          auto end = std::chrono::system_clock::now();
    
          timeUsed += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    
        cout << timeUsed << ":\t" << ((float)timeUsed / times) << endl;
      }
      {
        long long timeUsed = 0;
        map<Kid_, People_ > m;
    
        cout << "--------------------------------//(2)" << endl;
        for (int i = 0; i < times; i++) {
          string s1 = getRandomString(10);
          int r1 = std::rand();
          string s2 = getRandomString(10);
          int r2 = std::rand();
    
          auto start = std::chrono::system_clock::now();
          m.try_emplace(Kid_(s1, r1), s2, r2);
          auto end = std::chrono::system_clock::now();
    
          timeUsed += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    
        cout << timeUsed << ":\t" << ((float)timeUsed / times) << endl;
      }
      {
        long long timeUsed = 0;
        map<Kid_, People_ > m;
    
        cout << "--------------------------------//(3)" << endl;
        for (int i = 0; i < times; i++) {
          string s1 = getRandomString(10);
          int r1 = std::rand();
          string s2 = getRandomString(10);
          int r2 = std::rand();
    
          auto start = std::chrono::system_clock::now();
          Kid_ x1(s1, r1);
          People_ p1(s2, r2);
          m.emplace(x1, p1);
          auto end = std::chrono::system_clock::now();
    
          timeUsed += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    
        cout << timeUsed << ":\t" << ((float)timeUsed / times) << endl;
      }
      {
        long long timeUsed = 0;
        map<Kid_, People_ > m;
    
        cout << "--------------------------------//(4)" << endl;
        for (int i = 0; i < times; i++) {
          string s1 = getRandomString(10);
          int r1 = std::rand();
          string s2 = getRandomString(10);
          int r2 = std::rand();
    
          auto start = std::chrono::system_clock::now();
          m.emplace(Kid_(s1, r1), People_(s2, r2));
          auto end = std::chrono::system_clock::now();
    
          timeUsed += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    
        cout << timeUsed << ":\t" << ((float)timeUsed / times) << endl;
      }
      {
        long long timeUsed = 0;
        map<Kid_, People_ > m;
    
        cout << "--------------------------------//(5)" << endl;
        for (int i = 0; i < times; i++) {
          string s1 = getRandomString(10);
          int r1 = std::rand();
          string s2 = getRandomString(10);
          int r2 = std::rand();
    
          auto start = std::chrono::system_clock::now();
          m.emplace(make_pair(Kid_(s1, r1), People_(s2, r2)));
          auto end = std::chrono::system_clock::now();
    
          timeUsed += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    
        cout << timeUsed << ":\t" << ((float)timeUsed / times) << endl;
      }
      {
        long long timeUsed = 0;
        map<Kid_, People_ > m;
    
        cout << "--------------------------------//(6)" << endl;
        for (int i = 0; i < times; i++) {
          string s1 = getRandomString(10);
          int r1 = std::rand();
          string s2 = getRandomString(10);
          int r2 = std::rand();
    
          auto start = std::chrono::system_clock::now();
          m.emplace(std::piecewise_construct, std::forward_as_tuple(s1, r1), std::forward_as_tuple(s2, r2));
          auto end = std::chrono::system_clock::now();
    
          timeUsed += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    
        cout << timeUsed << ":\t" << ((float)timeUsed / times) << endl;
      }
      {
        long long timeUsed = 0;
        map<Kid_, People_ > m;
    
        cout << "--------------------------------//(8)" << endl;
        for (int i = 0; i < times; i++) {
          string s1 = getRandomString(10);
          int r1 = std::rand();
          string s2 = getRandomString(10);
          int r2 = std::rand();
    
          auto start = std::chrono::system_clock::now();
          m[Kid_(s1, r1)] = People_(s2, r2);
          auto end = std::chrono::system_clock::now();
    
          timeUsed += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    
        cout << timeUsed << ":\t" << ((float)timeUsed / times) << endl;
      }
      /
      cout << "--------------------------------//unordered_map" << endl;
    
      {
        long long timeUsed = 0;
        unordered_map<Kid_, People_, KeyHash, KeyEqual> m(3 * times);
    
        cout << "--------------------------------//(1)" << endl;
        for (int i = 0; i < times; i++) {
          string s1 = getRandomString(10);
          int r1 = std::rand();
          string s2 = getRandomString(10);
          int r2 = std::rand();
    
          auto start = std::chrono::system_clock::now();
          Kid_ k(s1, r1);
          m.try_emplace(k, s2, r2);
          auto end = std::chrono::system_clock::now();
    
          timeUsed += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    
        cout << timeUsed << ":\t" << ((float)timeUsed / times) << endl;
      }
      {
        long long timeUsed = 0;
        unordered_map<Kid_, People_, KeyHash, KeyEqual> m(3 * times);
    
        cout << "--------------------------------//(2)" << endl;
        for (int i = 0; i < times; i++) {
          string s1 = getRandomString(10);
          int r1 = std::rand();
          string s2 = getRandomString(10);
          int r2 = std::rand();
    
          auto start = std::chrono::system_clock::now();
          m.try_emplace(Kid_(s1, r1), s2, r2);
          auto end = std::chrono::system_clock::now();
    
          timeUsed += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    
        cout << timeUsed << ":\t" << ((float)timeUsed / times) << endl;
      }
      {
        long long timeUsed = 0;
        unordered_map<Kid_, People_, KeyHash, KeyEqual> m(3 * times);
    
        cout << "--------------------------------//(3)" << endl;
        for (int i = 0; i < times; i++) {
          string s1 = getRandomString(10);
          int r1 = std::rand();
          string s2 = getRandomString(10);
          int r2 = std::rand();
    
          auto start = std::chrono::system_clock::now();
          Kid_ x1(s1, r1);
          People_ p1(s2, r2);
          m.emplace(x1, p1);
          auto end = std::chrono::system_clock::now();
    
          timeUsed += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    
        cout << timeUsed << ":\t" << ((float)timeUsed / times) << endl;
      }
      {
        long long timeUsed = 0;
        unordered_map<Kid_, People_, KeyHash, KeyEqual> m(3 * times);
    
        cout << "--------------------------------//(4)" << endl;
        for (int i = 0; i < times; i++) {
          string s1 = getRandomString(10);
          int r1 = std::rand();
          string s2 = getRandomString(10);
          int r2 = std::rand();
    
          auto start = std::chrono::system_clock::now();
          m.emplace(Kid_(s1, r1), People_(s2, r2));
          auto end = std::chrono::system_clock::now();
    
          timeUsed += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    
        cout << timeUsed << ":\t" << ((float)timeUsed / times) << endl;
      }
      {
        long long timeUsed = 0;
        unordered_map<Kid_, People_, KeyHash, KeyEqual> m(3 * times);
    
        cout << "--------------------------------//(5)" << endl;
        for (int i = 0; i < times; i++) {
          string s1 = getRandomString(10);
          int r1 = std::rand();
          string s2 = getRandomString(10);
          int r2 = std::rand();
    
          auto start = std::chrono::system_clock::now();
          m.emplace(make_pair(Kid_(s1, r1), People_(s2, r2)));
          auto end = std::chrono::system_clock::now();
    
          timeUsed += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    
        cout << timeUsed << ":\t" << ((float)timeUsed / times) << endl;
      }
      {
        long long timeUsed = 0;
        unordered_map<Kid_, People_, KeyHash, KeyEqual> m(3 * times);
    
        cout << "--------------------------------//(6)" << endl;
        for (int i = 0; i < times; i++) {
          string s1 = getRandomString(10);
          int r1 = std::rand();
          string s2 = getRandomString(10);
          int r2 = std::rand();
    
          auto start = std::chrono::system_clock::now();
          m.emplace(std::piecewise_construct, std::forward_as_tuple(s1, r1), std::forward_as_tuple(s2, r2));
          auto end = std::chrono::system_clock::now();
    
          timeUsed += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
    
        cout << timeUsed << ":\t" << ((float)timeUsed / times) << endl;
      }
      {
        long long timeUsed = 0;
        unordered_map<Kid_, People_, KeyHash, KeyEqual> m(3 * times);
    
        cout << "--------------------------------//(8)" << endl;
        for (int i = 0; i < times; i++) {
          string s1 = getRandomString(10);
          int r1 = std::rand();
          string s2 = getRandomString(10);
          int r2 = std::rand();
    
          auto start = std::chrono::system_clock::now();
          m[Kid_(s1, r1)] = People_(s2, r2);
          auto end = std::chrono::system_clock::now();
    
          timeUsed += std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        }
        
        cout << timeUsed << ":\t" << ((float)timeUsed / times) << endl;
      }
    }
    
    
    int main() {
       testMapAdd();
    
      return 0;
    }

运行结果：

> \--------------------------------//map  
> \--------------------------------//(1)  
> 934167100:      934.167  
> \--------------------------------//(2)  
> 892646600:      892.647  
> \--------------------------------//(3)  
> 919973300:      919.973  
> \--------------------------------//(4)  
> 917704500:      917.705  
> \--------------------------------//(5)  
> 935676700:      935.677  
> \--------------------------------//(6)  
> 946283500:      946.284  
> \--------------------------------//(8)  
> 939161000:      939.161  
> \--------------------------------//unordered\_map  
> \--------------------------------//(1)  
> 269299400:      269.299  
> \--------------------------------//(2)  
> 278339800:      278.34  
> \--------------------------------//(3)  
> 269483600:      269.484  
> \--------------------------------//(4)  
> 273019500:      273.02  
> \--------------------------------//(5)  
> 274466600:      274.467  
> \--------------------------------//(6)  
> 267864800:      267.865  
> \--------------------------------//(8)  
> 273746400:      273.746

从数值上看，这几种方式的效率相差并不大，而且每次执行的结果的排名都不完全相同。这应该是编译器做了大量的编译优化，所以执行效率都还是不错的。