浏覽本文之前，事先告知，本文由兩個部分，如果你隻是忘記了<set>的某些常用的用法，那隻要看前半部分《STL_<set>快速養成》，如果你是初次接觸set并且想要做一番深究的話，可以把整篇都看完，相信大家或多或少都會有所收獲
一。《STL_<set>快速養成》
1.<set>的特性
<set>中所有的元素都互不相同，并且是有序的（預設從小到大），在内部是通過二叉查找樹實作，與map不同的是其關鍵詞（key）和值（value）相等
2.如何建立
-建立一個空的set
set<int> set_empty
-建立一個帶大于比較器的set，預設是小于比較器less<int>
set<int,greater<int>> set_greater
-用數組初始化一個set
int array[3]={1,2,3};
set<int> set_array(array,array+3);
-用拷貝構造函數初始化set
set<int> set_1;
set<int> set_2(set_1);
-區間初始化set
set<int> set_1;
set<int> set_2(set_1.begin(),set_1.end())
-自定義比較器
以類為比較器
struct classcmp
{
bool operator()(const int& lhs, const int& rhs)
{
return lhs < rhs ;
}
};
int main(void)
{
set<int, classcmp> s5
return 0;
}
以函數指針為比較器
bool fncmp(int lhs, int rhs)
{
return lhs < rhs ;
}
int main(void)
{
bool(*fn_pt)(int, int) = fncmp ;
set<int, bool(*)(int, int)> s1(fn_pt) ;
system("pause") ;
return 0 ;
}
3.如何周遊
-正向周遊
使用while()
int a[3] = {1, 2, 3} ;
set<int> s(a, a + 3) ;
set<int>::const_iterator itor ;
itor = s.begin() ;
while (itor != s.end())
{
cout << *itor << endl ;
++itor ;
}
使用for()
int a[3] = {1, 2, 3} ;
set<int> s(a, a + 3) ;
set<int>::const_iterator itor ;
for (itor = s.begin(); itor != s.end(); ++itor)
{
cout << *itor << endl ;
}
-反向周遊
使用while()
int a[3] = {1, 2, 3} ;
set<int> s(a, a + 3) ;
set<int>::const_reverse_iterator ritor ;
ritor = s.rbegin() ;
while (ritor != s.rend())
{
cout << *ritor << endl ;
++ritor ;
}
使用for()
int a[3] = {1, 2, 3} ;
set<int> s(a, a + 3) ;
set<int>::const_reverse_iterator ritor ;
for (ritor = s.rbegin(); ritor != s.rend(); ++ritor)
{
cout << *ritor << endl ;
}
4.如何插入
-插入單個值
set<int> s;
s.insert(value);
-插入整個數組
int a[3] = {1, 2, 3} ;
set<int> s ;
s.insert(a, a + 3) ;
-插入其他set的值
int a[3] = {1, 2, 3} ;
set<int> s(a, a + 3) ;
set<int> s1 ;
s1.insert(s.begin(), s.end()) ;
5.如何删除
set<int> s ;
for (int i = 1; i <= 5; ++i)
s.insert(i) ;
set<int>::const_iterator citor ;
citor = s.begin() ;
++citor ; // citor now point to 2
// 删除單個元素
s.erase(citor) ; // erase 2 ;
//批量删除
citor = s.find(3) ; // itor now point to 3
s.erase(citor, s.end()) ; // erase 3, 4, 5
//删除所有元素
s.erase(s.begin(), s.end()) ;// erase all elements, same as s.clear()
6.如何查找
-find()
set<int> s ;
for (int i = 1; i <= 5; ++i)
s.insert(i) ;
set<int>::iterator itor ;
itor = s.find(4) ;
if(itor != s.end()) // itor point to s.end() if not found
cout << "found" ;
else
cout << "not found" ;
-count()
set<int> s ;
for (int i = 1; i <= 5; ++i)
s.insert(i) ;
set<int>::iterator itor ;
if(s.count(4) == 1) // return 1 if s contains 4, else 0
cout << "s contains 4" ;
else
cout << "s does not contains 4" ;
OK,速成到這裡就結束了，想必大家已經可以照葫蘆畫瓢寫出代碼了，接下來是對其内部的解釋，當然不是我寫的，是一篇類似于API的文章
C++ STL之Set容器的用法
1 set中的元素類型... 1
2 set中構造相關函數... 2
3 set中的疊代器... 3
4 set中的容量相關函數... 3
5 set中元素修改函數... 3
5.1 insert 函數... 3
5.2 erase 函數... 4
5.3 clear 函數... 5
5.4 swap 函數... 5
5.5 emplace 函數... 5
5.6 emplace_hint函數... 5
6 set 中的比較函數體... 6
6.1 key_com 函數... 6
6.2 value_com函數... 6
7 set的其他操作函數... 7
7.1 find 函數... 7
7.2 count 函數... 8
7.3 lower_bound 函數... 8
7.4 upper_bound函數... 8
7.5 equal_range 函數... 9
7.6 get_allocator 函數... 10
Set容器是一個關聯容器，容器中的元素互不相同，并且容器中的元素按照鍵值大小進行排序。每當插入或者删除一個元素，容器都會重新排序。Set容器有兩大特點，一個是元素排序，另一個就是查詢速度快（當然沒有vector快）。Set擷取元素時通過鍵值，關聯容器都這樣。Set是通過二進制查找樹實作的，再具體點就是紅黑樹。
1 set中的元素類型
| member type | definition | notes |
| key_type | The first template parameter (T) | |
| value_type | The first template parameter (T) | |
| key_compare | The second template parameter (Compare) | defaults to: less<key_type> |
| value_compare | The second template parameter (Compare) | defaults to: less<value_type> |
| allocator_type | The third template parameter (Alloc) | defaults to:allocator<value_type> |
| reference | allocator_type::reference | for the default allocator:value_type& |
| const_reference | allocator_type::const_reference | for the default allocator: const value_type& |
| pointer | allocator_type::pointer | for the default allocator:value_type* |
| const_pointer | allocator_type::const_pointer | for the default allocator: const value_type* |
| iterator | a bidirectional iterator to value_type | convertible to const_iterator |
| const_iterator | a bidirectional iterator to const value_type | |
| reverse_iterator | reverse_iterator<iterator> | |
| const_reverse_iterator | reverse_iterator<const_iterator> | |
| difference_type | a signed integral type, identical to:iterator_traits<iterator>::difference_type | usually the same as ptrdiff_t |
| size_type | an unsigned integral type that can represent any non-negative value of difference_type | usually the same as size_t |
關于這個無需多言，切記set中的iterator是指向const 元素。
2 set中構造相關函數
| empty (1) | explicit set (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); explicit set (const allocator_type& alloc); |
| range (2) | template <class InputIterator> set (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& = allocator_type()); |
| copy (3) | set (const set& x); set (const set& x, const allocator_type& alloc); |
| move (4) | set (set&& x); set (set&& x, const allocator_type& alloc); |
| initializer list (5) | set (initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); |
以上分别為預設構造函數，範圍構造函數，複制構造函數，移動構造函數，初始化清單構造函數，其中最後兩個是C++11中的版本。關于構造函數，不同的編譯器可能提供的形式不一樣，但是種類都是這幾種。
構造函數示例：
#include <set> bool fncomp ( int lhs, int rhs) { return lhs<rhs;}
{ return lhs<rhs;}
};
int main ()
int myints[]= {10,20,30,40,50};
bool (*fn_pt)( int , int ) = fncomp;
return 0;
}
3 set中的疊代器
begin Return iterator to beginning (publicmember function )
end Returniterator to end (public memberfunction )
rbegin Returnreverse iterator to reverse beginning (publicmember function )
rend Returnreverse iterator to reverse end (public memberfunction )
cbegin Returnconst_iterator to beginning (publicmember function )
cend Returnconst_iterator to end (publicmember function )
crbegin Returnconst_reverse_iterator to reverse beginning (public member function )
crend Returnconst_reverse_iterator to reverse end (publicmember function )
關于疊代器也沒什麼好說的，疊代器和前面的都一樣。
4 set中的容量相關函數
empty Test whether container is empty (public member function )
size Return container size (public member function )
max_size Returnmaximum size (public member function )
這個和其它容量一樣。
5 set中元素修改函數
insert Insert element (public memberfunction )
erase Erase elements (public memberfunction )
swap Swapcontent (public member function )
clear Clearcontent (public member function )
emplace Constructand insert element (publicmember function )
emplace_hint Constructand insert element with hint (publicmember function )
5.1 insert 函數
| single element (1) | pair<iterator,bool> insert (const value_type& val); pair<iterator,bool> insert (value_type&& val); |
| with hint (2) | iterator insert (const_iterator position, const value_type& val); iterator insert (const_iterator position, value_type&& val); |
| range (3) | template <class InputIterator> void insert (InputIterator first, InputIterator last); |
| initializer list (4) | void insert (initializer_list<value_type> il); |
要注意其中的函數的傳回類型，這個在程式設計中或許會很有用，兩種不同的顔色來區分C++11中增加的函數，示例如下：
int main ()
std::set< int > myset;
std::set< int >::iterator it;
std::pair<std::set< int >::iterator, bool > ret;
myset.insert (myints,myints+3);
std::cout << "myset contains:" ;
for (it=myset.begin(); it!=myset.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n' ;
return 0;
}
結果：
myset contains: 5 10 15 20 24 25 26 30 40 50 5.2 erase 函數 | (1) | void erase (iterator position); |
| (2) | size_type erase (const value_type& val); |
| (3) | void erase (iterator first, iterator last); |
| (1) | iterator erase (const_iterator position); |
| (2) | size_type erase (const value_type& val); |
| (3) | iterator erase (const_iterator first, const_iterator last); |
紅色表格表示C++98，藍色表示C++11。函數的傳回值，其中第二個函數表示删除的元素的個數，當然在set中其傳回值最多是1，在C++11中，其餘兩個函數皆有傳回值為iterator類型的值，其指向删除的最後一個元素，或者指向set的末尾。示例如下：
int main ()
std::set< int > myset;
std::set< int >::iterator it;
it = myset.begin();
myset.erase (it);
myset.erase (40);
it = myset.find (60);
myset.erase (it, myset.end());
std::cout << "myset contains:" ;
for (it=myset.begin(); it!=myset.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n' ;
return 0;
}
結果：
myset contains: 10 30 50 5.3 clear 函數
void clear(); 清空set，容器大小變為0
5.4 swap 函數
void swap (set& x); 交換兩個set的内容
5.5 emplace 函數
template <class... Args> pair<iterator,bool> emplace (Args&&... args); 這個是C++11中的函數，也是插入一個元素
5.6 emplace_hint 函數
template <class... Args> iterator emplace_hint (const_iterator position, Args&&... args); 在一定的位置插入元素，position參數隻是用來提高插入的速度，并不一定就是說要在此處插入元素。示例
int main ()
std::set<std::string> myset;
auto it = myset.cbegin();
myset.emplace_hint (it, "alpha" );
it = myset.emplace_hint (myset.cend(), "omega" );
it = myset.emplace_hint (it, "epsilon" );
it = myset.emplace_hint (it, "beta" );
std::cout << "myset contains:" ;
for ( const std::string& x: myset)
std::cout << ' ' << x;
std::cout << '\n' ;
return 0;
}
結果：
myset contains: alpha beta epsilon omega 6 set 中的比較函數體
key_comp Returncomparison object (public member function )
value_comp Returncomparison object (public member function )
這兩個函數都是擷取set容器中比較函數
6.1 key_com 函數
key_compare key_comp() const; 函數傳回比較函數對象，預設的是升序排列。示例： int main ()
std::set< int > myset;
int highest;
std::set< int >::key_compare mycomp = myset.key_comp();
for ( int i=0; i<=5; i++) myset.insert(i);
std::cout << "myset contains:" ;
highest=*myset.rbegin();
std::set< int >::iterator it=myset.begin();
std::cout << ' ' << *it;
} while ( mycomp(*(++it),highest) );
std::cout << '\n' ;
return 0;
}
結果： myset contains: 0 1 2 3 4 6.2 value_com 函數 value_compare value_comp()const 函數傳回元素比較函數對象，預設的是升序排列，在set中，value_comp函數和key_value函數的作用一模一樣。示例： int main ()
std::set< int > myset;
std::set< int >::value_compare mycomp = myset.value_comp();
for ( int i=0; i<=5; i++) myset.insert(i);
std::cout << "myset contains:" ;
int highest=*myset.rbegin();
std::set< int >::iterator it=myset.begin();
std::cout << ' ' << *it;
} while ( mycomp(*(++it),highest) );
std::cout << '\n' ;
return 0;
}
結果： myset contains: 0 1 2 3 4 7 set的其他操作函數 find Get iterator to element (public member function )
count Count elements with a specific value (public member function )
lower_bound Return iterator to lower bound (public member function )
upper_bound Returniterator to upper bound (public member function )
equal_range Get range of equal elements (public member function )
get_allocator Get allocator (public memberfunction )
7.1 find 函數 | |
| |
| |
函數傳回找到元素的iterator，如果找不到就指向set的末尾 int main ()
std::set< int > myset;
std::set< int >::iterator it;
it=myset.find(20);
myset.erase (it);
myset.erase (myset.find(40));
std::cout << "myset contains:" ;
for (it=myset.begin(); it!=myset.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n' ;
return 0;
}
結果：
myset contains: 10 30 50 7.2 count 函數 size_type count (const value_type& val) const; 函數傳回值為val的元素的個數，當然在set容器中其最大為1.示例： int main ()
std::set< int > myset;
for ( int i=0; i<10; ++i)
std::cout << i;
if (myset.count(i)!=0)
std::cout << " is an element of myset.\n" ;
std::cout << " is not an element of myset.\n" ;
}
return 0;
}
結果： 0 is not an element of myset. 1 is not an element of myset. 2 is not an element of myset. 3 is an element of myset. 4 is not an element of myset. 5 is not an element of myset. 6 is an element of myset. 7 is not an element of myset. 8 is not an element of myset. 9 is an element of myset. 7.3 lower_bound 函數 iterator lower_bound (const value_type& val) const; （C++98） iterator lower_bound (const value_type& val);（C++11） const_iterator lower_bound (const value_type& val) const;（C++11） 函數傳回set中第一個小于或者等于val的元素的iterator。 7.4 upper_bound 函數 iterator upper_bound (const value_type& val) const; （C++98） iterator upper_bound (const value_type& val);（C++11） const_iterator upper_bound (const value_type& val) const;（C++11） 函數傳回set中第一個大于或者等于val的元素的iterator。示例 int main ()
std::set< int > myset;
std::set< int >::iterator itlow,itup;
std::cout << "myset contains:" ;
for (std::set< int >::iterator it=myset.begin(); it!=myset.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n' ;
return 0;
}
結果： myset contains: 10 20 70 80 90 7.5 equal_range 函數 pair<iterator,iterator> equal_range (const value_type& val) const; （C++98） pair<const_iterator,const_iterator> equal_range (const value_type& val) const;（C++11） pair<iterator,iterator> equal_range (const value_type& val);(C++11) 函數傳回等于set中val的上下界的iterator。示例： int main ()
std::set< int > myset;
std::pair<std::set< int >::const_iterator,std::set< int >::const_iterator> ret;
ret = myset.equal_range(30);
std::cout << "the lower bound points to: " << *ret.first << '\n' ;
std::cout << "the upper bound points to: " << *ret.second << '\n' ;
return 0;
}
結果： the lower bound points to: 30 the upper bound points to: 40 7.6 get_allocator 函數 allocator_type get_allocator() const; 函數傳回set的配置設定器對象 示例： int main ()
std::set< int > myset;
int * p;
unsigned int i;
p=myset.get_allocator().allocate(5);
for (i=0; i<5; i++) p[i]=(i+1)*10;
std::cout << "The allocated array contains:" ;
for (i=0; i<5; i++) std::cout << ' ' << p[i];
std::cout << '\n' ;
myset.get_allocator().deallocate(p,5);
return 0;
}
結果： The allocated array contains: 10 20 30 40 50 參考：http://www.cnblogs.com/graphics/archive/2010/06/01/1749569.html
![POJ 1284 Primitive Roots (歐拉函數&原根定理)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)