高效使用C++ Map容器，充分利用內存

一、Map容器簡介

C++中的Map容器是一種關聯式容器，它將 key-value 映射對存儲在內部樹結構中，允許通過鍵訪問元素，而鍵可以是任意可比較類型。使用Map容器可以輕鬆實現一些搜索、排序、計數等功能，也可以快速實現字典/哈希表的功能。Map的底層實現是紅黑樹，所以其時間複雜度一般為log(n)。

下面是一個簡單的使用Map容器的示例：

#include <iostream>
#include <map>

using namespace std;

int main() {
  // 聲明並初始化一個Map容器
  map<string, int> myMap = {{"apple", 1}, {"orange", 2}, {"banana", 3}};

  // 輸出Map容器中所有映射對
  for (auto it = myMap.begin(); it != myMap.end(); ++it) {
    cout << it->first << " -> " << it->second << endl;
  }

  // 查找並輸出Map容器中指定鍵對應的值
  string key = "apple";
  cout << "The value of " << key << " is: " << myMap[key] << endl;

  return 0;
}

二、提高Map容器的性能

1. 使用emplace()代替insert()

在向Map容器中插入新的元素時，通常會使用insert()函數實現。但是，如果使用insert()函數插入新的元素，就意味着需要先構造一個pair對象，再將其作為參數傳入insert()函數中，這樣會造成額外的開銷。而emplace()函數就是為了解決這個問題而設計的。使用emplace()函數插入新元素時，就可以直接向emplace()函數中傳入對應的鍵和值，實現更加高效的插入操作。

下面是一個使用emplace()函數的示例：

#include <iostream>
#include <map>

using namespace std;

int main() {
  // 聲明並初始化一個Map容器
  map<string, int> myMap = {{"apple", 1}, {"orange", 2}, {"banana", 3}};

  // 使用emplace()函數插入一個新元素
  myMap.emplace("peach", 4);

  // 輸出Map容器中所有映射對
  for (auto it = myMap.begin(); it != myMap.end(); ++it) {
    cout << it->first << " -> " << it->second << endl;
  }

  return 0;
}

2. 使用lower_bound()和upper_bound()代替find()

在Map容器中查找指定鍵值對應的值時，通常使用find()函數實現。但是，由於Map容器中元素是有序的，所以可以使用lower_bound()和upper_bound()函數代替find()函數，從而實現更高效的查找操作。

lower_bound()函數可以查找第一個大於等於指定鍵值的元素的迭代器，而upper_bound()函數則可以查找第一個大於指定鍵值的元素的迭代器。通過這兩個函數的結合使用，就可以快速的實現在Map容器中查找指定鍵值的操作。

下面是一個使用lower_bound()和upper_bound()函數的示例：

#include <iostream>
#include <map>

using namespace std;

int main() {
  // 聲明並初始化一個Map容器
  map<string, int> myMap = {{"apple", 1}, {"orange", 2}, {"banana", 3}};

  // 使用lower_bound()函數查找第一個大於等於指定鍵值的元素
  auto it_lower = myMap.lower_bound("mango");

  // 使用upper_bound()函數查找第一個大於指定鍵值的元素
  auto it_upper = myMap.upper_bound("mango");

  // 輸出查找到的元素的迭代器
  cout << "The lower bound is: " << it_lower->first << " -> " << it_lower->second << endl;
  cout << "The upper bound is: " << it_upper->first << " -> " << it_upper->second << endl;

  return 0;
}

3. 避免頻繁的插入和刪除操作

Map容器的底層實現是紅黑樹，其插入和刪除操作需要重新構建樹結構，開銷比較大。在實際使用中，應該盡量減少頻繁的插入和刪除操作，以提高Map容器的性能。

下面是一個插入元素較多、刪除元素較多的示例程序，可以看到其性能比較低：

#include <iostream>
#include <map>
#include <ctime>

using namespace std;

int main() {
  map<int, int> myMap;

  time_t start = time(nullptr);

  // 插入1~1000000個元素
  for (int i = 1; i <= 1000000; ++i) {
    myMap[i] = i;
  }

  cout << "Time elapsed for inserting 1000000 elements: " << time(nullptr) - start << endl;

  start = time(nullptr);

  // 刪除1~1000000個元素
  for (int i = 1; i <= 1000000; ++i) {
    myMap.erase(i);
  }

  cout << "Time elapsed for erasing 1000000 elements: " << time(nullptr) - start << endl;

  return 0;
}

三、內存管理

Map容器是一種佔用內存較大的容器，尤其是在元素數量較大、目標機是否足夠內存的情況下，需要高效利用內存。

1. 定製Map容器的比較函數

Map容器的鍵類型必須支持比較操作，否則會出現編譯錯誤。如果Map容器的鍵類型是自定義類型，可以通過定製比較函數的方式，實現對Map容器的排序或者改變Map容器元素的比較方式，從而達到優化內存使用的效果。

下面是一個定義自定義類型的Map容器，並定製比較函數的示例：

#include <iostream>
#include <map>

using namespace std;

class MyType {
public:
  int value;

  MyType(int v) : value(v) {}

  bool operator<(const MyType &other) const {
    return this->value < other.value;
  }
};

int main() {
  // 聲明並初始化一個Map容器，使用自定義類型作為鍵類型，並定製比較函數
  map<MyType, int> myMap{{MyType(2), 10}, {MyType(1), 20}, {MyType(3), 30}};

  // 輸出Map容器中所有映射對
  for (auto it = myMap.begin(); it != myMap.end(); ++it) {
    cout << it->first.value << " -> " << it->second << endl;
  }

  return 0;
}

2. 禁止Map容器的自動擴容

通過控制Map容器的默認擴容策略，可以有效地控制Map容器的內存使用。

Map容器默認的擴容策略是定期擴容，在容器元素數量增加到一定程度時，會自動對容器進行擴容，以增大容器的容量。這種自動擴容的策略會導致容器的內存佔用一直處於相對較高的狀態，對於內存資源寶貴的場景來說，可能會造成浪費。所以，在某些場景下，可以通過禁止Map容器的自動擴容來控制內存的使用。

下面是一個禁止Map容器自動擴容的示例程序：

#include <iostream>
#include <map>

using namespace std;

int main() {
  // 聲明並初始化一個Map容器，同時禁止該Map容器的自動擴容
  map<int, int> myMap;
  myMap.max_load_factor(1.0);

  // 清空Map容器，保證容器內沒有元素
  myMap.clear();

  // 插入1~1000000個元素
  for (int i = 1; i <= 1000000; ++i) {
    myMap[i] = i;
  }

  return 0;
}

3. 合併Map容器

在某些場景下，可能需要將多個Map容器合併成一個Map容器，這時可以使用Map容器的合併函數——merge()，將多個Map容器中的元素合併到一個Map容器中，從而減少內存的使用，避免多個Map容器的重複存儲。

下面是一個合併Map容器的示例程序：

#include <iostream>
#include <map>

using namespace std;

int main() {
  // 聲明並初始化兩個Map容器
  map<int, int> myMap1 = {{1, 10}, {2, 20}, {3, 30}};
  map<int, int> myMap2 = {{4, 40}, {5, 50}, {6, 60}};

  // 使用merge()函數合併兩個Map容器
  myMap1.merge(myMap2);

  // 輸出合併後的Map容器中所有映射對
  for (auto it = myMap1.begin(); it != myMap1.end(); ++it) {
    cout << it->first << " -> " << it->second << endl;
  }

  return 0;
}