C++ STL——set和multiset

目录

• 一 set和multiset
• 二 对组pair

---

注：原创不易，转载请务必注明原作者和出处，感谢支持！

注：内容来自某培训课程，不一定完全正确！

一 set和multiset

set和multiset的特性是所有元素会根据元素的值自动进行排序。set和multiset以红黑树（平衡二叉树的一种）为底层机制。其查找效率非常好。set容器中不允许重复的元素，multiset则允许重复元素存在。

构造函数

set<T> st;              // 默认构造函数
multiset<T> mst;        // multiset默认构造函数
set(const set &st);     // 拷贝构造函数

赋值操作

set &operator=(const set &st);  // 重载等号运算符
swap(st);                       // 交换两个集合容器中的元素

大小操作

size();     // 返回容器中元素的数目
empty();    // 判断容器是否为空

插入和删除

insert(elem);       // 在容器中插入元素
clear();            // 清空所有元素
erase(pos);         // 删除pos迭代器所指的元素，返回下一个元素的迭代器
erase(beg, end);    // 删除区间[beg, end)的所有元素
erase(elem);        // 删除容器中值为elem的元素

查找操作

find(key);              // 查找键key是否存在，若存在，返回该元素的迭代器；若不存在，则返回map.end()
lower_bound(keyElem);   // 返回第一个key>=keyElem元素的迭代器
upper_bound(keyElem);   // 返回第一个key>keyElem元素的迭代器
equal_range(keyElem);   // 返回容器中key和keyElem相等的上下限的两个迭代器

下面是set和multiset的应用案例。

void printSet(set<int> &v)
{
    decltype(v.begin()) it;
    for (it = v.begin(); it != v.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;
}

void printMultiset(multiset<int> &mst)
{
    decltype(mst.begin()) it;
    for (it = mst.begin(); it != mst.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;
}

void Test1()
{
    // 初始化
    set<int> s1;
    s1.insert(7);
    s1.insert(2);
    s1.insert(4);
    s1.insert(5);
    s1.insert(1);
    printSet(s1);

    // 赋值
    set<int> s2 = s1;
    printSet(s2);

    set<int> s3;
    s3.swap(s1);
    printSet(s1);
    printSet(s3);

    // 删除
    s3.erase(s3.begin());
    printSet(s3);
    s3.erase(7);
    printSet(s3);

    // multiset
    multiset<int> mst;
    mst.insert(7);
    mst.insert(6);
    mst.insert(9);
    mst.insert(1);
    mst.insert(6);
    cout << "mst = " << endl;
    decltype(mst.begin()) it;
    for (it = mst.begin(); it != mst.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;

    // 查找
    set<int> st;
    for (int i = 1; i <= 10; ++i)
    {
        st.insert(i * 10);
    }
    printSet(st);

    set<int>::iterator itlow, itup;
    // 第一个key >= 30的元素的迭代器
    itlow = st.lower_bound(30);
    // 第一个key > 60的元素的迭代器
    itup = st.upper_bound(60);
    cout << "*itlow = " << *itlow << endl;
    cout << "*itup = " << *itup << endl;
    st.erase(itlow, itup);
    printSet(st);

    // equal_range()
    multiset<int> s;
    s.insert(10);
    s.insert(20);
    s.insert(20);
    s.insert(20);
    s.insert(30);
    s.insert(40);
    printMultiset(s);

    pair<decltype(s.begin()), decltype(s.begin())> iteq;
    iteq = s.equal_range(20);
    cout << "*iteq.first = " << *iteq.first << endl;
    cout << "*iteq.second = " << *iteq.second << endl;
    s.erase(iteq.first, iteq.second);
    printMultiset(s);
}

使用仿函数更改set容器的默认排序方式
在上面的案例中，我们知道set容器默认是对int数据从小到大进行排序的。那么怎样才能让set从大到小排序呢？请看下面的例子。

// 仿函数
class MyCompare
{
public:
    bool operator() (int v1, int v2)
    {
        return v1 > v2;
    }
};

// 从大到小排序
void Test2()
{
    set<int, MyCompare> s1;
    s1.insert(7);
    s1.insert(2);
    s1.insert(4);
    s1.insert(5);
    s1.insert(1);
    decltype(s1.begin()) it;
    for (it = s1.begin(); it != s1.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;
}

set容器当中如何放置对象
如果你直接这样写的话是不行的！

class Person
{
public:
    Person(int id, int age) : id(id), age(age) {}
public:
    int id;
    int age;
};

void Test3()
{
    // 会报错！因为set内部是需要排序的，当你往set里放置对象时，
    // set是不知道如何对对象进行排序的。这与基础数据类型不同
    set<Person> sp;
    Person p1(1000, 20);
    Person p2(1001, 21);
    Person p3(1002, 22);
    sp.insert(p1);
    sp.insert(p2);
    sp.insert(p3);
}

那这个问题如何解决？使用仿函数！如下所示。

class cmp
{
public:
    bool operator() (const Person &p1, const Person &p2)
    {
        // 根据ID从小到大排序
        return p1.id < p2.id;
    }
};

void Test3()
{
    // 会报错！因为set内部是需要排序的，当你往set里放置对象时，
    // set是不知道如何对对象进行排序的。这与基础数据类型不同
    // set<Person> sp;

    // 正确的写法
    set<Person, cmp> sp;
    Person p1(1000, 23);
    Person p2(1001, 26);
    Person p3(1002, 22);
    sp.insert(p1);
    sp.insert(p2);
    sp.insert(p3);

    decltype(sp.begin()) it;
    for (it = sp.begin(); it != sp.end(); ++it)
    {
        cout << "id = " << it->id << " " << "age = " << it->age << endl;
    }

    // 务必注意：因为仿函数cmp里只对Person的ID进行比较
    // 所以在下面的案例中，在sp中查找p4，结果理应是p4不在
    // sp中的。但是，因为cmp直对Person的ID进行比较，所以
    // 下面案例的实际输出是p4在sp中！,因为p4的ID和p3的ID
    // 相同。所以，it返回的实际上是p3的迭代器！！！！！！
    Person p4(1002, 29);
    it = sp.find(p4);
    if (it != sp.end())
    {
        cout << "p4在sp中！" << endl;
        cout << "id = " << it->id << " " << "age = " << it->age << endl;
    }
    else
    {
        cout << "p4不在sp中！" << endl;
    }
}

务必注意上面案例中的查找的注意事项！

二 对组pair

对组（pair）将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用pair的两个公有函数first和second访问。

创建对组

// 方法一
pair<string, int> p1(string("name"), 20);
cout << p1.first << endl;
cout << p1.second << endl;

// 方法二
pair<string, int> p2 = make_pair("name", 20);
cout << p2.first << endl;
cout << p2.second << endl;

// 对组的赋值
pair<string, int> p3 = p2;
cout << p3.first << endl;
cout << p3.second << endl;