1 set和multiset容器的能力
set
和multiset容器的內(nèi)部結(jié)構(gòu)通常由平衡二叉樹(balanced binary
tree)來實(shí)現(xiàn)。當(dāng)元素放入容器中時(shí)，會(huì)按照一定的排序法則自動(dòng)排序，默認(rèn)是按照less<>排序規(guī)則來排序。這種自動(dòng)排序的特性加速了元
素查找的過程，但是也帶來了一個(gè)問題：不可以直接修改set或multiset容器中的元素值，因?yàn)檫@樣做就可能違反了元素自動(dòng)排序的規(guī)則。如果你希望修
改一個(gè)元素的值，必須先刪除原有的元素，再插入新的元素。
2 set和multiset容器的操作
Constructor and Destructor
- set c: 創(chuàng)建一個(gè)空的set或multiset容器
- set c(op): 創(chuàng)建一個(gè)空的使用op作為排序法則的set或multiset容器
- set c1(c2): 創(chuàng)建一個(gè)已存在的set或multiset容器的復(fù)制品，容器的類型和所有元素一同復(fù)制
- set c(beg, end): 創(chuàng)建一個(gè)set或multiset容器，并且以[beg, end)范圍中的元素進(jìn)行初始化
- set c(beg, end, op): 創(chuàng)建一個(gè)使用op作為排序法則的set或multiset容器，并且以[beg, end)范圍中的元素進(jìn)行初始化
- c.~set(): 容器的析構(gòu)函數(shù)，銷毀所有的元素，釋放所有的分配內(nèi)存
上面的set可以是下面幾種形式：
- set<type>: 以less<>為排序法則的set
- set<type, op>: 以op為排序法則的set
- multiset<type>: 以less<>為排序法則的multiset
- multiset<type, op>: 以op為排序法則的multiset
從上面我們可以看到，可以從兩個(gè)地方來指定排序法則：
（1）作為模板參數(shù)
例如：std::set<int, greater<int> > col1;
這種情況下，排序法則本身作為容器類型的一部分。對(duì)于一個(gè)set或者multiset容器，只有當(dāng)元素類型和排序法則類型都相同時(shí)，他們的類型才被認(rèn)為相同，否則就是不同類型的容器。
（2）作為構(gòu)造函數(shù)參數(shù)
例如：std::set<int> col1(greater<int>);
這種情況下指定的排序法則不作為容器類型的一部分，你可以為相同類型的容器指定不同的排序規(guī)則。這通常應(yīng)用于要求相同的容器類型，但排序規(guī)則可以不同的場(chǎng)合。
Size and Comparing
set
和multiset容器同樣提供size(), empty(), max_size()三個(gè)關(guān)于查詢?cè)財(cái)?shù)目的接口，提供==, !=, <,
<=, >, >=等比較操作符。但值得注意的是比較操作符只針對(duì)相同類型的容器，元素類型和排序法則類型都必須相同。
Special Search Operations
set和multiset容器的內(nèi)部結(jié)構(gòu)對(duì)于元素的查找提供了優(yōu)化空間，所以它們提供了一些特殊的查找接口，這些查找操作通常要比同名的通用算法高效，所以在相同的條件下應(yīng)該優(yōu)先使用這些接口。
- count(val): 返回容器中值等于val的元素?cái)?shù)目。
- find(val): 返回容器中值等于val的第一個(gè)元素的iterator位置；如果沒有匹配元素，則返回end()位置。
- lower_bound(val): 返回容器中第一個(gè)值大于或等于val的元素的iterator位置。
- upper_bound(val): 返回容器中第一個(gè)值大于val的元素的iterator位置。
- equal_range(val): 返回容器中值等于val的所有元素的范圍[beg, end)組成的pair<beg, end> 。
下面我們看一個(gè)使用lower_bound(), upper_bound和equal_range(val)例子，以加深對(duì)它們的理解：
#include <iostream>
#include <set>
#include "print.hpp"
using namespace std;
int main()
{
multiset<int> col1;
col1.insert(2);
col1.insert(5);
col1.insert(4);
col1.insert(6);
col1.insert(1);
col1.insert(5);
PRINT_ELEMENTS(col1, "col1: ");
cout << endl;
multiset<int>::const_iterator pos;
pair<multiset<int>::iterator, multiset<int>::iterator> range;
cout << "lower_bound(3): " << *col1.lower_bound(3) << endl;
cout << "upper_bound(3): " << *col1.upper_bound(3) << endl;
range = col1.equal_range(3);
cout << "equal_range(3): " << *range.first << " " << *range.second << endl;
cout << "elements with value(3): ";
for (pos = range.first; pos != range.second; ++pos)
{
cout << *pos << " ";
}
cout << endl;
cout << endl;
cout << "lower_bound(5): " << *col1.lower_bound(5) << endl;
cout << "upper_bound(5): " << *col1.upper_bound(5) << endl;
range = col1.equal_range(5);
cout << "equal_range(5): " << *range.first << " " << *range.second << endl;
cout << "elements with value(5): ";
for (pos = range.first; pos != range.second; ++pos)
{
cout << *pos << " ";
}
cout << endl;
}
執(zhí)行結(jié)果如下：
col1: 1 2 4 5 5 6
lower_bound(3): 4
upper_bound(3): 4
equal_range(3): 4 4
elements with value(3):
lower_bound(5): 5
upper_bound(5): 6
equal_range(5): 5 6
elements with value(5): 5 5
Assignment
set和multiset容器只提供最基本的賦值操作：
- c1 = c2: 把c2的所有元素復(fù)制到c1中，同時(shí)c1原有的元素被銷毀。
- c1.swap(c2): 交換c1和c2的元素。
- swap(c1, c2): 同上，只不過這是一個(gè)通用算法。
需要注意的是兩個(gè)容器的類型要一致（包括元素類型和排序法則類型）。
Inserting and Removing Elements
set和multiset容器的插入和刪除元素接口跟其他容器也非常類似，但在細(xì)節(jié)上卻存在差別。
- c.insert(elem): 在容器中插入元素elem的一份拷貝，并返回新元素的iterator位置；如果是set容器，同時(shí)還返回是否插入成功的標(biāo)志。
- c.insert(pos, elem): 在容器中插入元素elem的一份拷貝，并返回新元素的iterator位置；因?yàn)閟et和multiset容器的元素是自動(dòng)排序的，所以pos位置只是插入位置的一個(gè)提示，設(shè)置恰當(dāng)?shù)脑挘梢蕴岣卟迦朐氐男省?/span>
- c.insert(beg, end): 在容器中插入[beg, end)范圍中所有元素的拷貝，沒有返回值。
- c.erase(val): 刪除容器中所有值為val的元素，返回刪除元素的數(shù)目。
- c.erase(pos): 刪除容器中位置pos處的元素，沒有返回值。
- c.erase(beg, end): 刪除容器中[ben, end)范圍內(nèi)所有的元素，沒有返回值。
- c.clear(): 刪除容器中所有元素，使容器成為空容器。
其中我們重點(diǎn)說一下c.insert(elem)接口。
對(duì)于set容器，它的定義如下：
pair<iterator, bool> insert(const TYPE& val);
而對(duì)于multiset容器，它的定義如下：
iterator insert(const TYPE& val);
它
們的不同就是set容器的insert接口返回的是一個(gè)pair<iterator,
bool>，而multiset容器的insert接口直接返回一個(gè)iterator。這是因?yàn)閟et容器中不允許有重復(fù)的元素，如果容器中已經(jīng)存
在一個(gè)跟插入值相同的元素，那么插入操作就會(huì)失敗，而pair中的bool值就是標(biāo)識(shí)插入是否成功的。而multiset不存在這個(gè)問題。
3 set和multiset容器的異常處理
因?yàn)閟et和multiset容器的獨(dú)特內(nèi)部結(jié)構(gòu)，當(dāng)發(fā)生異常時(shí)，也可以把影響減到最小。也就是說，跟list容器一樣，set和multiset容器的操作要么成功，要么對(duì)原有容器沒有影響。
4 運(yùn)行時(shí)指定排序法則
通常情況下，我們是在定義容器時(shí)指定排序法則，就像下面形式：
std::set<int, greater<int> > col1;
或者
std::set<int> col1; //use default sorting criterion less<>
然而，如果你需要在運(yùn)行時(shí)動(dòng)態(tài)指定容器的排序法則，或者你希望對(duì)于相同的容器類型卻有著不同的排序法則，那么就要做一些特殊處理。下面我們看一個(gè)例子：
#include <iostream>
#include <set>
#include "print.hpp"
using namespace std;
template <typename T>
class RuntimeCmp
{
public:
enum cmp_mode {normal, reverse};
private:
cmp_mode mode;
public:
RuntimeCmp(cmp_mode m = normal) : mode(m) {}
bool operator() (const T& t1, const T& t2)
{
return mode == normal ? t1 < t2 : t1 > t2;
}
bool operator== (const T& rhv)
{
return mode == rhv.mode;
}
};
typedef set<int, RuntimeCmp<int> > IntSet;
//pre-declare
void fill(IntSet& col1);
int main()
{
IntSet col1;
fill(col1);
PRINT_ELEMENTS(col1, "col1: ");
RuntimeCmp<int> reverse_cmp(RuntimeCmp<int>::reverse);
IntSet col2(reverse_cmp);
fill(col2);
PRINT_ELEMENTS(col2, "col2: ");
if (col1 == col2)
{
cout << "col1 and col2 is equal" <<endl;
}
else
{
if (col1 < col2)
{
cout << "col1 is less than col2" << endl;
}
else
{
cout << "col1 is greater than col2" << endl;
}
}
return 0;
}
void fill(IntSet& col1)
{
col1.insert(2);
col1.insert(3);
col1.insert(6);
col1.insert(5);
col1.insert(1);
col1.insert(4);
}
運(yùn)行結(jié)果如下：
col1 1 2 3 4 5 6
col2 6 5 4 3 2 1
col1 is less than col2
這里例子中，col1和col2有著相同的類型：set<int,
RuntimeCmp<int>
>，但是它們的排序法則卻不相同，一個(gè)升序，一個(gè)降序。這都是通過自定義的函數(shù)對(duì)象來實(shí)現(xiàn)的，所以函數(shù)對(duì)象比普通函數(shù)有著更加靈活與強(qiáng)大的控制，可
以滿足一些特殊的需求。