set所有元素都会根据元素的值被自动排序，不允许有两个相同的键值。
由于RB-tree是一种平衡二叉树，自动排序效果很不错，所以标准的stl以BR-tree做为底层实现机制。
#include
#include
using namespace std;
int main(){
set s={2,3,1,4};
set::iterator sit=s.begin();
for(;sit!=s.end();++sit){ // 输出1 2 3 4
cout<<*sit<<" ";
}
return 0;
} 特别的，stl还提供了一组set/multiset相关算法，包括交集、并集、差集、对称差集等。
template
class set {
// requirements:
__STL_CLASS_REQUIRES(_Key, _Assignable);
__STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Key, _Key);
public:
// 类型
typedef _Key key_type;
typedef _Key value_type;
typedef _Compare key_compare;
typedef _Compare value_compare;
private:
typedef _Rb_tree, key_compare, _Alloc> _Rep_type;
_Rep_type _M_t; // 指定红黑树做为底层实现
public:
// 迭代器采用RB-tree的const_iterator，表示set的迭代器无法执行写入 *** 作
typedef typename _Rep_type::const_pointer pointer;
typedef typename _Rep_type::const_pointer const_pointer;
typedef typename _Rep_type::const_reference reference;
typedef typename _Rep_type::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;
typedef typename _Rep_type::allocator_type allocator_type;
// allocation/deallocation
// 只选取一个说明下：使用RB-tree的insert_unique()
#ifdef __STL_MEMBER_TEMPLATES
template
set(_InputIterator __first, _InputIterator __last)
: _M_t(_Compare(), allocator_type())
{ _M_t.insert_unique(__first, __last); }
.....
// accessors:
// 以下 *** 作都是转调RB-tree的函数
key_compare key_comp() const { return _M_t.key_comp(); }
value_compare value_comp() const { return _M_t.key_comp(); }
allocator_type get_allocator() const { return _M_t.get_allocator(); }
// insert/erase
.....
// set operations:同样是转调
// 关联式容器最好用自己提供的find()函数，效率会快一些
iterator find(const key_type& __x) const { return _M_t.find(__x); }
size_type count(const key_type& __x) const {
return _M_t.find(__x) == _M_t.end() ? 0 : 1;
}
iterator lower_bound(const key_type& __x) const {
return _M_t.lower_bound(__x);
}
iterator upper_bound(const key_type& __x) const {
return _M_t.upper_bound(__x);
}
pair equal_range(const key_type& __x) const {
return _M_t.equal_range(__x);
}
// 友元函数定义：这里为啥用友元，函数为什么这么组织呢
#ifdef __STL_TEMPLATE_FRIENDS
template
friend bool operator== (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&);
template
friend bool operator< (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&);
#else /* __STL_TEMPLATE_FRIENDS */
friend bool __STD_QUALIFIER
operator== __STL_NULL_TMPL_ARGS (const set&, const set&);
friend bool __STD_QUALIFIER
operator< __STL_NULL_TMPL_ARGS (const set&, const set&);
#endif /* __STL_TEMPLATE_FRIENDS */
};
map也会有序的（所以也采用RB-tree），其所有元素都是pair，根据键值自动排序，且不允许有两个相同的键值
template
struct pair {
typedef _T1 first_type;
typedef _T2 second_type;
_T1 first; // public
_T2 second;
pair() : first(_T1()), second(_T2()) {}
pair(const _T1& __a, const _T2& __b) : first(__a), second(__b) {}
#ifdef __STL_MEMBER_TEMPLATES
template
pair(const pair<_U1, _U2>& __p) : first(__p.first), second(__p.second) {}
#endif
};
// 为啥不直接写成类成员函数呢，类成员函数也是默认inline啊（不含有循环的话）
template
inline pair<_T1, _T2> make_pair(const _T1& __x, const _T2& __y)
{
return pair<_T1, _T2>(__x, __y);
} * 注意友元类的设计
* 注意重载[] *** 作符的设计
template
class map {
public:
// requirements:
__STL_CLASS_REQUIRES(_Tp, _Assignable);
__STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Key, _Key);
// 类型
typedef _Key key_type;
typedef _Tp data_type;
typedef _Tp mapped_type;
typedef pair value_type;
typedef _Compare key_compare; // 获取函数对象的类别
// 定义一个类的成员，这里是一个functor
class value_compare
: public binary_function { // 继承
// 自己做自己的类-类成员的友元，这样value_compare就可以访问map类成员了:_Compare
friend class map<_Key,_Tp,_Compare,_Alloc>;
protected :
_Compare comp;
value_compare(_Compare __c) : comp(__c) {}
public:
bool operator()(const value_type& __x, const value_type& __y) const {
return comp(__x.first, __y.first);
}
};
private:
typedef _Rb_tree, key_compare, _Alloc> _Rep_type;
_Rep_type _M_t; // 指定红黑树为底层结构
public:
typedef typename _Rep_type::pointer pointer;
typedef typename _Rep_type::const_pointer const_pointer;
typedef typename _Rep_type::reference reference;
typedef typename _Rep_type::const_reference const_reference;
typedef typename _Rep_type::iterator iterator;
typedef typename _Rep_type::const_iterator const_iterator;
typedef typename _Rep_type::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;
typedef typename _Rep_type::allocator_type allocator_type;
// 构造与析构
#ifdef __STL_MEMBER_TEMPLATES
template
map(_InputIterator __first, _InputIterator __last)
: _M_t(_Compare(), allocator_type())
{ _M_t.insert_unique(__first, __last); }
......
// accessors: 也都是转调,空间配置器在RB-tree结构中就配置好了
key_compare key_comp() const { return _M_t.key_comp(); }
value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
allocator_type get_allocator() const { return _M_t.get_allocator(); }
// map需重载[] *** 作符
// 以by reference方式传递，所以做为左值和右值（可以做右值？）都可以
// 也就是可以赋值和被赋值
_Tp& operator[](const key_type& __k) {
iterator __i = lower_bound(__k);
if (__i == end() || key_comp()(__k, (*__i).first))
// 这里用insert的原因：map不允许键值重复，所以这里会插入失败，返回插入失败的元素
__i = insert(__i, value_type(__k, _Tp()));
return (*__i).second;
}
......
// insert/erase
// 返回一个pair对象：第一个参数记录插入的位置（插入成功指向新元素，插入失败指向旧元素），
// 第二个参数标识是否插入成功
pair insert(const value_type& __x)
{ return _M_t.insert_unique(__x); }
// 返回迭代器，重载[]会用到
iterator insert(iterator position, const value_type& __x)
{ return _M_t.insert_unique(position, __x); }
.....
// map operations:
// sort方法定义在算法里
iterator find(const key_type& __x) { return _M_t.find(__x); }
const_iterator find(const key_type& __x) const { return _M_t.find(__x); }
size_type count(const key_type& __x) const {
return _M_t.find(__x) == _M_t.end() ? 0 : 1;
}
iterator lower_bound(const key_type& __x) {return _M_t.lower_bound(__x); }
const_iterator lower_bound(const key_type& __x) const {
return _M_t.lower_bound(__x);
}
iterator upper_bound(const key_type& __x) {return _M_t.upper_bound(__x); }
const_iterator upper_bound(const key_type& __x) const {
return _M_t.upper_bound(__x);
}
pair equal_range(const key_type& __x) {
return _M_t.equal_range(__x);
}
pair equal_range(const key_type& __x) const {
return _M_t.equal_range(__x);
}
// 怎么不重载 > *** 作符呢
#ifdef __STL_TEMPLATE_FRIENDS
template
friend bool operator== (const map<_K1, _T1, _C1, _A1>&,
const map<_K1, _T1, _C1, _A1>&);
template
friend bool operator< (const map<_K1, _T1, _C1, _A1>&,
const map<_K1, _T1, _C1, _A1>&);
#else /* __STL_TEMPLATE_FRIENDS */
friend bool __STD_QUALIFIER
operator== __STL_NULL_TMPL_ARGS (const map&, const map&);
friend bool __STD_QUALIFIER
operator< __STL_NULL_TMPL_ARGS (const map&, const map&);
#endif /* __STL_TEMPLATE_FRIENDS */
};
// 然后就是一堆内联函数了
template
inline bool operator==(const map<_Key,_Tp,_Compare,_Alloc>& __x,
const map<_Key,_Tp,_Compare,_Alloc>& __y) {
return __x._M_t == __y._M_t;
}
......
multi-（set/map）：区别主要是insert时用了insert_equal()而不是insert_unique()
从空间配置服务于容器的角度来说，感觉set和map也属于适配器；
RB-tree之所以将结构和数据分离，也是为了分别为set和map服务，因为set和map最重要的区别就是data，一个是value，一个是pair（key，value）.
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）