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

| | 0 Comments| 09:39
Categories:

C++11 應該算是 C++ 改變最大的版本,而針對 C++11 的東西其實 Heresy 已經寫了不少了,但是實際上還是沒有能把想記錄的東西都寫過一遍。

而這一篇呢,則是來寫一下 C++11 新加入的六種容器:


std::array<>

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。


std::forward_list

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 associative containers

再來,則是一系列 unordered 的容器,這些容器都是對應到本來的 setmap 的。

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

#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)。

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

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

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

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

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


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

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

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

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

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

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

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

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

Leave a Reply

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *