C++ 标准模板库 STL（1）set 与 multiset

一、简介

        set与multiset容器能够快速查找键，键是存储在一维容器中的值，二者的区别在于前者不能够存储重复的键值，后者能够存储重复键值。

        set与multiset内部结构类似于二叉树，并且被插入到set与multiset容器中的元素会默认进行排序，从而提高查找速度。这意味着set与multiset不能够像vector那样可以使用其他元素替换给定位置的元素。

二、基本操作

2.1 头文件

#include <set>

2.2 初始化

// 初始化int类型的 set 和 multiset
std::set<int> setInts;
std::multiset<int> msetInts;

// 声明指向 set 和 multiset 的迭代器
std::set<int>::iterator element;
std::set<int>::const_iterator element; // const 无法修改值

std::multiset<int>::iterator element;
std::multiset<int>::const_iterator element; // const 无法修改值

        如果没有指定排序标准，set和multiset将默认使用std::less进行排序，即升序排序。倘若想要按照降序排序，可以使用std::greater初始化。

#include <functional>

// 默认升序排列, 例如 1, 2, 3, 4, 5
std::set<int> setInts;

// 降序排列, 例如 5, 4, 3, 2, 1
std::set<int, std::greater<int>> setInts;

        除了使用标准库提供的函数，还可以自定义比较函数。

template <typename T>
struct MyCompare {
    bool operator()(const T& a, const T& b) const {
        return a > b;
    }
};

std::set<int, MyCompare<int>> setInts;
std::multiset<int, MyCompare<int>> setInts;

2.3 插入元素

        使用insert()函数能够向两种容器插入元素，这个函数接受要插入的值或者容器的指定范围。

setInts.insert(-1);
msetInts.insert(setInts.begin(), setInts.end());

        对于multiset容器，可以使用其成员函数count来计数容器中包含了多少个该元素值。

// 计数容器中有多少个-1
msetInts.count(-1);

2.4 查找元素

        使用find()函数能够根据给定的键来查找值。对于multiset，find()函数查找第一个与给定键匹配的元素。

// 查找-1元素是否在set中
auto elementFound = setInts.find(-1);

// 判断是否找到元素
if(elementFound != setInts.end()) {
    cout << *elementFound << endl;
} else {
    cout << "Not Found!" << endl;
}

2.5 删除元素

        使用erase()能够删除给定的键值，该函数还可以接受迭代器变量或者使用迭代器指定的边界，如果使用迭代器边界删除键值，那么该范围内的所有元素都将从容器中删除。

// 删除-1元素
setInts.erase(-1);

// 查找-1并删除
auto element = setInts.find(-1);
setInts.erase(element);

// 删除setInts的所有元素
setInts.erase(setInts.begin(), setInts.end());

        对于multiset容器，erase()将删除所有与键值相同的元素。

#include <set>
#include <iostream>

using namespace std;

template <typename T>
void DisplayContents (const T& Input) {
    for(auto e = Input.cbegin(); e != Input.cend(); e++) {
        cout << *e << " ";
    }
    cout << endl;
}

int main() {
    multiset<int> msetInts{43, 78, 78, -1, 124};

    // 输出当前所有元素
    cout << msetInts.size() << endl;
    DisplayContents(msetInts);

    // 删除78
    cout << msetInts.count(78) << endl;
    msetInts.erase(78);

    // 输出当前所有元素
    cout << msetInts.size() << endl;
    DisplayContents(msetInts);

    return 0;
}

        上面的代码输出内容如下：

5
-1 43 78 78 124
2
3
-1 43 124

三、优缺点

        对于需要频繁查找的程序来说，set和multiset很有优势，因为其内容是经过排序的，因此查找速度要快很多。但这为插入元素带来额外的开销。所以在需要频繁插入而很少查找的情况下，应当尽可能使用std::vector和std::list，而不是std::set和std::multiset。

        set和multiset使用find()查找到元素后无法像vector一样直接使用迭代器对元素值进行修改，因为这样会打乱元素的排序顺序。