C++11 新的容器：array、沒排序的 set 與 map

array（文件）算是用來取代傳統 C 的陣列用的，他必須要在編譯階段就決定好大小，事後也不能修改；而它的好處，則是有 STL 容器形式包含 iterator 在內大部分的介面，能更好地和 STL 其他功能整合（傳統陣列也可以用 C++20 的 span 來處理就是）。

下面就是一個簡單的例子：

#include <array>
#include <algorithm>
#include <iostream>
 
int main()
{
  std::array<int, 3> aData = { 3,2,1 };
 
  for (size_t i = 0; i < aData.size(); ++i)
    std::cout << aData[i] << "\n";
 
  std::sort(aData.begin(), aData.end());
  for (const auto& v : aData)
    std::cout << v << "\n";
}

這邊的 aData 就類似以前的 int aData[3] 這樣的寫法，也一樣可以透過 [] 來存取值，但是相較之下能更好地對應 STL 的演算法，同時也因為本身就可以透過 size() 取得大小，會更方便使用。

另外，從 C++17 開始，也可以省略 template 引數，讓邊義器自己去判斷（文件）；也就是可以寫成下面的形式：

std::array aData = { 3,2,1 };

這樣寫起來會更簡單一點。

最後，可能會要注意的，是 array 基本上是使用 stack，所以大小應該會有限制；太大的話會造成 stack overflow。

forward_list（文件）基本上就是本來 list 的單向版本（singly-linked list）。

他採用非連續的記憶體配置，並且依序連結，所以可以比 vector 更快速地將新的元素插入在任何位置、或把任何位置的元素移除；但是相對地，他並沒有隨機存取的能力，要讀取中間的值會需要從頭開始找。

由於他是單向的版本，所以基本上只能從頭往後找，不能反向回來，在介面上也只有 begin() 而沒有 rbegin() 可以用。

另外，似乎是為了效能，forward_list 並沒有提供 size() 的函式，所以如果要知道一個 forward_list 有多大，基本上需要透過 begin() 和 end() 來計算，下面是個簡單的寫法：

#include <iostream>
#include <forward_list>
 
int main()
{
  std::forward_list<int> aData = {1,2,3};
  std::cout << "size: " << std::distance(aData.begin(), aData.end()) << "\n";
}

再來，則是一系列 unordered 的容器，這些容器都是對應到本來的 set、map 的。

原始版本的 set 和 map 在修改資料的時候，實際上在內部都是會進行排序來加快之後的存取的，像下面就是一個例子：

#include <iostream>
#include <map>
 
int main()
{
  std::map<int, int> m;
  m[1] = 3;
  m[3] = 1;
  m[2] = 2;
 
  for (auto [key, val] : m)
    std::cout << key << " : " << val << "\n";
  
  // 1 : 3
  // 2 : 2
  // 3 : 1
}

這邊不管資料建立的順序，在最後依序去存取 m 這個 map 的時候，出來的結果都會按照 key 的順序（不過應該是不保證是哪個方向）；而實務上，一般來說 map 會是透過「紅黑樹」（維基百科）來實作的，搜尋的複雜度是 O(log n)。

相較於內部是排序過的 map，unordered_map 顧名思義，就是內部沒有排序過的版本。

他基本上會是透過 Hash Table 來實作，存取的時候是直接去查表，理論上會提供更好的隨機存取效能（平均 O(1)、最壞 O(n)），但是相對地會使用更多的記憶體。

在《Ordered map vs. Unordered map – A Performance Study》這篇，就有針對 map 和 unordered_map 做效能上的比較，在他的測試結果，不管是加入資料、或是查詢資料，unordered_map 的效能都是比 map 好的。

尤其是當資料多的時候，map 插入單一資料的成本明顯會隨著資料量的增加而變多；但是 unordered_map 的插入成本則大致上會是固定值、與資料量無關。

所以理論上，如果在不需要管他有沒有排序過、而效能很重要的狀況，或許把本來 map 這類的容器改成 unordered_map 會比較好。

但是 Heresy 自己的測試狀況，則是發現 unordered_map 也不一定會比較快，應該還是得看資料的狀況來判斷。

Heresy 這邊的測試的方法，是產生一堆亂數作為 key（有重複不管），然後都塞進  map 和 unordered_map 裡、計算需要的時間；同時，也產生另一組亂數、然後依序查找看看裡面有沒有包含這個數值、並計算時間。完整的測試程式可以參考這邊。

下面是在 Visual Studio 2022 17.2.2 下的測試。這邊測試是用數量不同的資料丟到 map 和 unordered_map，計算建立的時候需要的時間：

這邊 unordered_map 在插入資料所需要的時間，大致上都是 map 的一半、甚至更少。

而查詢的速度呢？在固定 100 萬組資料的情況下，不同查詢次數的時間如下：

基本上，這邊的差距就更大了。到了最後所需要的時候，需要的時間大概只有 1/3。

不過，Heresy 在測試的時候，某些數字的組合，卻有可能會出現 unordered_map 比 map 還慢的狀況？這點就不知道什麼回事了。
純以理論上來說，由於 unordered_map 最糟會是 O(n)，確實是有可能會比 map 的 O(log n) 來的慢就是了。

而實際上，這邊的測試…由於實際上應該很少會塞這麼多資料、又查這麼多次，個人是覺得意義應該有限就是了。老實說，在一般狀況下，個人覺得很有可能不會有明顯的效能變化吧？所以真正要用的話，可能還是得根據自己的使用情境，來做測試、評估了。