天天看點

STL 标準模闆庫之<set>詳解

        浏覽本文之前,事先告知,本文由兩個部分,如果你隻是忘記了<set>的某些常用的用法,那隻要看前半部分《STL_<set>快速養成》,如果你是初次接觸set并且想要做一番深究的話,可以把整篇都看完,相信大家或多或少都會有所收獲

STL 标準模闆庫之&lt;set&gt;詳解

一。《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      
find(const value_type& val) const;(C++98)      
const_iterator      
find(const value_type& val) const;(C++11)      
iterator      
find(const value_type& val);       (C++11)      
函數傳回找到元素的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