C++(STL):27 ---關聯式容器set源碼剖析

一、set

set文法使用參閱：

set的特性

set所有元素都會根據元素的鍵值自動被排序

set中的鍵值就是實值，實值就是鍵值

預設情況下set不允許兩個元素重複

set的疊代器

不能根據set的疊代器改變set元素的值。因為其鍵值就是實值，實值就是鍵值，如果改變set元素值，會嚴重破壞set組織

在後面的源碼中會看到，set的疊代器set<T>::iterator被定義為底層RB-tree的const_iterator。是以set的疊代器是一種constant iterators

set擁有與list的相同的某些性質

當用戶端對它進行元素新增（insert）操作或删除（erase）操作時，操作之前的所有疊代器在操作完成之後依然有效（當然，被删除的那個元素的疊代器無效）

相關算法

STL提供了一組set/multiset相關算法，包括交集（set_intersection）、聯集（set_union）、差集（set_difference）、對稱差集（set_symmetric_difference）

詳情會在後面的“算法”文章中介紹

set的底層結構

由于RB-tree是一種平衡二叉搜尋樹，自動排序的效果很不錯，是以标準的STL set是以RB-tree為底層機制

又由于set所開放的各種操作接口，RB-tree也都提供了，是以幾乎所有的set操作行為，都隻是轉調用RB-tree的操作行為而已

set源碼

下面是set的源代碼摘錄

//代碼摘錄于stl_set.h
template <class _Key, class _Compare, class _Alloc>
class set {
// requirements:




__STL_CLASS_REQUIRES(_Key, _Assignable);
__STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Key, _Key);




public:
// typedefs:




typedef _Key     key_type;
typedef _Key     value_type;
typedef _Compare key_compare;
typedef _Compare value_compare;
private:
typedef _Rb_tree<key_type, value_type,
_Identity<value_type>, key_compare, _Alloc> _Rep_type;
_Rep_type _M_t;  // 采用紅黑樹來表現set
public:
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;
//注意上一行，iterator定義為RB-tree的const_iterator，表示
//set的疊代器無法執行寫入操作
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
//注意，set一定使用RB-=tree的insert_unique()而非insert_equal()
//multiset才使用RB-tree的insert_equal()
set() : _M_t(_Compare(), allocator_type()) {}
explicit set(const _Compare& __comp,
const allocator_type& __a = allocator_type())
: _M_t(__comp, __a) {}




#ifdef __STL_MEMBER_TEMPLATES
template <class _InputIterator>
set(_InputIterator __first, _InputIterator __last)
: _M_t(_Compare(), allocator_type())
{ _M_t.insert_unique(__first, __last); }




template <class _InputIterator>
set(_InputIterator __first, _InputIterator __last, const _Compare& __comp,
const allocator_type& __a = allocator_type())
: _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
#else
set(const value_type* __first, const value_type* __last)
: _M_t(_Compare(), allocator_type())
{ _M_t.insert_unique(__first, __last); }




set(const value_type* __first,
const value_type* __last, const _Compare& __comp,
const allocator_type& __a = allocator_type())
: _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }




set(const_iterator __first, const_iterator __last)
: _M_t(_Compare(), allocator_type())
{ _M_t.insert_unique(__first, __last); }




set(const_iterator __first, const_iterator __last, const _Compare& __comp,
const allocator_type& __a = allocator_type())
: _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
#endif /* __STL_MEMBER_TEMPLATES */




set(const set<_Key,_Compare,_Alloc>& __x) : _M_t(__x._M_t) {}
set<_Key,_Compare,_Alloc>& operator=(const set<_Key, _Compare, _Alloc>& __x)
{
_M_t = __x._M_t;
return *this;
}




//以下所有的set操作，RB-tree都已提供，是以set隻要傳遞調用即可
// accessors:




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(); }




iterator begin() const { return _M_t.begin(); }
iterator end() const { return _M_t.end(); }
reverse_iterator rbegin() const { return _M_t.rbegin(); }
reverse_iterator rend() const { return _M_t.rend(); }
bool empty() const { return _M_t.empty(); }
size_type size() const { return _M_t.size(); }
size_type max_size() const { return _M_t.max_size(); }
void swap(set<_Key,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }




// insert/erase
pair<iterator,bool> insert(const value_type& __x) {
pair<typename _Rep_type::iterator, bool> __p = _M_t.insert_unique(__x);
return pair<iterator, bool>(__p.first, __p.second);
}
iterator insert(iterator __position, const value_type& __x) {
typedef typename _Rep_type::iterator _Rep_iterator;
return _M_t.insert_unique((_Rep_iterator&)__position, __x);
}
#ifdef __STL_MEMBER_TEMPLATES
template <class _InputIterator>
void insert(_InputIterator __first, _InputIterator __last) {
_M_t.insert_unique(__first, __last);
}
#else
void insert(const_iterator __first, const_iterator __last) {
_M_t.insert_unique(__first, __last);
}
void insert(const value_type* __first, const value_type* __last) {
_M_t.insert_unique(__first, __last);
}
#endif /* __STL_MEMBER_TEMPLATES */
void erase(iterator __position) {
typedef typename _Rep_type::iterator _Rep_iterator;
_M_t.erase((_Rep_iterator&)__position);
}
size_type erase(const key_type& __x) {
return _M_t.erase(__x);
}
void erase(iterator __first, iterator __last) {
typedef typename _Rep_type::iterator _Rep_iterator;
_M_t.erase((_Rep_iterator&)__first, (_Rep_iterator&)__last);
}
void clear() { _M_t.clear(); }




// set operations:




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<iterator,iterator> equal_range(const key_type& __x) const {
return _M_t.equal_range(__x);
}




#ifdef __STL_TEMPLATE_FRIENDS
template <class _K1, class _C1, class _A1>
friend bool operator== (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&);
template <class _K1, class _C1, class _A1>
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 */
};

set的使用案例

#include <iostream>
#include <set>
using namespace std;




int main()
{
int i;
int ia[5] = { 0,1,2,3,4 };
set<int> iset(ia,ia+5);
std::cout << "size=" << iset.size() << std::endl;
std::cout << "3 count" << iset.count(3) << std::endl << std::endl;




iset.insert(3);
std::cout << "size=" << iset.size() << std::endl;
std::cout << "3 count" << iset.count(3) << std::endl << std::endl;




iset.insert(5);
std::cout << "size=" << iset.size() << std::endl;
std::cout << "3 count" << iset.count(3) << std::endl << std::endl;




iset.erase(1);
std::cout << "size=" << iset.size() << std::endl;
std::cout << "3 count" << iset.count(3) << std::endl;
std::cout << "1 count" << iset.count(1) << std::endl << std::endl;




set<int>::iterator ite1 = iset.begin();
set<int>::iterator ite2 = iset.end();
for (; ite1 != ite2; ite1++)
std::cout << *ite1<<" ";
std::cout << std::endl << std::endl;




//使用STL算法來搜尋元素(循環搜尋的)，但是沒有set的内置find函數高效
ite1 = find(iset.begin(), iset.end(), 3);
if (ite1 != iset.end())
std::cout << "3 found" << std::endl;
else
std::cout << "3 not found" << std::endl << std::endl;




//使用set的内置find函數，比STL算法高效
ite1 = iset.find(1);
if (ite1 != iset.end())
std::cout << "1 found" << std::endl;
else
std::cout << "1 not found" << std::endl << std::endl;




//*ite1 = 9;  錯誤，不能通過set的疊代器來改變元素的值
return 0;
}

C++(STL):27 ---關聯式容器set源碼剖析

一、set

set的特性

set的疊代器

set擁有與list的相同的某些性質

相關算法

set的底層結構

set源碼

set的使用案例

繼續閱讀

100道JavaScript 面試題和答案(下）

疊代器使用方法1. 簡介2. 概念3. 示例代碼4. 運作結果

JavaScript 生成器的簡介

ES6深度解析：Generators

for...of循環的使用

ES6 疊代器和生成器

Vue開發中可以使用的 ES6新特征

新星計劃Day3【JavaSE】集合 Part1

android 添加新的鍵值，自定義按鍵【轉】

java集合之ArrayList 源碼閱讀記錄

cd 915E(離散化+線段樹)（新線段樹模闆）

【python基礎-字典】

yield語句

Unity3d中協程的原理，你要的yield return new xxx的真正了解之道之前還是要說一下疊代器c#裡的yield return回到unity3d應用之二強行總分總

Python3學習筆記（2）——特性和語句1 特性2 語句

【python】可疊代對象（Iterable）與疊代器（Iterator）