稲葉 一浩 kinaba@google.com Dec 4, 2015 Post-Kona paper 解説 P0083R1: Splicing Maps and Sets (Rev.3) http://open-std.org/JTC1/SC22/WG21/docs/papers/2015/p0083r1.pdf 稲葉 一浩 kinaba@google.com Dec 4, 2015
std::list には、ある list から別の list に要素を “移す” 機能がある list<int> x = {0,1,2,3,4}; auto xs = std::find(x.begin(), x.end(), 1); auto xe = std::find(x.begin(), x.end(), 4); list<int> y = {10,20,30}; auto yi = std::find(y.begin(), y.end(), 20); y.splice(yi, x, xs, xe); // x == {0, 4} // y == {10, 1,2,3, 20, 30} map や set にも欲しい！ というのが今回の提案
ただし std::list::splice は (連結リストのポインタの付け替えとして実装できるので) O(1) 時間 set, map, unordered_set, ... では無理 コンテナ内部表現のためのメモリの解放や 再割り当ては行わずに、移動できるようにする “ちょっとだけ”効率化するための提案
C++14 での要素の移動 std::set<int> x = {1,2,3}; std::set<int> y; int elem = *x.begin(); x.erase(x.begin()); y.insert(elem); ここで x 内部で 探索木の ノード用メモリ解放 ここで y 内部で 探索木の ノード用メモリ確保 提案 std::set<int> x = {1,2,3}; std::set<int> y; y.insert(x.extract(x.begin())); 内部ノードの所有権を move で x から y へ 移動。
ポイント set<Key, Comp, Allocator> Comp が例外を投げないなら insert/erase も投げない set<MoveOnlyType> から値を取り出せるようになる。 (以前も値を入れることは .emplace でできた)
論点になるかもしれないポイント extract() された set::node_type オブジェクトは、元のコンテナの寿命を超えて生存する extract(const key_type& k) で存在しないキーを指定してもよい （“ノード無し”を表す値を返す） この値の insert は常に失敗 取り出した(移動途中の)値のkeyやvalueは変更可能
template<class Key, class Comp, class Alloc> class set { typedef 未規定 node_type; typedef 未規定 insert_return_type; node_type extract(iterator); node_type extract(const key_type&); insert_return_type insert(node_type&&); insert_return_type insert(iterator, node_type&&); template<class C2> void merge(set<Key,C2,Alloc>& source); template<class C2> void merge(set<Key,C2,Alloc>&& source); };
class node_type { value_type& value(); key_type& key(); mapped_type& mapped(); // mapの場合 explicit operator bool(); bool empty(); }; class insert_return_type { bool inserted; iterator position; node_type node; //挿入できなかった場合ここに戻る };
気になった点 unordered_ コンテナへの移動が nothrow というのは難しいのではないか (他は特になし)