1 set和multiset容器的能力
set 和multiset容器的内部结构通常由平衡二叉树(balanced binary tree)来实现。当元素放入容器中时，会按照一定的排序法则自动排序，默认是按照less<>排序规则来排序。这种自动排序的特性加速了元 素查找的过程，但是也带来了一个问题：不可以直接修改set或multiset容器中的元素值，因为这样做就可能违反了元素自动排序的规则。如果你希望修 改一个元素的值，必须先删除原有的元素，再插入新的元素。

2 set和multiset容器的操作
Constructor and Destructor

• set c: 创建一个空的set或multiset容器
• set c(op): 创建一个空的使用op作为排序法则的set或multiset容器
• set c1(c2): 创建一个已存在的set或multiset容器的复制品，容器的类型和所有元素一同复制
• set c(beg, end): 创建一个set或multiset容器，并且以[beg, end)范围中的元素进行初始化
• set c(beg, end, op): 创建一个使用op作为排序法则的set或multiset容器，并且以[beg, end)范围中的元素进行初始化
• c.~set(): 容器的析构函数，销毁所有的元素，释放所有的分配内存

上面的set可以是下面几种形式：

• set<type>: 以less<>为排序法则的set
• set<type, op>: 以op为排序法则的set
• multiset<type>: 以less<>为排序法则的multiset
• multiset<type, op>: 以op为排序法则的multiset

从上面我们可以看到，可以从两个地方来指定排序法则：

（1）作为模板参数

例如：std::set<int, greater<int> > col1;

这种情况下，排序法则本身作为容器类型的一部分。对于一个set或者multiset容器，只有当元素类型和排序法则类型都相同时，他们的类型才被认为相同，否则就是不同类型的容器。

（2）作为构造函数参数
例如：std::set<int> col1(greater<int>);

这种情况下指定的排序法则不作为容器类型的一部分，你可以为相同类型的容器指定不同的排序规则。这通常应用于要求相同的容器类型，但排序规则可以不同的场合。

Size and Comparing
set 和multiset容器同样提供size(), empty(), max_size()三个关于查询元素数目的接口，提供==, !=, <, <=, >, >=等比较操作符。但值得注意的是比较操作符只针对相同类型的容器，元素类型和排序法则类型都必须相同。

Special Search Operations
set和multiset容器的内部结构对于元素的查找提供了优化空间，所以它们提供了一些特殊的查找接口，这些查找操作通常要比同名的通用算法高效，所以在相同的条件下应该优先使用这些接口。

• count(val): 返回容器中值等于val的元素数目。
• find(val): 返回容器中值等于val的第一个元素的iterator位置；如果没有匹配元素，则返回end()位置。
• lower_bound(val): 返回容器中第一个值大于或等于val的元素的iterator位置。
• upper_bound(val): 返回容器中第一个值大于val的元素的iterator位置。
• equal_range(val): 返回容器中值等于val的所有元素的范围[beg, end)组成的pair<beg, end> 。

下面我们看一个使用lower_bound(), upper_bound和equal_range(val)例子，以加深对它们的理解：

#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;

}

执行结果如下：

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的所有元素复制到c1中，同时c1原有的元素被销毁。
• c1.swap(c2): 交换c1和c2的元素。
• swap(c1, c2): 同上，只不过这是一个通用算法。

需要注意的是两个容器的类型要一致（包括元素类型和排序法则类型）。

Inserting and Removing Elements
set和multiset容器的插入和删除元素接口跟其他容器也非常类似，但在细节上却存在差别。

• c.insert(elem): 在容器中插入元素elem的一份拷贝，并返回新元素的iterator位置；如果是set容器，同时还返回是否插入成功的标志。
• c.insert(pos, elem): 在容器中插入元素elem的一份拷贝，并返回新元素的iterator位置；因为set和multiset容器的元素是自动排序的，所以pos位置只是插入位置的一个提示，设置恰当的话，可以提高插入元素的效率。
• c.insert(beg, end): 在容器中插入[beg, end)范围中所有元素的拷贝，没有返回值。
• c.erase(val): 删除容器中所有值为val的元素，返回删除元素的数目。
• c.erase(pos): 删除容器中位置pos处的元素，没有返回值。
• c.erase(beg, end): 删除容器中[ben, end)范围内所有的元素，没有返回值。
• c.clear(): 删除容器中所有元素，使容器成为空容器。

其中我们重点说一下c.insert(elem)接口。

对于set容器，它的定义如下：

pair<iterator, bool> insert(const TYPE& val);

而对于multiset容器，它的定义如下：

iterator insert(const TYPE& val);

它 们的不同就是set容器的insert接口返回的是一个pair<iterator, bool>，而multiset容器的insert接口直接返回一个iterator。这是因为set容器中不允许有重复的元素，如果容器中已经存 在一个跟插入值相同的元素，那么插入操作就会失败，而pair中的bool值就是标识插入是否成功的。而multiset不存在这个问题。

3 set和multiset容器的异常处理

因为set和multiset容器的独特内部结构，当发生异常时，也可以把影响减到最小。也就是说，跟list容器一样，set和multiset容器的操作要么成功，要么对原有容器没有影响。

4 运行时指定排序法则

通常情况下，我们是在定义容器时指定排序法则，就像下面形式：

std::set<int, greater<int> > col1;

或者

std::set<int> col1;    //use default sorting criterion less<>

然而，如果你需要在运行时动态指定容器的排序法则，或者你希望对于相同的容器类型却有着不同的排序法则，那么就要做一些特殊处理。下面我们看一个例子：

#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);

}

运行结果如下：

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> >，但是它们的排序法则却不相同，一个升序，一个降序。这都是通过自定义的函数对象来实现的，所以函数对象比普通函数有着更加灵活与强大的控制，可 以满足一些特殊的需求。

  众所周知，Linux动态库的默认搜索路径是/lib和/usr/lib。动态库被创建后，一般都复制到这两个目录中。当程序执行时需要某动态库，并且该动态库还未加载到内存中，则系统会自动到这两个默认搜索路径中去查找相应的动态库文件，然后加载该文件到内存中，这样程序就可以使用该动态库中的函数，以及该动态库的其它资源了。在Linux 中，动态库的搜索路径除了默认的搜索路径外，还可以通过以下三种方法来指定。

方法一：在配置文件/etc/ld.so.conf中指定动态库搜索路径。

可以通过编辑配置文件/etc/ld.so.conf来指定动态库的搜索路径，该文件中每行为一个动态库搜索路径。每次编辑完该文件后，都必须运行命令ldconfig使修改后的配置生效。我们通过例1来说明该方法。

例1：

我们通过以下命令用源程序pos_conf.c（见程序1）来创建动态库 libpos.so，详细创建过程请参考文[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）生成目标程序pos。

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

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

程序2: main.c

然后把库文件移动到目录/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"。

运行程序pos试试。

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

出错了，系统未找到动态库libpos.so。找找原因，原来在编辑完配置文件/etc/ld.so.conf后，没有运行命令ldconfig，所以刚才的修改还未生效。我们运行ldconfig后再试试。

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

程序pos运行成功，并且打印出正确结果。

方法二：通过环境变量LD_LIBRARY_PATH指定动态库搜索路径（！）。

通过设定环境变量LD_LIBRARY_PATH也可以指定动态库搜索路径。当通过该环境变量指定多个动态库搜索路径时，路径之间用冒号"："分隔。

    不过LD_LIBRARY_PATH的设定作用是全局的，过多的使用可能会影响到其他应用程序的运行，所以多用在调试。（LD_LIBRARY_PATH的缺陷和使用准则，可以参考《Why LD_LIBRARY_PATH is bad》）。通常情况下推荐还是使用gcc的-R或-rpath选项来在编译时就指定库的查找路径，并且该库的路径信息保存在可执行文件中，运行时它会直接到该路径查找库，避免了使用LD_LIBRARY_PATH环境变量查找。

下面通过例2来说明本方法。

例2：

我们通过以下命令用源程序pos_env.c（见程序3）来创建动态库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

测试用的可执行文件pos可以使用例1中的得到的目标程序pos，不需要再次编译。因为pos_conf.c中的函数pos和pos_env.c中的函数pos 函数原型一致，且动态库名相同，这就好比修改动态库pos后重新创建该库一样。这也是使用动态库的优点之一。

然后把动态库libpos.so移动到目录/root/test/conf/lib中。

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

我们可以使用export来设置该环境变量，在设置该环境变量后所有的命令中，该环境变量都有效。

例如：

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

但本文为了举例方便，使用另一种设置环境变量的方法，既在命令前加环境变量设置，该环境变量只对该命令有效，当该命令执行完成后，该环境变量就无效了。如下述命令：

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

程序pos运行成功，并且打印的结果是"/root/test/env/lib"，正是程序pos_env.c中的函数pos的运行结果。因此程序pos搜索到的动态库是/root/test/env/lib/libpos.so。

方法三：在编译目标代码时指定该程序的动态库搜索路径。

还可以在编译目标代码时指定程序的动态库搜索路径。这是通过gcc 的参数"-Wl,-rpath,"指定（如例3所示）。当指定多个动态库搜索路径时，路径之间用冒号"："分隔。

例3：

我们通过以下命令用源程序pos.c（见程序4）来创建动态库libpos.so。

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

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

因为我们需要在编译目标代码时指定可执行文件的动态库搜索路径，所以需要用gcc命令重新编译源程序main.c(见程序2)来生成可执行文件pos。

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

再运行程序pos试试。

# ./pos   ./
      #

程序pos运行成功，输出的结果正是pos.c中的函数pos的运行结果。因此程序pos搜索到的动态库是./libpos.so。

以上介绍了三种指定动态库搜索路径的方法，加上默认的动态库搜索路径/lib和/usr/lib，共五种动态库的搜索路径，那么它们搜索的先后顺序是什么呢？

在 介绍上述三种方法时，分别创建了动态库./libpos.so、 /root/test/env/lib/libpos.so和/root/test/conf/lib/libpos.so。我们再用源程序 pos_lib.c（见程序5）来创建动态库/lib/libpos.so，用源程序pos_usrlib.c（见程序6）来创建动态库 /usr/lib/libpos.so。

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

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

这样我们得到五个动态库libpos.so，这些动态库的名字相同，且都包含相同函数原型的公用函数pos。但存储的位置不同和公用函数pos 打印的结果不同。每个动态库中的公用函数pos都输出该动态库所存放的位置。这样我们可以通过执行例3中的可执行文件pos得到的结果不同获知其搜索到了哪个动态库，从而获得第1个动态库搜索顺序，然后删除该动态库，再执行程序pos，获得第2个动态库搜索路径，再删除第2个被搜索到的动态库，如此往复，将可得到Linux搜索动态库的先后顺序。程序pos执行的输出结果和搜索到的动态库的对应关系如表1所示：

程序pos输出结果	使用的动态库	对应的动态库搜索路径指定方式
./	./libpos.so	编译目标代码时指定的动态库搜索路径
/root/test/env/lib	/root/test/env/lib/libpos.so	环境变量LD_LIBRARY_PATH指定的动态库搜索路径
/root/test/conf/lib	/root/test/conf/lib/libpos.so	配置文件/etc/ld.so.conf中指定的动态库搜索路径
/lib	/lib/libpos.so	默认的动态库搜索路径/lib
/usr/lib	/usr/lib/libpos.so	默认的动态库搜索路径/usr/lib

表1: 程序pos输出结果和动态库的对应关系

创建各个动态库，并放置在相应的目录中。测试环境就准备好了。执行程序pos，并在该命令行中设置环境变量LD_LIBRARY_PATH。

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

根据程序pos的输出结果可知，最先搜索的是编译目标代码时指定的动态库搜索路径。然后我们把动态库./libpos.so删除了，再运行上述命令试试。

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

根据程序pos的输出结果可知，第2个动态库搜索的路径是环境变量LD_LIBRARY_PATH指定的。我们再把/root/test/env/lib/libpos.so删除，运行上述命令。

# 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个动态库的搜索路径是配置文件/etc/ld.so.conf指定的路径。删除动态库/root/test/conf/lib/libpos.so后再运行上述命令。

# 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个动态库的搜索路径是默认搜索路径/lib。我们再删除动态库/lib/libpos.so，运行上述命令。

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

最后的动态库搜索路径是默认搜索路径/usr/lib。

综合以上结果可知，动态库的搜索路径搜索的先后顺序是：

1.编译目标代码时指定的动态库搜索路径；

2.环境变量LD_LIBRARY_PATH指定的动态库搜索路径；

3.配置文件/etc/ld.so.conf中指定的动态库搜索路径；

4.默认的动态库搜索路径/lib；

5.默认的动态库搜索路径/usr/lib。

在上述1、2、3指定动态库搜索路径时，都可指定多个动态库搜索路径，其搜索的先后顺序是按指定路径的先后顺序搜索的。对此本文不再举例说明，有兴趣的读者可以参照本文的方法验证。