C++ STL Container Set and MultiSet
C++ STL Container Set and MultiSet
Set and MultiSet
- based on gnu 2.9
- 底层用红黑树实现(RB Tree)
- 不同点在于使用rb tree::insert_unique/rb tree::insert_equal, 其他相同
Set
Container
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/*
typedef _Key key_type;
typedef _Compare key_compare;
typedef _Compare value_compare;
typedef _Alloc allocator_type;
typedef __gnu_cxx::__alloc_traits<_Key_alloc_type> _Alloc_traits;
/// Iterator-related typedefs.
typedef typename _Alloc_traits::pointer pointer;
typedef typename _Alloc_traits::const_pointer const_pointer;
typedef typename _Alloc_traits::reference reference;
typedef typename _Alloc_traits::const_reference const_reference;
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 103. set::iterator is required to be modifiable,
// but this allows modification of keys.
typedef typename _Rep_type::const_iterator iterator;
typedef typename _Rep_type::const_iterator const_iterator;
typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
typedef typename _Rep_type::size_type size_type;
typedef typename _Rep_type::difference_type difference_type;
*/
template<typename _Key, typename _Compare = std::less<_Key>,
typename _Alloc = std::allocator<_Key> >
class set
{
// value_type就是T
typedef _Key value_type;
// 与map的不同, 从value中提取key的方式不同
// _Identity<value_type>
typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
key_compare, _Key_alloc_type> _Rep_type;
_Rep_type _M_t; // Red-black tree representing set.
// iterator
iterator begin() { return _M_t.begin(); }
iterator end() const { return _M_t.end(); }
reverse_iterator rbegin() { return _M_t.rbegin(); }
reverse_iterator rend() { return _M_t.rend(); }
// size
bool empty() { return _M_t.empty(); }
size_type size() { return _M_t.size(); }
size_type max_size() { return _M_t.max_size(); }
// 插入
// rb tree::insert_unique
std::pair<iterator, bool> insert(const value_type& __x) {
std::pair<typename _Rep_type::iterator, bool> __p = _M_t._M_insert_unique(__x);
return std::pair<iterator, bool>(__p.first, __p.second);
}
iterator insert(const_iterator __position, const value_type& __x) {
return _M_t._M_insert_unique_(__position, __x);
}
// 删除
// rb tree::erase
iterator erase(const_iterator __position) { return _M_t.erase(__position); }
size_type erase(const key_type& __x) { return _M_t.erase(__x); }
// 查找
// rb tree::find
iterator find(const key_type& __x) { return _M_t.find(__x); }
// rb tree::count
size_type count(const key_type& x) const { return t.count(x); }
// rb tree::lower_bound
iterator lower_bound(const key_type& __x) { return _M_t.lower_bound(__x); }
// rb tree::upper_bound
iterator upper_bound(const key_type& __x) { return _M_t.upper_bound(__x); }
}
MultiSet
Container
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*
typedef _Key key_type;
typedef _Key value_type;
typedef _Compare key_compare;
typedef _Compare value_compare;
typedef _Alloc allocator_type;
typedef __gnu_cxx::__alloc_traits<_Key_alloc_type> _Alloc_traits;
typedef typename _Alloc_traits::pointer pointer;
typedef typename _Alloc_traits::const_pointer const_pointer;
typedef typename _Alloc_traits::reference reference;
typedef typename _Alloc_traits::const_reference const_reference;
typedef typename _Rep_type::const_iterator iterator;
typedef typename _Rep_type::const_iterator const_iterator;
typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
typedef typename _Rep_type::size_type size_type;
typedef typename _Rep_type::difference_type difference_type;
*/
template <typename _Key, typename _Compare = std::less<_Key>,
typename _Alloc = std::allocator<_Key> >
class multiset
{
// _Identity<value_type>
typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
key_compare, _Key_alloc_type> _Rep_type;
_Rep_type _M_t;
// iterator
iterator begin() { return _M_t.begin(); }
iterator end() const { return _M_t.end(); }
reverse_iterator rbegin() { return _M_t.rbegin(); }
reverse_iterator rend() { return _M_t.rend(); }
// size
bool empty() { return _M_t.empty(); }
size_type size() { return _M_t.size(); }
size_type max_size() { return _M_t.max_size(); }
// 插入
// rb tree::insert_equal
iterator insert(const value_type& __x) { return _M_t._M_insert_equal(__x); }
// 删除
// rb tree::erase
iterator erase(const_iterator __position) { return _M_t.erase(__position); }
size_type erase(const key_type& __x) { return _M_t.erase(__x); }
// 查找
// rb tree::find
iterator find(const key_type& __x) { return _M_t.find(__x); }
// rb tree::count
size_type count(const key_type& x) const { return t.count(x); }
// rb tree::lower_bound
iterator lower_bound(const key_type& __x) { return _M_t.lower_bound(__x); }
// rb tree::upper_bound
iterator upper_bound(const key_type& __x) { return _M_t.upper_bound(__x); }
}
This post is licensed under CC BY 4.0 by the author.