关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高
set
排序+去重
find找不到会返回end
lower_bound(val) 返回大于或者等于val的位置
upper_bound(val) 返回大于val的位置
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
| int a[] = { 3,1, 2, 1, 6, 3, 8,3, 5,3};
multiset<int> s(a, a + sizeof(a) / sizeof(int));
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
cout << s.count(1) << endl;
auto pos = s.find(3);
while (pos != s.end())
{
cout << *pos << " ";
++pos;
}
cout << endl;
s.erase(3);
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
pos = s.find(1);
if (pos != s.end())
{
s.erase(pos);
}
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
|
map
重载的方括号
- map中有这个key，返回value的引用。（查找、修改value）
- map中没有这个key，会插入一个pair(key,V())，返回value的引用。（插入+修改）
具体点：
- key在map中，返回pair(key_iterator, false) 这个pair是insert返回的
- key不在map中，返回pair(new_key_iterator, true)
实现
1
2
3
4
5
| V& operator[](const K& key)
{
pair<iterator,bool>ret=insert(make_pair(key, V()));
return (ret.first)->second;
}
|
map和set封装
迭代器（红黑树）
迭代器的begin是中序的第一个节点，也就是最左节点，这里将end设置为空，封装重点是++和–的逻辑
重载++
- 右子树不为空，++就是找右子树中序第一个（最左节点）
- 右子树为空，++找孩子不是父亲右的那个祖先
重载–
- 左子树不为空，–就是找左子树的最右节点
- 左子树为空，–找孩子不是父亲左的那个祖先
代码
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| template <class T, class Ref, class Ptr>
struct __RBTreeIterator
{
typedef RBTreeNode<T> Node;
Node *_node;
typedef __RBTreeIterator<T, Ref, Ptr> self;
__RBTreeIterator(Node *node) : _node(node)
{
}
T &operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
self &operator++()
{
if (_node->_right)
{
Node *left = _node->_right;
while (left->_left)
{
left = left->_left;
}
_node = left;
}
else
{
Node *parent = _node->_parent;
Node *cur = _node;
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
self &operator--()
{
if (_node->_left)
{
Node *right = _node->_left;
while (right->_right)
{
right = right->_right;
}
_node = right;
}
else
{
Node *parent = _node->_parent;
Node *cur = _node;
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
bool operator!=(const self &s) const
{
return _node != s._node;
}
bool operator==(const self &s) const
{
return _node == s._node;
}
};
|
map封装
map的红黑树 RBTree<K, pair<K, V>, MapKeyOfT>，第一个模板参数是key，第二个模板参数是pair
代码
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
| template <class K, class V>
class map
{
struct MapKeyOfT
{
const K &operator()(const pair<K, V> &kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
pair<iterator, bool> insert(const pair<K, V> &kv)
{
return _t.insert(kv);
}
V &operator[](const K &key)
{
return _t.insert(make_pair(key, V())).first->second;
}
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
|
set封装
set的红黑树 RBTree<K, K, SetKeyOfT>，第一个模板参数是key，第二个模板参数是pair
代码
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
| template <class K>
class set
{
struct SetKeyOfT
{
const K &operator()(const K &key)
{
return key;
}
};
public:
typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
pair<iterator, bool> insert(const K &k)
{
return _t.insert(k);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
|
微信
支付宝
