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)大的控制，可 以滿足一些特殊的需求。

  眾所周知，Linux動(dòng)態(tài)庫的默認(rèn)搜索路徑是/lib和/usr/lib。動(dòng)態(tài)庫被創(chuàng)建后，一般都復(fù)制到這兩個(gè)目錄中。當(dāng)程序執(zhí)行時(shí)需要某動(dòng)態(tài)庫，并且該動(dòng)態(tài)庫還未加載到內(nèi)存中，則系統(tǒng)會(huì)自動(dòng)到這兩個(gè)默認(rèn)搜索路徑中去查找相應(yīng)的動(dòng)態(tài)庫文件，然后加載該文件到內(nèi)存中，這樣程序就可以使用該動(dòng)態(tài)庫中的函數(shù)，以及該動(dòng)態(tài)庫的其它資源了。在Linux 中，動(dòng)態(tài)庫的搜索路徑除了默認(rèn)的搜索路徑外，還可以通過以下三種方法來指定。

方法一：在配置文件/etc/ld.so.conf中指定動(dòng)態(tài)庫搜索路徑。

可以通過編輯配置文件/etc/ld.so.conf來指定動(dòng)態(tài)庫的搜索路徑，該文件中每行為一個(gè)動(dòng)態(tài)庫搜索路徑。每次編輯完該文件后，都必須運(yùn)行命令ldconfig使修改后的配置生效。我們通過例1來說明該方法。

例1：

我們通過以下命令用源程序pos_conf.c（見程序1）來創(chuàng)建動(dòng)態(tài)庫 libpos.so，詳細(xì)創(chuàng)建過程請(qǐng)參考文[1]。

# gcc -c pos_conf.c
      # gcc -shared -fPCI -o libpos.so pos_conf.o
      #

#include <stdio.h>
      void pos()
      {
          printf("/root/test/conf/lib\n");

}

接著通過以下命令編譯main.c（見程序2）生成目標(biāo)程序pos。

# gcc -o pos main.c -L. -lpos
      #

void pos();
      int main()
      {
          pos();
               return 0;
      }

程序2: main.c

然后把庫文件移動(dòng)到目錄/root/test/conf/lib中。

# mkdir -p /root/test/conf/lib
      # mv libpos.so /root/test/conf/lib
      #

最后編輯配置文件/etc/ld.so.conf，在該文件中追加一行"/root/test/conf/lib"。

運(yùn)行程序pos試試。

# ./pos
        ./pos: error while loading shared libraries: libpos.so: cannot open shared object file: No such file or directory
      #

出錯(cuò)了，系統(tǒng)未找到動(dòng)態(tài)庫libpos.so。找找原因，原來在編輯完配置文件/etc/ld.so.conf后，沒有運(yùn)行命令ldconfig，所以剛才的修改還未生效。我們運(yùn)行l(wèi)dconfig后再試試。

# ldconfig
      # ./pos     /root/test/conf/lib
      #

程序pos運(yùn)行成功，并且打印出正確結(jié)果。

方法二：通過環(huán)境變量LD_LIBRARY_PATH指定動(dòng)態(tài)庫搜索路徑（！）。

通過設(shè)定環(huán)境變量LD_LIBRARY_PATH也可以指定動(dòng)態(tài)庫搜索路徑。當(dāng)通過該環(huán)境變量指定多個(gè)動(dòng)態(tài)庫搜索路徑時(shí)，路徑之間用冒號(hào)"："分隔。

    不過LD_LIBRARY_PATH的設(shè)定作用是全局的，過多的使用可能會(huì)影響到其他應(yīng)用程序的運(yùn)行，所以多用在調(diào)試。（LD_LIBRARY_PATH的缺陷和使用準(zhǔn)則，可以參考《Why LD_LIBRARY_PATH is bad》）。通常情況下推薦還是使用gcc的-R或-rpath選項(xiàng)來在編譯時(shí)就指定庫的查找路徑，并且該庫的路徑信息保存在可執(zhí)行文件中，運(yùn)行時(shí)它會(huì)直接到該路徑查找?guī)欤苊饬耸褂肔D_LIBRARY_PATH環(huán)境變量查找。

下面通過例2來說明本方法。

例2：

我們通過以下命令用源程序pos_env.c（見程序3）來創(chuàng)建動(dòng)態(tài)庫libpos.so。

# gcc -c pos_env.c
      # gcc -shared -fPCI -o libpos.so pos_env.o
      #

#include <stdio.h>
          void pos()
          {
                printf("/root/test/env/lib\n");
          }
      程序3: pos_env.c

測(cè)試用的可執(zhí)行文件pos可以使用例1中的得到的目標(biāo)程序pos，不需要再次編譯。因?yàn)閜os_conf.c中的函數(shù)pos和pos_env.c中的函數(shù)pos 函數(shù)原型一致，且動(dòng)態(tài)庫名相同，這就好比修改動(dòng)態(tài)庫pos后重新創(chuàng)建該庫一樣。這也是使用動(dòng)態(tài)庫的優(yōu)點(diǎn)之一。

然后把動(dòng)態(tài)庫libpos.so移動(dòng)到目錄/root/test/conf/lib中。

# mkdir -p /root/test/env/lib
      # mv libpos.so /root/test/env/lib
      #

我們可以使用export來設(shè)置該環(huán)境變量，在設(shè)置該環(huán)境變量后所有的命令中，該環(huán)境變量都有效。

例如：

# export LD_LIBRARY_PATH=/root/test/env/lib
      #

但本文為了舉例方便，使用另一種設(shè)置環(huán)境變量的方法，既在命令前加環(huán)境變量設(shè)置，該環(huán)境變量只對(duì)該命令有效，當(dāng)該命令執(zhí)行完成后，該環(huán)境變量就無效了。如下述命令：

# LD_LIBRARY_PATH=/root/test/env/lib ./pos  /root/test/env/lib
      #

程序pos運(yùn)行成功，并且打印的結(jié)果是"/root/test/env/lib"，正是程序pos_env.c中的函數(shù)pos的運(yùn)行結(jié)果。因此程序pos搜索到的動(dòng)態(tài)庫是/root/test/env/lib/libpos.so。

方法三：在編譯目標(biāo)代碼時(shí)指定該程序的動(dòng)態(tài)庫搜索路徑。

還可以在編譯目標(biāo)代碼時(shí)指定程序的動(dòng)態(tài)庫搜索路徑。這是通過gcc 的參數(shù)"-Wl,-rpath,"指定（如例3所示）。當(dāng)指定多個(gè)動(dòng)態(tài)庫搜索路徑時(shí)，路徑之間用冒號(hào)"："分隔。

例3：

我們通過以下命令用源程序pos.c（見程序4）來創(chuàng)建動(dòng)態(tài)庫libpos.so。

# gcc -c pos.c
      # gcc -shared -fPCI -o libpos.so pos.o
      #

#include <stdio.h>
      void pos()
      {
                printf("./\n");
      }

因?yàn)槲覀冃枰诰幾g目標(biāo)代碼時(shí)指定可執(zhí)行文件的動(dòng)態(tài)庫搜索路徑，所以需要用gcc命令重新編譯源程序main.c(見程序2)來生成可執(zhí)行文件pos。

# gcc -o pos main.c -L. -lpos -Wl,-rpath,./
      #

再運(yùn)行程序pos試試。

# ./pos   ./
      #

程序pos運(yùn)行成功，輸出的結(jié)果正是pos.c中的函數(shù)pos的運(yùn)行結(jié)果。因此程序pos搜索到的動(dòng)態(tài)庫是./libpos.so。

以上介紹了三種指定動(dòng)態(tài)庫搜索路徑的方法，加上默認(rèn)的動(dòng)態(tài)庫搜索路徑/lib和/usr/lib，共五種動(dòng)態(tài)庫的搜索路徑，那么它們搜索的先后順序是什么呢？

在 介紹上述三種方法時(shí)，分別創(chuàng)建了動(dòng)態(tài)庫./libpos.so、 /root/test/env/lib/libpos.so和/root/test/conf/lib/libpos.so。我們?cè)儆迷闯绦? pos_lib.c（見程序5）來創(chuàng)建動(dòng)態(tài)庫/lib/libpos.so，用源程序pos_usrlib.c（見程序6）來創(chuàng)建動(dòng)態(tài)庫 /usr/lib/libpos.so。

#include <stdio.h>
      void pos()
      {
                   printf("/lib\n");
      }

#include <stdio.h>
      void pos()
      {
                 printf("/usr/lib\n");
      }

這樣我們得到五個(gè)動(dòng)態(tài)庫libpos.so，這些動(dòng)態(tài)庫的名字相同，且都包含相同函數(shù)原型的公用函數(shù)pos。但存儲(chǔ)的位置不同和公用函數(shù)pos 打印的結(jié)果不同。每個(gè)動(dòng)態(tài)庫中的公用函數(shù)pos都輸出該動(dòng)態(tài)庫所存放的位置。這樣我們可以通過執(zhí)行例3中的可執(zhí)行文件pos得到的結(jié)果不同獲知其搜索到了哪個(gè)動(dòng)態(tài)庫，從而獲得第1個(gè)動(dòng)態(tài)庫搜索順序，然后刪除該動(dòng)態(tài)庫，再執(zhí)行程序pos，獲得第2個(gè)動(dòng)態(tài)庫搜索路徑，再刪除第2個(gè)被搜索到的動(dòng)態(tài)庫，如此往復(fù)，將可得到Linux搜索動(dòng)態(tài)庫的先后順序。程序pos執(zhí)行的輸出結(jié)果和搜索到的動(dòng)態(tài)庫的對(duì)應(yīng)關(guān)系如表1所示：

程序pos輸出結(jié)果	使用的動(dòng)態(tài)庫	對(duì)應(yīng)的動(dòng)態(tài)庫搜索路徑指定方式
./	./libpos.so	編譯目標(biāo)代碼時(shí)指定的動(dòng)態(tài)庫搜索路徑
/root/test/env/lib	/root/test/env/lib/libpos.so	環(huán)境變量LD_LIBRARY_PATH指定的動(dòng)態(tài)庫搜索路徑
/root/test/conf/lib	/root/test/conf/lib/libpos.so	配置文件/etc/ld.so.conf中指定的動(dòng)態(tài)庫搜索路徑
/lib	/lib/libpos.so	默認(rèn)的動(dòng)態(tài)庫搜索路徑/lib
/usr/lib	/usr/lib/libpos.so	默認(rèn)的動(dòng)態(tài)庫搜索路徑/usr/lib

表1: 程序pos輸出結(jié)果和動(dòng)態(tài)庫的對(duì)應(yīng)關(guān)系

創(chuàng)建各個(gè)動(dòng)態(tài)庫，并放置在相應(yīng)的目錄中。測(cè)試環(huán)境就準(zhǔn)備好了。執(zhí)行程序pos，并在該命令行中設(shè)置環(huán)境變量LD_LIBRARY_PATH。

# LD_LIBRARY_PATH=/root/test/env/lib ./pos  ./
      #

根據(jù)程序pos的輸出結(jié)果可知，最先搜索的是編譯目標(biāo)代碼時(shí)指定的動(dòng)態(tài)庫搜索路徑。然后我們把動(dòng)態(tài)庫./libpos.so刪除了，再運(yùn)行上述命令試試。

# rm libpos.so
        rm: remove regular file `libpos.so'? y
      # LD_LIBRARY_PATH=/root/test/env/lib ./pos /root/test/env/lib
      #

根據(jù)程序pos的輸出結(jié)果可知，第2個(gè)動(dòng)態(tài)庫搜索的路徑是環(huán)境變量LD_LIBRARY_PATH指定的。我們?cè)侔?root/test/env/lib/libpos.so刪除，運(yùn)行上述命令。

# rm /root/test/env/lib/libpos.so
        rm: remove regular file `/root/test/env/lib/libpos.so'? y
      # LD_LIBRARY_PATH=/root/test/env/lib ./pos  /root/test/conf/lib
      #

第3個(gè)動(dòng)態(tài)庫的搜索路徑是配置文件/etc/ld.so.conf指定的路徑。刪除動(dòng)態(tài)庫/root/test/conf/lib/libpos.so后再運(yùn)行上述命令。

# rm /root/test/conf/lib/libpos.so
        rm: remove regular file `/root/test/conf/lib/libpos.so'? y
      # LD_LIBRARY_PATH=/root/test/env/lib ./pos  /lib
      #

第4個(gè)動(dòng)態(tài)庫的搜索路徑是默認(rèn)搜索路徑/lib。我們?cè)賱h除動(dòng)態(tài)庫/lib/libpos.so，運(yùn)行上述命令。

# rm /lib/libpos.so
        rm: remove regular file `/lib/libpos.so'? y
      # LD_LIBRARY_PATH=/root/test/env/lib ./pos  /usr/lib
      #

最后的動(dòng)態(tài)庫搜索路徑是默認(rèn)搜索路徑/usr/lib。

綜合以上結(jié)果可知，動(dòng)態(tài)庫的搜索路徑搜索的先后順序是：

1.編譯目標(biāo)代碼時(shí)指定的動(dòng)態(tài)庫搜索路徑；

2.環(huán)境變量LD_LIBRARY_PATH指定的動(dòng)態(tài)庫搜索路徑；

3.配置文件/etc/ld.so.conf中指定的動(dòng)態(tài)庫搜索路徑；

4.默認(rèn)的動(dòng)態(tài)庫搜索路徑/lib；

5.默認(rèn)的動(dòng)態(tài)庫搜索路徑/usr/lib。

在上述1、2、3指定動(dòng)態(tài)庫搜索路徑時(shí)，都可指定多個(gè)動(dòng)態(tài)庫搜索路徑，其搜索的先后順序是按指定路徑的先后順序搜索的。對(duì)此本文不再舉例說明，有興趣的讀者可以參照本文的方法驗(yàn)證。