首页 > 编程笔记

C++ set容器用法详解

set 是 C++ 标准库中提供的一个关联式容器，以红黑树作为其底层数据结构，因此插入数据时可以自动排序。同时，在排好序的红黑树中查找数据效率也非常高。

为了能在红黑树中存取数据，set 中的元素也分为键值和实值，但这两者之间不存在对应关系，set 中各个元素的键值和实值是相同的。

为了满足底层数据结构红黑树的要求，set 容器不得不将其元素分为键值和实值两部分，一定程度上导致了内存空间的浪费。因此选择使用 set 时，尽量使用那些占内存小的数据类型。

set容器的构造

在 C++ 标准库中，set 容器的定义如下：

template < class T, // set::key_type/value_type
           class Compare = less<T>, // set::key_compare/value_compare
           class Alloc = allocator<T> // set::allocator_type
         >class set;

在 set 容器中，键值和实值是一样的，它们的类型都是类模板实例化时的类型参数 T。

创建 set 容器的方法，常用的有以下 5 种。

1) 创建空的 set 容器。比如：

std::set<std::string> myset;

如果程序中已经默认指定了 std 命令空间，这里可以省略std::。

由此就创建好了一个 set 容器，该容器采用默认的 std::less<T> 排序规则，会对存储的 string 类型元素做升序排序。

注意，由于 set 容器支持随时向内部添加新的元素，因此创建空 set 容器的方法是经常使用的。

2) 除此之外，set 类模板还支持在创建 set 容器的同时，对其进行初始化。例如：

std::set<std::string> myset{"http://c.biancheng.net/java/",
                            "http://c.biancheng.net/stl/",
                            "http://c.biancheng.net/python/"};

由此即创建好了包含 3 个 string 元素的 myset 容器。由于其采用默认的 std::less<T> 规则，因此其内部存储 string 元素的顺序如下所示：

"http://c.biancheng.net/java/"
"http://c.biancheng.net/python/"
"http://c.biancheng.net/stl/"

3) set 类模板中还提供了拷贝（复制）构造函数，可以实现在创建新 set 容器的同时，将已有 set 容器中存储的所有元素全部复制到新 set 容器中。

例如，在第 2 种方式创建的 myset 容器的基础上，执行如下代码：

std::set<std::string> copyset(myset);
//等同于
//std::set<std::string> copyset = myset

该行代码在创建 copyset 容器的基础上，还会将 myset 容器中存储的所有元素，全部复制给 copyset 容器一份。

另外，C++ 11 标准还为 set 类模板新增了移动构造函数，其功能是实现创建新 set 容器的同时，利用临时的 set 容器为其初始化。比如：

set<string> retSet() {
    std::set<std::string> myset{ "http://c.biancheng.net/java/",
                            "http://c.biancheng.net/stl/",
                            "http://c.biancheng.net/python/" };
    return myset;
}
std::set<std::string> copyset(retSet());
//或者
//std::set<std::string> copyset = retSet();

注意，由于 retSet() 函数的返回值是一个临时 set 容器，因此在初始化 copyset 容器时，其内部调用的是 set 类模板中的移动构造函数，而非拷贝构造函数。

显然，无论是调用复制构造函数还是调用拷贝构造函数，都必须保证这 2 个容器的类型完全一致。

4) 在第 3 种方式的基础上，set 类模板还支持取已有 set 容器中的部分元素，来初始化新 set 容器。例如：

std::set<std::string> myset{ "http://c.biancheng.net/java/",
                    "http://c.biancheng.net/stl/",
                    "http://c.biancheng.net/python/" };
std::set<std::string> copyset(++myset.begin(), myset.end());

由此初始化的 copyset 容器，其内部仅存有如下 2 个 string 字符串：

"http://c.biancheng.net/python/"
"http://c.biancheng.net/stl/"

5) 以上几种方式创建的 set 容器，都采用了默认的std::less<T>规则。其实，借助 set 类模板定义中第 2 个参数，我们完全可以手动修改 set 容器中的排序规则。比如：

std::set<std::string,std::greater<string> > myset{
    "http://c.biancheng.net/java/",
    "http://c.biancheng.net/stl/",
    "http://c.biancheng.net/python/"};

通过选用 std::greater<string> 降序规则，myset 容器中元素的存储顺序为:

"http://c.biancheng.net/stl/"
"http://c.biancheng.net/python/"
"http://c.biancheng.net/java/"

以下是一个完整的 C++ 实例，包含上述 5 种创建 set 容器的方法：

#include <iostream>
#include <set>
#include <string>

// retSet函数应该在main函数之外定义
std::set<std::string> retSet() {
    return std::set<std::string>{
        "http://c.biancheng.net/java/",
            "http://c.biancheng.net/stl/",
            "http://c.biancheng.net/python/"
    };
}

int main() {
    // 1. 创建空的 set 容器
    std::set<std::string> emptySet;

    // 2. 初始化 set 容器
    std::set<std::string> myset{
        "http://c.biancheng.net/java/",
        "http://c.biancheng.net/stl/",
        "http://c.biancheng.net/python/"
    };
    for (const auto& url : myset) {
        std::cout << url << std::endl;
    }
    std::cout << "--------------------" << std::endl;

    // 3. 拷贝构造函数和移动构造函数
    std::set<std::string> copyset1(myset);
    for (const auto& url : copyset1) {
        std::cout << url << std::endl;
    }
    std::cout << "--------------------" << std::endl;

    std::set<std::string> copyset2(retSet());
    for (const auto& url : copyset2) {
        std::cout << url << std::endl;
    }
    std::cout << "--------------------" << std::endl;

    // 4. 使用部分已有 set 容器的元素初始化新 set 容器
    std::set<std::string> partialCopyset(++myset.begin(), myset.end());
    for (const auto& url : partialCopyset) {
        std::cout << url << std::endl;
    }
    std::cout << "--------------------" << std::endl;

    // 5. 手动修改 set 容器的排序规则
    std::set<std::string, std::greater<std::string>> customOrderSet{
        "http://c.biancheng.net/java/",
        "http://c.biancheng.net/stl/",
        "http://c.biancheng.net/python/"
    };
    for (const auto& url : customOrderSet) {
        std::cout << url << std::endl;
    }
    std::cout << "--------------------" << std::endl;

    return 0;
}

set容器的迭代器

正如前面已经提到过的，set 容器中的元素虽然也包含键值和实值，但是这两个值是相同的。因此，使用迭代器访问 set 容器的元素时，与 map 容器的迭代器有两个不同地方：

使用解引用运算符“*”取值，不用 first 和 second。
所有迭代器都是常量迭代器，不能用来修改所指元素。

因为键值和实值相同，所以在 set 元素中区分键值和实值就没有任何意义，因此也就不必使用 first 和 second 成员了。

以下是一个 set 容器的完整 C++ 实例，演示了如何使用迭代器遍历容器并访问元素：

#include <iostream>
#include <set>

int main() {
    // 初始化 set 容器
    std::set<int> numbers{3, 1, 4, 1, 5, 9, 2, 6, 5};

    // 使用迭代器遍历 set 容器
    for (std::set<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " ";  // 使用解引用运算符“*”来访问元素值
    }
    std::cout << std::endl;

    return 0;
}

另外，也是因为键值和实值相同，所以也不允许通过迭代器修改实值。因为修改实值，就意味着要修改键值，而修改键值则必然导致红黑树重新排序。如果程序中存在大量修改键值的操作，那么必将严重影响程序的效率。因此，set 容器禁止修改其元素的值。

#include <iostream>
#include <set>

int main() {
    // 初始化 set 容器
    std::set<int> numbers{ 3, 1, 4, 1, 5, 9, 2, 6, 5 };

    for (std::set<int>::iterator it = numbers.begin(); it != numbers.end(); ++it) {
        *it = *it * 2;  // 错误，尝试修改元素的值
    }

    return 0;
}

set容器的基本操作

set 容器的基本操作包括数据的增、删、查，以及判断容器是否为空、求元素个数、交换两个容器的内容、求指向容器头尾的迭代器等。

下表列出了 set 容器提供的常用成员方法以及各自的功能。

表 1 C++ set 容器常用成员方法
成员方法	功能
begin()	返回指向容器中第一个（注意，是已排好序的第一个）元素的双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
end()	返回指向容器最后一个元素（注意，是已排好序的最后一个）所在位置后一个位置的双向迭代器，通常和 begin() 结合使用。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
rbegin()	返回指向最后一个（注意，是已排好序的最后一个）元素的反向双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
rend()	返回指向第一个（注意，是已排好序的第一个）元素所在位置前一个位置的反向双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的反向双向迭代器。
cbegin()	和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
cend()	和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
crbegin()	和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
crend()	和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改容器内存储的元素值。
find(val)	在 set 容器中查找值为 val 的元素，如果成功找到，则返回指向该元素的双向迭代器；反之，则返回和 end() 方法一样的迭代器。另外，如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
lower_bound(val)	返回一个指向当前 set 容器中第一个大于或等于 val 的元素的双向迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
upper_bound(val)	返回一个指向当前 set 容器中第一个大于 val 的元素的迭代器。如果 set 容器用 const 限定，则该方法返回的是 const 类型的双向迭代器。
equal_range(val)	该方法返回一个 pair 对象（包含 2 个双向迭代器），其中 pair.first 和 lower_bound() 方法的返回值等价，pair.second 和 upper_bound() 方法的返回值等价。也就是说，该方法将返回一个范围，该范围中包含的值为 val 的元素（set 容器中各个元素是唯一的，因此该范围最多包含一个元素）。
empty()	若容器为空，则返回 true；否则 false。
size()	返回当前 set 容器中存有元素的个数。
max_size()	返回 set 容器所能容纳元素的最大个数，不同的操作系统，其返回值亦不相同。
insert()	向 set 容器中插入元素。
erase()	删除 set 容器中存储的元素。
swap()	交换 2 个 set 容器中存储的所有元素。这意味着，操作的 2 个 set 容器的类型必须相同。
clear()	清空 set 容器中所有的元素，即令 set 容器的 size() 为 0。
emplace()	在当前 set 容器中的指定位置直接构造新元素。其效果和 insert() 一样，但效率更高。
emplace_hint()	在本质上和 emplace() 在 set 容器中构造新元素的方式是一样的，不同之处在于，使用者必须为该方法提供一个指示新元素生成位置的迭代器，并作为该方法的第一个参数。
count(val)	在当前 set 容器中，查找值为 val 的元素的个数，并返回。注意，由于 set 容器中各元素的值是唯一的，因此该函数的返回值最大为 1。

有关表示各个成员函数的语法格式，读者不需要死记硬背，需要时直接去查 C++ 标准库即可，这里不再过多赘述。

如下的 C++ 程序演示了表中部分成员函数的用法：

#include <iostream>
#include <set>
#include <string>
using namespace std;

int main()
{
    //创建空set容器
    std::set<std::string> myset;
    //空set容器不存储任何元素
    cout << "1、myset size = " << myset.size() << endl;
    //向myset容器中插入新元素
    myset.insert("http://c.biancheng.net/java/");
    myset.insert("http://c.biancheng.net/stl/");
    myset.insert("http://c.biancheng.net/python/");
    cout << "2、myset size = " << myset.size() << endl;
    //利用双向迭代器，遍历myset
    for (auto iter = myset.begin(); iter != myset.end(); ++iter) {
        cout << *iter << endl;
    }
    return 0;
}

输出结果为：

1、myset size = 0
2、myset size = 3
http://c.biancheng.net/java/
http://c.biancheng.net/python/
http://c.biancheng.net/stl/

C++ set容器用法详解

set容器的构造

set容器的迭代器

set容器的基本操作

推荐阅读