本文共 5482 字，大约阅读时间需要 18 分钟。

【结构】

set和multiset会根据特定的排序原则将元素排序。两者不同之处在于，multisets允许元素重复，而set不允许重复。如果没有特别的排序原则，采用默认的less，已operator < 对元素进行比较，以便完成排序。

【功能】

和所有的标准关联容器类似，set和multiset通常以平衡二叉树完成。

自动排序的主要优点在于使二叉树搜寻元素具有良好的性能，在其搜索函数算法具有对数复杂度。但是自动排序也造成了一个限制，不能直接改变元素值，因为这样会打乱原有的顺序，要改变元素的值，必须先删除旧元素，再插入新元素。所以sets和multisets具有以下特点：

• 不提供直接用来存取元素的任何操作元素
• 通过迭代器进行元素的存取。

【操作函数】

3.1 构造、拷贝、析构

3.2 非变动性操作

3.3 特殊的搜寻函数

　　sets和multisets在元素快速搜寻方面做了优化设计，提供了特殊的搜寻函数，所以应优先使用这些搜寻函数，可获得对数复杂度，而非STL的线性复杂度。比如在1000个元素搜寻，对数复杂度平均十次，而线性复杂度平均需要500次。

3.4 赋值

3.5 迭代器相关函数

　　sets和multisets的迭代器是双向迭代器，对迭代器操作而言，所有的元素都被视为常数，可以确保你不会人为改变元素值，从而打乱既定顺序，所以无法调用变动性算法，如remove()。

3.6 安插和删除元素

　　必须保证参数有效,迭代器必须指向有效位置，序列起点不能位于终点之后，不能从空容器删除元素。

 【示例代码】

  set

// cont/set1.cpp    #include 
   
        #include 
    
         using namespace std;    int main()    {       /*type of the collection:        *-no duplicates        *-elements are integral values        *-descending order        */       typedef set
     
      
        > IntSet;       IntSet coll1;         // empty set container       //insert elements in random order       coll1.insert(4);       coll1.insert(3);       coll1.insert(5);       coll1.insert(1);       coll1.insert(6);       coll1.insert(2);       coll1.insert(5);       //iterate over all elements and print them       IntSet::iterator pos;       for (pos = coll1.begin(); pos != coll1.end(); ++pos) {           cout << *pos << ' ';       }       cout << endl;       //insert 4 again and process return value       pair
       
         status = coll1.insert(4);       if (status.second) {           cout << "4 inserted as element "                << distance (coll1.begin(),status. first) + 1                << endl;       }       else {           cout << "4 already exists" << endl;       }       //assign elements to another set with ascending order       set
        
          coll2(coll1.begin(), coll1.end()); //print all elements of the copy copy (coll2.begin(), coll2.end(), ostream_iterator
         
          (cout," ")); cout << endl; //remove all elements up to element with value 3 coll2.erase (coll2.begin(), coll2.find(3)); //remove all elements with value 5 int num; num = coll2.erase (5); cout << num << " element(s) removed" << endl; //print all elements copy (coll2.begin(), coll2.end(), ostream_iterator
          
           (cout," ")); cout << endl; }
          
         
        
       
      
     
    
   

输出：

6 5 4 3 2 1   4 already exists   1 2 3 4 5 6   1 element(s) removed   3 4 6

multiset

// cont/mset1.cpp   #include 
   
       #include 
    
        using namespace std;   int main()   {       /*type of the collection:        *-duplicates allowed        *-elements are integral values        *-descending order        */       typedef multiset
     
      
        > IntSet;       IntSet coll1,        // empty multiset container       //insert elements in random order       coll1.insert(4);       coll1.insert(3);       coll1.insert(5);       coll1.insert(l);       coll1.insert(6);       coll1.insert(2);       coll1.insert(5);       //iterate over all elements and print them       IntSet::iterator pos;       for (pos = coll1.begin(); pos != coll1.end(); ++pos) {           cout << *pos << ' ';       }       cout << endl;       //insert 4 again and process return value       IntSet::iterator ipos = coll1.insert(4);       cout << "4 inserted as element "            << distance (coll1.begin(),ipos) + 1            << endl;       //assign elements to another multiset with ascending order       multiset
       
         coll2(coll1.begin(),                              coll1.end());       //print all elements of the copy       copy (coll2.begin(), coll2.end(),             ostream_iterator
        
         (cout," ")); cout << endl; //remove all elements up to element with value 3 coll2.erase (coll2.begin(), coll2.find(3)); //remove all elements with value 5 int num; num = coll2.erase (5); cout << num << " element(s) removed" << endl; //print all elements copy (coll2.begin(), coll2.end(), ostream_iterator
         
          (cout," ")); cout << endl; }
         
        
       
      
     
    
   

输出：

6 5 5 4 3 2 14 inserted as element 51 2 3 4 4 5 5 62 element(s) removed3 4 4 6

转载地址：http://qyben.baihongyu.com/