[lv5] ft_containers(6/6) map(erase)
[(5/6) map(insert)にもどる] https://note.com/syamashi/n/n957bb9ca7719
[(7/6) setにすすむ] https://note.com/syamashi/n/n95838c9d5266
1. map eraseが呼び出せるまで
/containers/map.hpp
//// Modifiers
size_type erase(const key_type& key) { return _M_t.erase(key); }erase(key)だけ呼び出せるようにします。
戻り値は、成功したら1。失敗（もともと存在しなかった）は0。
2. _Rb_tree eraseが動くまで
erase(key)はこんな感じ
/utils/rb_tree.hpp
public:
// utility function that deletes the node with given value
size_type erase(const key_type& key) {
if (_S_root() == NULL)
// Tree is empty
return 0;
iterator v = lower_bound(key);
if (v == end() || _M_key_compare(key, _S_key(v))) return 0;
deleteNode(v.get_link());
// headerの更新
if (size()) {
_M_root()->_M_parent = _M_header;
_M_header->_M_left = _S_mostleft();
_M_header->_M_right = _S_mostright();
} else {
_M_root() = NULL;
_M_header->_M_left = _M_header;
_M_header->_M_right = _M_header;
}
return 1;
}Q. headerの更新
A. headerの左右を毎回取り直す実装は、効率度外視の怠慢です。
deleteNodeのアルゴリズム部分は、神サイトを参考に構築します。
https://www.geeksforgeeks.org/red-black-tree-set-3-delete-2/?ref=lbp
これを10回見たほうがいい。
https://www.youtube.com/watch?v=DHDKhWoQcNc
/utils/rb_tree.hpp
// delete
// find node that do not have a left child
// in the subtree of the given node
// 今いる場所から、左の突き当りノード
_Link_type successor(_Link_type x) {
_Link_type temp = x;
while (temp->_M_left != NULL) temp = temp->_M_left;
return temp;
}
// find node that replaces a deleted node in BST
_Link_type BSTreplace(_Link_type x) {
// when node have 2 children
// 子供が2人いるなら、RLLLLL
if (x->_M_left != NULL and x->_M_right != NULL)
return successor(x->_M_right);
// when leaf
if (x->_M_left == NULL and x->_M_right == NULL) return NULL;
// when single child
// 子供が1人なら左から返す。
if (x->_M_left != NULL)
return x->_M_left;
else
return x->_M_right;
}
// deletes the given node
void deleteNode(_Link_type v) {
_Link_type u = BSTreplace(v);
// True when u and v are both black
bool uvBlack =
((u == NULL or u->_M_color == _S_black) and (v->_M_color == _S_black));
_Link_type parent = v->_M_parent;
if (u == NULL) { // vが葉
// u is NULL therefore v is leaf
if (v == _S_root()) {
// v is root, making root null
_M_root() = _M_header;
} else {
if (uvBlack) {
// u and v both black
// v is leaf, fix double black at v
/*
B
/
v:B
*/
fixDoubleBlack(v);
} else {
// v is red
/*
B
/ \
v:R (R)
*/
if (v->sibling() != NULL)
// sibling is not null, make it red"
v->sibling()->_M_color = _S_red;
}
// delete v from the tree
if (v->isOnLeft()) {
parent->_M_left = NULL;
} else {
parent->_M_right = NULL;
}
}
_M_put_node(v);
return;
}
if (v->_M_left == NULL or v->_M_right == NULL) {
// v has 1 child
if (v == _S_root()) {
// v is root, assign the value of u to v, and delete u
/*
v
/
u
u
/ \
NU NU
*/
_M_root() = u;
v->swapNode(u);
u->_M_left = u->_M_right = NULL;
_M_put_node(v);
} else {
// Detach v from tree and move u up
/*
B
/
v:R
/
u:(B)
*/
if (v->isOnLeft()) {
parent->_M_left = u;
} else {
parent->_M_right = u;
}
_M_put_node(v);
u->_M_parent = parent;
if (uvBlack) {
// u and v both black, fix double black at u
fixDoubleBlack(u);
} else {
// u or v red, color u black
u->_M_color = _S_black;
}
}
return;
}
// v has 2 children, swap values with successor and recurse
/*
before del(B10)
B10:v
/ \
R7 R22
/ \ / \
B6 B8 B13:u B26
/
R2
after
B13
/ \
R7 B22
/ \ \
B6 B8 R26
/
R2
*/
if (v == _S_root()) _M_root() = u;
v->swapNode(u);
deleteNode(v);
}
void fixDoubleBlack(_Link_type x) {
if (x == _S_root())
// Reached root
return;
_Link_type sibling = x->sibling();
_Link_type parent = x->_M_parent;
if (sibling == NULL) {
// No sibiling, double black pushed up
fixDoubleBlack(parent);
} else {
if (sibling->_M_color == _S_red) {
// Sibling red
/*
before
B
/ \
x:B R
after
(R)
/ \
x:B (B)
*/
parent->_M_color = _S_red;
sibling->_M_color = _S_black;
if (sibling->isOnLeft()) {
// left case
rightRotate(parent);
} else {
// right case
/*
(B)
/
(R)
/
x:B
*/
leftRotate(parent); // 右が持ち上がる
}
fixDoubleBlack(x);
} else {
// Sibling black
if (sibling->hasRedChild()) {
// 赤い子供がいるならおしまい
// vを削除しても、どの葉からも黒ノードが同じ数になる。
// at least 1 red children
if (sibling->_M_left != NULL and
sibling->_M_left->_M_color == _S_red) { // 左が赤
if (sibling->isOnLeft()) {
// left left
sibling->_M_left->_M_color = sibling->_M_color;
sibling->_M_color = parent->_M_color;
rightRotate(parent);
} else {
// right left
sibling->_M_left->_M_color = parent->_M_color;
rightRotate(sibling);
leftRotate(parent);
}
} else { // 右が赤
if (sibling->isOnLeft()) {
// left right
/*
before
R
/ \
x:B B
/ /
R R
xをdelすると、x下の葉がB0, それ以外がB1になってしまう
changeColor
R
/ \
x:B (R)
/
(B)
leftRotate
(R)
/ \
R B
/
x:B
changeColor
(R)
/ \
parent:(B) B
/
x:B
// xを除いた場合どの葉もB1になった。
*/
sibling->_M_right->_M_color = parent->_M_color;
leftRotate(sibling);
rightRotate(parent);
} else {
// right right
sibling->_M_right->_M_color = sibling->_M_color;
sibling->_M_color = parent->_M_color;
leftRotate(parent);
}
}
parent->_M_color = _S_black;
} else {
// 2 black children
/*
R
/ \
x:B B
/ \
B B
xがなくなるとx側がB1に。右側がB2になってしまう
(B)
/ \
x:B (R)
/ \
B B
*/
sibling->_M_color = _S_red;
if (parent->_M_color ==
_S_black) // parent以下全体の黒が1個減ってしまうので、さらにparentで調整
fixDoubleBlack(parent);
else
parent->_M_color = _S_black;
}
}
}
}・swapNode
/utils/rb_tree.hpp
// _Rb_tree_node
void swapNode(_Link_type& x) {
// xのまわり
_Link_type xp = x->_M_parent;
_Link_type xr = x->_M_right;
_Link_type xl = x->_M_left;
_Link_type tp = _M_parent;
_Link_type tr = _M_right;
_Link_type tl = _M_left;
if (xp->_M_left == x)
xp->_M_left = this;
else if (xp->_M_right == x)
xp->_M_right = this;
if (xl) xl->_M_parent = this;
if (xr) xr->_M_parent = this;
// 自分のまわり
if (isOnLeft())
tp->_M_left = x;
else
tp->_M_right = x;
if (tl) tl->_M_parent = x;
if (tr) tr->_M_parent = x;
std::swap(_M_color, x->_M_color);
std::swap(_M_parent, x->_M_parent);
std::swap(_M_right, x->_M_right);
std::swap(_M_left, x->_M_left);
}
};Q. swapNode？なんで？
A. 神サイトだと、swapvalue()箇所。
本当は*M_value_type だけ交換したいですが、期待通りのeraseができなくなりました。絶対動くはずだと思うんですが。
どうにも解消しないので、逆転の発想で、valueを動かさずNodeを全部取り換える実装にしています。
処理数が増えて、かなり怠慢です。
*M_value_typeはポインタなのでswapできると思います。
_M_value_typeの第一引数がconstなので、ポインタの中身はswapできません。
Q. eraseのアルゴリズム
https://www.youtube.com/watch?v=DHDKhWoQcNc
A. ざっくりと
1. 赤を消すほうが楽。
2. 消した後、親戚との関係が「黒黒」になってたら回転対象
3. 黒を消すと「どの葉からも、根までに通る黒の個数が一緒」ルールに合わせるため、全体を組み替える。
4. 改善するための回転方法が3パターンある。
必要なmap実装のアイテムがそろいました。後はスムーズに実装できます。コメントできる関数のみ補足しておきます。
3. map その他関数実装
cppreference
https://en.cppreference.com/w/cpp/container/map
Member functions
・constructer
・destructer
・operator=
/utils/rb_tree.hpp
_Rb_tree& operator=(const _Rb_tree& src) {
if (this == &src) return *this;
_M_erase(_S_root());
// headerは上書き再利用
_M_reset();
_M_key_compare = src._M_key_compare;
_M_node_alloc = src._M_node_alloc;
// root以下クローン
if (src._M_node_count) {
_M_root() = _M_copy(src._M_header->_M_parent, _M_header);
_M_header->_M_left = _S_mostleft();
_M_header->_M_right = _S_mostright();
}
return *this;
}Q. _M_copy()
A. root以下の要素をまるまるコピーするヘルパーです。
_M_copy(_Const_Link_type x, _Link_type p); // {origin, parent}
head
|
3:root
/ \
1 5
/ \ / \
0 2 4 7
/ \
6 8
\
9
1(x:3 p:header)
2(x:5 p:3)
3(x:7 p:5)
4(x:8 p:7)
5(x:9 p:8)
6(x:2 p:1) // 3->leftの再帰処理する順序は、
1. rootから探索。
2. 右にすすめるなら右に進んでいく。
3. 左に進めるなら1個左に進んで、2.の処理。
/utils/rb_tree.hpp
_Link_type _M_copy(_Const_Link_type x, _Link_type p) { // {origin, parent}
_Link_type top = _M_clone_node(x);
top->_M_parent = p;
try {
if (x->_M_right) top->_M_right = _M_copy(x->_M_right, top);
p = top;
x = x->_M_left; // 左に進んで次の探索
while (x != 0) {
_Link_type y = _M_clone_node(x);
p->_M_left = y;
y->_M_parent = p;
if (x->_M_right) y->_M_right = _M_copy(x->_M_right, y);
p = y;
x = x->_M_left;
}
} catch (...) {
_M_erase(top);
throw; // throw_exception_again;
}
return top;
}・get_allocator
Element access
・at
/containers/map.hpp
mapped_type& at(const key_type& k) {
iterator i = lower_bound(k);
if (i == end() || key_comp()(k, (*i).first))
std::__throw_out_of_range("map::at");
return (*i).second;
}Q. std::__throw_out_of_range
A. atは例外を投げます。operator[]は投げません。
・operator[]
/containers/map.hpp
mapped_type& operator[](const key_type& k) {
iterator i = insert(value_type(k, mapped_type())).first;
return i->second;
}Q. insert
A. mapの忘れがちで、とても大事な仕様です。
M[1]が存在していない状態で、(M.count(1) == 0のとき)
M[1];
を参照すると、
M[1] = 0;
が自動生成されます。
_M_node_countも+1されます。
Iterators
・begin / end / rbegin / rend
Capacity
・empty
・size
・max_size
max_sizeですが、定義通りに作っても環境差異が出ます。
定義パターン1
std::numeric_limits<size_type>::max() / sizeof(value_type);
定義パターン2
alloc.max_size() をかえす
実装パターン3(これを採用)
ワカモレにベタ合わせ。
参考値
わかもれstd::max_size
vector<char> : max() / 2
vector<int> : max() / 4
map<int,int> : max() / 40
map<int,char> : max() / 40
map<char,int> : max() / 40
map<char,char>: max() / 32
set<int> : max() / 32
set<char> : max() / 32
std::numeric_limits<size_type>::max()/utils/rb_tree.hpp
size_type max_size() const {
size_t div = sizeof(_Link_type) * 4 + sizeof(value_type);
div = (div / 8) * 8;
return std::numeric_limits<size_type>::max() / div ;
// return _M_node_alloc.max_size();
}
Modifiers
・clear
・insert
・erase
・swap
/utils/rb_tree.hpp
void swap(_Rb_tree& __t) {
// どちらかが size==0 の場合、移す or reset()する
if (_M_root() == 0) {
if (__t._M_root() != 0) _M_move_data(__t);
} else if (__t._M_root() == 0)
__t._M_move_data(*this);
else { // どっちも要素がある場合
std::swap(_M_root(), __t._M_root());
std::swap(_M_header->_M_left, __t._M_header->_M_left);
std::swap(_M_header->_M_right, __t._M_header->_M_right);
_M_root()->_M_parent = _M_end();
__t._M_root()->_M_parent = __t._M_end();
std::swap(_M_node_count, __t._M_node_count);
}
// No need to swap header's color as it does not change.
std::swap(_M_key_compare, __t._M_key_compare);
std::swap(_M_node_alloc, __t._M_node_alloc);
}Q. swapするのは、要素全部？
A. いいえ。headerだけです。
Lookup
・count
Q. 戻り値は0/1
A. keyの存在有無だけを返します。よく勘違いしがちですが、valを返すわけじゃないです。
M[1] = 100のとき、
M.count(1) == 1
です。
M.count(1) == 100
ではありません。
・find
・equal_range
ft::pair<iterator, iterator> equal_range(const _Key& __k) {
_Link_type __x = _S_root();
_Link_type __y = _M_end();
while (__x != 0) {
if (_M_key_compare(_S_key(__x), __k))
__x = __x->_M_right;
else if (_M_key_compare(__k, _S_key(__x)))
__y = __x, __x = __x->_M_left;
else { // __x が keyに合致。 __yは__x->_M_parent
_Link_type __xu(__x);
_Link_type __yu(__y);
__y = __x,
__x = __x->_M_left; // __yはkeyに一致。 __xはkeyより小さいかNULL
__xu = __xu->_M_right; // __xuはkeyより大きいかNULL
/*
__x : key->left
__y : keyに一致
__xu : key->right
__yu : keyに一致
_M_lower_bound(__x, __y, __k) :
__x==NULLなら__y
__xのできるだけ右を返す == keyの前
_M_upper_bound(__xu, __yu, __k) :
__xu==NULLなら__yu。
__xuのできるだけ左を返す == keyの次
つまり、
p.first = M.lower_bound(key);
p.second = M.upper_bound(key);
を効率化してるだけ
*/
return ft::pair<iterator, iterator>(_M_lower_bound(__x, __y, __k),
_M_upper_bound(__xu, __yu, __k));
}
}
// 末端まで来た
return ft::pair<iterator, iterator>(iterator(__y), iterator(__y));
}Q. 簡単にいうと
A. これで十分です。
第一引数に、lower_bound(__k)
第二引数に、upper_bound(__k)
を返すだけ。
でも、これはrootから葉までを2 回探索する怠慢。
1 回の探索で返せる実装にしたのが上記。・lower_bound
・upper_bound
Observers
・key_comp
・value_comp
Non-member functions
・map終了時点でセーブ。
テストケース追加してます。
/testfiles/test_map.cpp
/testfiles/main.cpp
/testfiles/tester.hpp
https://github.com/syamashi/ft_container/tree/55ac028b01824f04503c6e821ac2b396cdc0c3a3/newgame
[(7/6) setにすすむ] https://note.com/syamashi/n/n95838c9d5266