C++11 開始的一些標準容器的新功能

以前在使用 iterator 的時候，大多是直接使用 ++iter 這樣的形式，但是總覺得很多時候會把它和其他整數混淆。

而在 C++11 也在 <iterator> 加入了 next()（文件）和 prev()（文件）這兩個函式，可以針對 iterator 做位置的計算。下面就是簡單的範例：

#include <iostream>
#include <array>
#include <iterator>
 
int main()
{
  std::array aData = { 1,2,3,4,5 };
 
  auto it = std::next(aData.begin());
  std::cout << *it << "\n";
 
  it = std::next(it, 3);
  std::cout << *it << "\n";
 
  it = std::prev(it, 2);
  std::cout << *it << "\n";
}

其實要說的話，之前也就有 advance() 這個函式（文件）可以用啦～但是老實說，那個命名 Heresy 始終無法把他和 iterator 做聯想…

這個真的是 Heresy 以前碰過的問題了。

vector 在要用來儲存不確定數量的資料的時候，算是相當地方便；他會自己去配置需要的記憶體空間來做儲存，同時也會保有資料在記憶體上的連續性。

而實際上，vector 會先去配置一塊比較大的記憶體空間、作為他的容量（capacity），而當真的放資料進去的時候，則是會去記錄目前的資料量（size）；如果資料量超過容量的時候，則是會自動去重新跟系統要一塊更大的容量，然後把資料都搬到新的記憶體空間去（稱為 reallocation）。

所以如果再要插入大量資料的時候，其實一個能提高效能的方法，就是先透過 reserve() 這個函式（文件）、要求 vector 先去配置一塊夠大的記憶體來做之後的操作；這樣就可以避免之後的重新配置、記憶體複製了。

但是，相對的問題是，以前的 vector 只能增加容量、卻沒有減少容量的方法！即便是你刪除了 vector 裡的 一堆資料、又或者把整個 vector 都清空了，他的大小會變小沒錯，但是實際上佔用的記憶體空間（容量）卻不會變。

也就是說，直到這個 vector 的生命週期結束前，都難以真的去釋放掉他所占用的記憶體；而如果這個 vector 曾經放過很大量的資料的話，那將會是一個很麻煩的問題。

而到了 C++11，STL 也才終於幫他加入了 shrink_to_fit() 這個函式，可以將 vector 的容量縮減到和大小一樣了。

下面就是一個簡單的示意：

#include <iostream>
#include <vector>
 
int main()
{
  std::vector<size_t> v;
  v.reserve(50);
  std::cout << v.size() << "/" << v.capacity() << std::endl; //0/50
 
  for(size_t i = 0 ; i < 100; ++i)
    v.push_back(i);
  std::cout << v.size() << "/" << v.capacity() << std::endl; //100/112
 
  v.clear();
  std::cout << v.size() << "/" << v.capacity() << std::endl; //0/112
 
  v.reserve(50);
  std::cout << v.size() << "/" << v.capacity() << std::endl; //0/112
 
  v.shrink_to_fit();
  std::cout << v.size() << "/" << v.capacity() << std::endl; //0/0
}

當然啦，以前不是完全沒有辦法可以做到強制釋放記憶體啦。基本上只要重新產生一個新的 vector 物件取代本來的就好了…感覺就是很蠢的方法。

STL 的容器其實本來大多就都已經有 erase() 這個函式，可以透過指定 iterator 的方法來刪除容器裡的特定元素了。

但是當要大量刪除符合條件的元素的時候，其實會相當麻煩…比如說，想要把一個 vector 裡面的奇數都刪除的話，大概得寫成下面的樣子：

for (auto it = v.begin(); it != v.end(); ) {
  if (*it % 2)
    it = v.erase(it);
  else
    ++it;
}

老實說，非常地不直覺…（不過認真說，針對 vector 做這種操作效率也不好就是了 ）

而在 C++20，則是引進了不是 member function、比較好用的 erase() 和 erase_if() 了。

如果只是要刪除特定的值的話，可以直接透過下面這樣的寫法：

std::erase(v, 2);

這樣就可以直接把 v 這個 vector 裡、數值是 2 的元素都刪除了。

而如果是要比較複雜的判斷的話，則也可以透過 erase_if() 來做：

std::erase_if(v, [](const size_t& val) { return val % 2; });

上面的程式碼一樣是用來刪除 vector 裡面的奇數，寫起來比本來透過 iterator 好看多了～

而 erase_if() 也同時有針對 set、map 等其它容器型別的版本可以拿來用，使用方法也都一樣；像下面就是一個 map 的例子：

std::map<int, char> m = { {1, 'a'}, {2, 'b'}, {3, 'c'} };

std::erase_if(m, [](const auto& v) {
  auto [key, val] = v;
  return val == 'b';
});

這樣就可以把 m 這個 map 裡面，值是 ‘b’ 的項目刪除了。

以往要確認 set 或 map 裡面有沒有自己要的資料的時候，往往是得透過檢查 find() 的結果是否是 end() 來做確認，個人始終是覺得不是很直覺。

而在 C++20，這邊終於加入了 contains() 這個更直覺的函式，可以用來確認有沒有需要的值了！

下面就是一段示意的程式：

#include <iostream>
#include <set>
 
int main()
{
  std::set<int> sData = { 1, 2, 3, 4, 5 };
  
  if (sData.find(4) != sData.end())
    std::cout << "Found" << std::endl;
  else
    std::cout << "Not Found" << std::endl;
 
  if (sData.contains(4))
    std::cout << "Found" << std::endl;
  else
    std::cout << "Not Found" << std::endl;
}

個人覺得，這點不但算是語法上簡化，重點是看起來也更直觀了。

extract()
和 merge() 這兩個新的函式基本上也是為了提高效率而在
C++17 新增的。

extract()（map 版、set 版）的功能主要是將一個元素從容器中抽出來成為 node handle 的形式（型別頗複雜的 template type），之後可以用來插入到其他的容器中。

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

std::set<int> sData1 = { 1,2,3 };
std::set<int> sData2 = { 4,5,6 };
auto tmp = sData1.extract(1);
sData2.insert(std::move(tmp));

在上面的範例中，會把 sData1 中的 1 抽出來、然後放到 sData2 裡面；而使用 extract() 的好處則是這邊的 tmp 這個 node handle 在處理的時候基本上不會有物件複製的狀況產生，所以當 set / map 內的型別較為複雜的時候，是可以有效透過避免資料的複製來增加效能的。

而在 merge() 的部分也是類似的狀況；他可以在沒有無謂的資料複製的情況下，將一個容器中的物件轉移到另一個物件。下面就是一個簡單的例子：

std::set<int> sData1 = { 1,2,3 };
std::set<int> sData2 = { 4,5,6 };
sData2.merge(sData1);

在執行完成後，sData1 會是空的，而 sData2 則會有 6 個數字，而在 merge() 的過程中都不會有實際上的資料複製。

相較於本來就有的 std::merge()（文件）是將兩個容器的內容都複製一份到新的容器中，基本上是完全不同的用法的。

另外，要注意的是在呼叫 merge() 的時候，如果兩邊的資料有重複的話，重複的資料是不會被轉移到 sData2 的。