Post-Kona paper ** P0083R1: Splicing Maps and Sets

Post-Kona paper 解説
P0083R1: Splicing Maps and Sets (Rev.3)
http://open-std.org/JTC1/SC22/WG21/docs/papers/2015/p0083r1.pdf
稲葉一浩
[email protected]
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);
提案
ここで y 内部で
探索木の
ノード用メモリ確保
ここで x 内部で
探索木の
ノード用メモリ解放
std::set<int> x = {1,2,3};
std::set<int> y;
y.insert(x.extract(x.begin()));
内部ノードの所有権を
move で x から y へ
移動。
ポイント
• set<Key, Comp, Allocator>
– Allocator が違うコンテナ間は移動できない
– Comp が違っていてもよい
• 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
node_type
extract(iterator);
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 と
いうのは難しいのではないか
• (他は特になし)

Download Report