[lv5] ft_containers(7/6) set

syamashi

[(6/6) map(erase)にもどる] https://note.com/syamashi/n/n6f043c7b8ef6

Q. setとは
A. valを持たないmap。keyが昇順sortで格納されます。

mapと比較した特徴3点。
1. Rb_treeを使うのは同じ。
2. Rb_treeのvalue_typeが違う。
map: pair<const key, val>
set: key
3. 関数はほぼ同じ。次の2つがない。
・class value_compare
・operator[] / at

これだけ。ベースをmapに、setを作ります。
/containers/set.hpp

1. /containers/map.hpp をコピー
2. `s/map/set/g`

あとは
2 value_type を keyにする。
3, value_compareと、oprator[]と、atを削除する。
をしていく。

・_KeyOfValue

rb_treeの中で、keyの取得を「value_typeのfirstをとる」と限定的に書いていました。
/utils/rb_tree

 protected:
 key_type _S_key(_Link_type x) const { return x->_M_value_type->first; }

ところが、setで渡されるvalue_typeはpair型ではありません。
そのためコンパイルエラーになります。

value_typeの型によって、keyの戻り値を変更できるようにしたい。
どうしよう？

is_sameを使ってif分岐させましたが、これはコンパイルエラー。

 key_type _S_key(_Link_type x) const {
   if (is_same<_Key, _Val>::value) // set
     return x->_M_value_type;
   else // map
     return x->_M_value_type.first;

mapを実行すると

rb_tree.hpp:435:14: error: no viable conversion from returned value of type 'std::pair<const int, std::__cxx11::basic_string<char> >' to function     
     return type 'ft::_Rb_tree<int, std::pair<const int, std::__cxx11::basic_string<char> >, std::less<int>, std::allocator<std::pair<const int,
     std::__cxx11::basic_string<char> > > >::key_type' (aka 'int')
     return x->_M_value_type;
            ^~~~~~~~~~~~~~~~

処理上はifに入らないけど、ifに入った場合の return の型があってないよ、と言われます。returnの分岐ができないので「特殊化」で実装します。
Q. 特殊化
A. テンプレートを使用する箇所において、 関数テンプレートから関数を生成すること

/utils/util.hpp

//// _KeyOfValue

template <typename _Pair>
struct _Select1st {
 typename _Pair::first_type& operator()(_Pair& __x) const { return __x.first; }

 const typename _Pair::first_type& operator()(const _Pair& __x) const {
   return __x.first;
 }
};

template <typename _Tp>
struct _Identity {
 _Tp& operator()(_Tp& __x) const { return __x; }

 const _Tp& operator()(const _Tp& __x) const { return __x; }
};

// Partial specialization, avoids confusing errors in e.g. std::set<const T>.
template <typename _Tp>
struct _Identity<const _Tp> : _Identity<_Tp> {};

Q. _Select1st
A. ()(pair)を渡すと、第一引数の値を返してくれる関数。mapで使えば、pairからkeyを取得できそう。

 ft::pair<int, int> P;
 P = ft::make_pair<int, int>(10, 20);
 cout << ft::_Select1st<ft::pair<int, int> >()(P) << endl;

>> 10

Q. _Identity
A. ()(key)を渡すと、keyを返します。setはこれを使えばkeyをそのまま取得できそう。​

keyに変換してくれる関数を、_Rb_treeを呼び出すtemplateに加えます。
/containers/map.hpp

 private:
 typedef _Rb_tree<key_type, value_type, ft::_Select1st<value_type>, key_compare,
                  allocator_type>
     _Rep_type;

/containers/set.hpp

 private:
 typedef _Rb_tree<key_type, value_type, ft::_Identity<value_type>, key_compare,
                  allocator_type>
     _Rep_type;

struct rb_treeのtemplateに、要素[_KeyOfValue]を加えます。
/utils/rb_tree.hpp

template <typename _Key, typename _Val, typename _KeyOfValue, typename _Compare,
         typename _Alloc = std::allocator<_Val> >
class _Rb_tree {
 ...

protected:
 key_type _S_key(_Link_type x) const {
   return _KeyOfValue()(*(x->_M_value_type));
 }
 key_type _S_key(_Const_Link_type x) const {
   return _KeyOfValue()(*(x->_M_value_type));
 }
 key_type _S_key(value_type x) const { return _KeyOfValue()(x); }
 key_type _S_key(iterator x) const { return _KeyOfValue()(*x); }
 key_type _S_key(const_iterator x) const { return _KeyOfValue()(*x); }

_S_key()の戻り値について。
_KeyOfValue()を通すことで、mapでもsetでもkeyを返す実装ができました。

・set 実装

cppreferenceに沿って、atとoperator[]を除いて実装。
https://en.cppreference.com/w/cpp/container/set



以上です。おつかれさまでした。



・処理時間の計測

c++11はだめなので、chronoは使えません。
/testfiles/main.cpp

int main() {
 clock_t clockstart, clockend;

 // 開始時間の取得
 clockstart = clock();

 // 処理

 
 // 終了時間の取得
 clockend = clock();
  
 // 処理時間の取得(マイクロ秒だと思う)
 double time = (double)(clockend - clockstart);
 cerr << "totaltime:" << time << endl; // エラー出力にだす。
}

mapの処理時間が本家より20倍以上遅くなければいい。

・最後の記録https://github.com/syamashi/ft_container/tree/bf5f4adbd1ddce3f20110eeb03906d619d2a79fc/newgame

テストケースを追加しました。
/testfiles/test_review.cpp
/testfiles/test_set.cpp
/testfiles/main.cpp
/testfiles/tester.hpp


・おまけ setの処理時間ランキング

[Q] 典型90 027 - Sign Up Requests （★2)
https://atcoder.jp/contests/typical90/tasks/typical90_aa

ft::setのヘッダーをべた書きし、mainを次のコードで提出してみてください。50000Byte以上になるかも。

using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < n; ++i)

int main() {
 ft::set<string> sets;

 ll N;
 cin >> N;
 rep(i, N) {
   string S;
   cin >> S;
   if (sets.count(S)) continue;
   sets.insert(S);
   cout << i + 1 << endl;
 }
}

std::set(243 ms)
https://atcoder.jp/contests/typical90/submissions/28062817

syamashi::set(341 ms)
https://atcoder.jp/contests/typical90/submissions/27979220

tkodai::set(256 ms)
https://atcoder.jp/contests/typical90/submissions/28062764


いいなと思ったら応援しよう！