連想コンテナ間で、コピー、ムーブなしに要素を移動させる方法

初めに

C++17から、連想コンテナ(setやmapです。unorderd,multiも含みます)で、コピーもムーブも行わずに、要素の所有権を転送することができるようになりました。(この種の操作は「スプライシング」と呼ばれます。)

どうやっているのか

連想コンテナはノードベースです。そこで、ノードを所有することができる「ノードハンドル」というものが追加され、これを用いることで、要素のコピーやムーブを行わずにコンテナ間で要素を転送することができるようになりました。ノードハンドルは、各連想コンテナのextract()という名前のメンバ関数から取得できます。また、2つの互換性のあるコンテナをコピー、ムーブなしに結合するための、merge()という名前のメンバ関数も追加されました。（互換性は、同じコンテナどうし、multi なものとそうでないものどうしであります。）

ノードハンドルについて

ノードハンドルは、互換性のあるノードを持つ別のコンテナに、その所有権を移すために使用されます。例を次に示します。

#include <iostream>
#include <string>
#include <map>

int main()
{
  std::map<int, std::string> m1 = {
    { 1, "nya" },
    { 2, "nyanya" },
    { 3, "nyau" }
  };

  std::map<int, std::string> m2;

  // ノードを取得 (要素は、コピーもムーブもされません)
  // node_type は node-handle の特殊化です
  std::map<int, std::string>::node_type node = m1.extract(m1.begin());

  // m2 へ挿入(要素は、コピーもムーブもされません)
  m2.insert(std::move(node));
}

また、ノードハンドルに格納されている要素にアクセスするためのメンバ関数は、setコンテナとmapコンテナで違います。setコンテナでは、メンバ関数value()、mapコンテナでは、キーをメンバ関数key()、もう一方の要素をmapped()で取得できます。戻り値はconstでない参照になっており、値を書き換えることができます。例を次に示します。

#include <iostream>
#include <string>
#include <map>
#include <set>

int main()
{
  // set
  std::set<int> s = { 1, 2, 3 };

  // ノードを取得
  auto node1 = s.extract(2);

  // 値の書き換え
  node1.value() = 4;

  // ノードをもどす
  s.insert(std::move(node1));

  // map
  std::map<int, std::string> m = {
    { 1, "shift" },
    { 2, "ctrl" },
    { 3, "enter" }
  };

  // ノードを取得
  auto node2 = m.extract(2);

  // キーを書き換え
  node2.key() = 4;

  // 値を書き換え
  node2.mapped() = "esc";

  // ノードをもどす
  m.insert(std::move(node2));
}

ノードハンドルでできること+α

ノードハンドルを用いることで、再確保なしにmapのキーを変更したり、setに格納されているムーブオンリーなオブジェクトを取り出すことができるようになりました。

std::mapの例です。

#include <iostream>
#include <map>

int main()
{
  std::map<int, char> m1;
  std::map<int, char> m2 = {
    {10, 'a'},
    {20, 'b'},
    {30, 'c'}
  };

  // ノードを取得
  std::map<int, char>::node_type node = m2.extract(10);

  // 再確保なしにキーを書き換えます
  node.key() = 15;

  // ノードを転送
  m1.insert(std::move(node));
}

std::setの例です。

#include <iostream>
#include <set>

class noncopyable {
protected:
  constexpr noncopyable() noexcept = default;
  ~noncopyable() = default;
  constexpr noncopyable(noncopyable const &) noexcept = delete;
  constexpr noncopyable(noncopyable &&) noexcept = default;
  noncopyable & operator=(noncopyable const &) noexcept = delete;
  noncopyable & operator=(noncopyable &&) noexcept = default;
};

struct my_struct // ムーブオンリーな型
  : noncopyable {
  int value;
  constexpr explicit my_struct(int i) noexcept : value(i) {};
  bool operator < (const my_struct &rhs) const noexcept {return this->value < rhs.value;}
};

int main()
{
  // ムーブオンリーな型をキーとして扱う set
  std::set<my_struct> s;

  // 挿入
  s.insert(my_struct{3});
  s.insert(my_struct{1});
  s.insert(my_struct{4});

  // 要素を取り出す
  my_struct m = std::move(s.extract(s.begin()).value());

  std::cout << m.value;
}

2つの連想コンテナを結合する

メンバ関数 merge() を使います。

#include <iostream>
#include <map>
#include <string>

int main()
{
  std::map<int, std::string> m1 = {
    {1, "nya"},
    {2, "nya?"},
    {3, "nya!"}
  };
  std::map<int, std::string> m2 = {
    {1, "nyanya"}
  };

  // m1 の要素を m2 に merge
  // コピー、ムーブはされません
  // std::map はキーの重複ができないので、
  // m1 の {1, "nya"} は転送されずに残ります
  m2.merge(m1);
}

まとめ

連想コンテナを結合するためには、メンバ関数merge()を使うことができます。
また、互換性のある連想コンテナどうしで要素を転送するためには、メンバ関数extract()が使えます。

例

m2.insert(std::move(m1.extract(m1.begin()))); // 要素はコピー、ムーブされません

また、ノードハンドルはextract()から取得でき、そのノードの要素を変更することができます。