当前位置： 首页 > article >正文

容器库(6)-std::set

article 2024/11/18 23:29:58

std::set是以key为元素的关联容器，容器中的key是唯一的且按顺序排列的。搜索、移除和插入的时间复杂度是 O(logn)。底层通常是以红黑树实现的。

template<
    class Key,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<Key>
> class set;

本文章的代码库：

https://gitee.com/gamestorm577/CppStd

成员函数

构造、析构和赋值

构造函数

可以用迭代器、另一个set或者元素列表来构造一个set。代码示例：

auto print_func = [](const std::set<int>& set)
{
    for (auto i : set)
    {
        std::cout << i << " ";
    }
    std::cout << std::endl;
};

std::vector<int> vec{11, 7, 5, 3, 5, 5, 11};

std::set<int> s1(vec.begin(), vec.end());
std::set<int> s2(s1);
std::set<int> s3{29, 15, 15, 3, 17};

print_func(s1);
print_func(s2);
print_func(s3);

输出结果：

3 5 7 11 
3 5 7 11 
3 15 17 29

析构函数

删除set时，会调用各元素的析构函数。代码示例：

struct MyStruct
{
    MyStruct(int i)
        : Index(i)
    {
    }

    ~MyStruct()
    {
        std::cout << "destruct, Index = " << Index << std::endl;
    }

    int Index = 0;
};

struct MyStructCmp
{
    bool operator()(const MyStruct& lhs, const MyStruct& rhs) const
    {
        return lhs.Index < rhs.Index;
    }
};

std::set<MyStruct, MyStructCmp> s = {7, 3, 17, 3, 9};
std::cout << "end" << std::endl;

输出结果：

destruct, Index = 9
destruct, Index = 3
destruct, Index = 17
destruct, Index = 3
destruct, Index = 7
end
destruct, Index = 3
destruct, Index = 9
destruct, Index = 17
destruct, Index = 7

赋值函数

可以用另一个set或者元素列表给set赋值。代码示例：

std::set<int> tmp{29, 15, 15, 3, 17, 17, 19};
std::set<int> s1;
std::set<int> s2;
s1 = tmp;
s2 = {29, 15, 15, 3, 17, 17, 19};
std::cout << "s1 size = " << s1.size() << std::endl;
std::cout << "s2 size = " << s2.size() << std::endl;

输出结果：

s1 size = 5
s2 size = 5

迭代器

接口begin、cbegin指向list起始的迭代器，end、cend指向末尾的迭代器。rbegin、crbegin指向起始的逆向迭代器，rend、crend指向末尾的逆向迭代器。无论什么迭代器都不能修改元素的值。代码示例：

std::set<int> s{7, 15, 19, 29, 39};
for (auto iter = s.begin(); iter != s.end(); ++iter)
{
    std::cout << "num is: " << *iter << std::endl;
}

输出结果：

num is: 7
num is: 15
num is: 19
num is: 29
num is: 39

容量

empty

检查set是否为空。代码示例：

std::set<int> s1{7, 15, 19, 29, 39};
std::set<int> s2;
std::cout << std::boolalpha;
std::cout << "s1 empty: " << s1.empty() << std::endl;
std::cout << "s2 empty: " << s2.empty() << std::endl;

输出结果：

s1 empty: false
s2 empty: true

size

获取set中元素的个数。代码示例：

std::set<int> s1{7, 15, 19, 29, 39};
std::set<int> s2;
std::cout << "s1 size = " << s1.size() << std::endl;
std::cout << "s2 size = " << s2.size() << std::endl;

输出结果：

s1 size = 5
s2 size = 0

max_size

返回可以容纳的最大元素个数。代码示例：

struct MyStruct
{
    double num1;
    double num2;
    double num3;
    double num4;
};

std::set<float> s1;
std::set<double> s2;
std::set<MyStruct> s3;
std::cout << "s1 max size = " << s1.max_size() << std::endl;
std::cout << "s2 max size = " << s2.max_size() << std::endl;
std::cout << "s3 max size = " << s3.max_size() << std::endl;

输出结果：

s1 max size = 576460752303423487
s2 max size = 461168601842738790
s3 max size = 288230376151711743

修改器

clear

清除所有的元素。代码示例：

std::set<int> s{7, 15, 19, 29, 39};
std::cout << "s size = " << s.size() << std::endl;
s.clear();
std::cout << "s size = " << s.size() << std::endl;

输出结果：

s size = 5
s size = 0

extract

提取一个元素并返回它的句柄，提取完成后set不再拥有该元素。代码示例：

auto print_func = [](const std::set<int>& set)
{
    for (auto i : set)
    {
        std::cout << i << " ";
    }
    std::cout << std::endl;
};

std::set<int> s{1, 2, 3};
print_func(s);
std::set<int>::node_type node = s.extract(1);
print_func(s);

std::cout << std::boolalpha;
std::cout << "node empty: " << node.empty() << std::endl;
std::cout << "node value: " << node.value() << std::endl;
node.value() = 5;
std::cout << "node value: " << node.value() << std::endl;

insert

插入元素，可以插入元素、迭代器或者节点。代码示例：

auto print_func = [](const std::set<int>& set)
{
    for (auto i : set)
    {
        std::cout << i << " ";
    }
    std::cout << std::endl;
};

std::vector<int> vec{7, 8, 9};

std::set<int> s{2, 3, 5, 7, 11};
print_func(s);

s.insert(4);
print_func(s);
s.insert(4);
print_func(s);

s.insert(std::next(s.begin(), 1), 19);
print_func(s);

s.insert(vec.begin(), vec.end());
print_func(s);

std::set<int>::node_type node = s.extract(19);
print_func(s);
node.value() = 1;
s.insert(std::move(node));
print_func(s);

输出结果：

2 3 5 7 11 
2 3 4 5 7 11 
2 3 4 5 7 11 
2 3 4 5 7 11 19 
2 3 4 5 7 8 9 11 19 
2 3 4 5 7 8 9 11 
1 2 3 4 5 7 8 9 11

emplace

构造一个元素到set中。代码示例：

struct MyStruct
{
    MyStruct(float num1, int num2)
    {
        std::cout << "construct " << num1 << " " << num2 << std::endl;
    }
};

struct MyStructCmp
{
    bool operator()(const MyStruct&, const MyStruct&) const
    {
        return true;
    }
};

std::set<MyStruct, MyStructCmp> s;
s.emplace(1.5f, 2);
s.emplace(12.1f, 9);

输出结果：

construct 1.5 2
construct 12.1 9

erase

移除指定位置的元素或者移除指定的值。代码示例：

auto print_func = [](const std::set<int>& set)
{
    for (auto i : set)
    {
        std::cout << i << " ";
    }
    std::cout << std::endl;
};

std::set<int> s{1, 2, 3, 4, 5, 6, 7, 8, 9};
print_func(s);
s.erase(std::next(s.begin(), 2));
print_func(s);
s.erase(std::next(s.begin(), 2), std::next(s.begin(), 5));
print_func(s);
s.erase(8);
print_func(s);

输出结果：

1 2 3 4 5 6 7 8 9 
1 2 4 5 6 7 8 9 
1 2 7 8 9 
1 2 7 9

swap

和另一个set交换元素内容。代码示例：

std::set<int> s1{1, 2, 3, 4, 5, 6, 7, 8, 9};
std::set<int> s2{1, 2, 3};
s1.swap(s2);
std::cout << "s1 size = " << s1.size() << std::endl;
std::cout << "s2 size = " << s2.size() << std::endl;

输出结果：

s1 size = 3
s2 size = 9

merge

合并另一个set或者multiset的元素。代码示例：

auto print_func = [](std::string tag, const std::set<int>& set)
{
    std::cout << tag;
    for (auto i : set)
    {
        std::cout << i << " ";
    }
    std::cout << std::endl;
};

std::set<int> s1{1, 2, 8, 9};
std::set<int> s2{3, 4};
s1.merge(s2);
print_func("s1 = ", s1);
print_func("s2 = ", s2);

输出结果：

s1 = 1 2 3 4 8 9 
s2 =

查找

count

获取元素的数量。由于set的元素是不重复的，结果只能是0或者1。代码示例：

std::set<int> s{1, 2, 8, 9};
std::cout << "elment 1 count = " << s.count(1) << std::endl;
std::cout << "elment 3 count = " << s.count(3) << std::endl;

输出结果：

elment 1 count = 1
elment 3 count = 0

find

获取元素的位置。代码示例：

std::set<int> s{1, 2, 8, 9};
auto iter1 = s.find(1);
auto iter2 = s.find(3);

std::cout << std::boolalpha;
std::cout << "elment has 1: " << (iter1 == s.end()) << std::endl;
std::cout << "elment has 3: " << (iter2 == s.end()) << std::endl;

输出结果：

elment has 1: false
elment has 3: true

contains

检查是否包含特定的元素。代码示例：

std::set<int> s{1, 2, 8, 9};
std::cout << std::boolalpha;
std::cout << "contain 1: " << s.contains(1) << std::endl;
std::cout << "contain 3: " << s.contains(3) << std::endl;

输出结果：

contain 1: true
contain 3: false

equal_range

返回两个迭代器，第一个迭代器指向第一个大于等于指定元素的位置，第一个迭代器指向第一个大于指定元素的位置。代码示例：

std::set<int> s{2, 3, 5, 7, 11};
auto [iter1, iter2] = s.equal_range(3);
std::cout << "iter1 is: " << *iter1 << std::endl;
std::cout << "iter2 is: " << *iter2 << std::endl;
auto [iter3, iter4] = s.equal_range(4);
std::cout << "iter3 is: " << *iter3 << std::endl;
std::cout << "iter4 is: " << *iter4 << std::endl;
iter1 is: 3
iter2 is: 5
iter3 is: 5
iter4 is: 5

lower_bound

获取首个大于等于指定元素的位置。代码示例：

std::set<int> s{2, 3, 5, 7, 11};
auto iter1 = s.lower_bound(3);
auto iter2 = s.lower_bound(4);
std::cout << "iter1 is: " << *iter1 << std::endl;
std::cout << "iter2 is: " << *iter2 << std::endl;

输出结果：

iter1 is: 3
iter2 is: 5

upper_bound

获取首个大于指定元素的位置。代码示例：

std::set<int> s{2, 3, 5, 7, 11};
auto iter1 = s.upper_bound(3);
auto iter2 = s.upper_bound(4);
std::cout << "iter1 is: " << *iter1 << std::endl;
std::cout << "iter2 is: " << *iter2 << std::endl;

输出结果：

iter1 is: 5
iter2 is: 5

观察器

key_comp

返回用于比较键值的函数。代码示例：

struct Comp
{
    bool operator()(int lhs, int rhs) const
    {
        std::cout << "Comp" << std::endl;
        return lhs < rhs;
    }
};

std::set<int, Comp> s;
auto comp_func = s.key_comp();
std::cout << std::boolalpha;
std::cout << comp_func(10, 20) << std::endl;

输出结果：

Comp
true

value_comp

和key_comp相同，返回用于比较键值的函数。

非成员函数

比较运算符

operator==,!=,<,<=,>,>=用于比较两个set。代码示例：

std::set<int> s1 = {2, 3, 5};
std::set<int> s2 = {5, 3, 2};
std::cout << std::boolalpha;
std::cout << "s1 == s2: " << (s1 == s2) << std::endl;
std::cout << "s1 != s2: " << (s1 != s2) << std::endl;
std::cout << "s1 <  s2: " << (s1 < s2) << std::endl;
std::cout << "s1 <= s2: " << (s1 <= s2) << std::endl;
std::cout << "s1 >  s2: " << (s1 > s2) << std::endl;
std::cout << "s1 >= s2: " << (s1 >= s2) << std::endl;

输出结果：

s1 == s2: true
s1 != s2: false
s1 <  s2: false
s1 <= s2: true
s1 >  s2: false
s1 >= s2: true

swap

交换两个set的元素内容。示例代码：

std::set<int> s1 = {2, 3, 5};
std::set<int> s2 = {5, 3, 2, 19};
std::swap(s1, s2);
std::cout << "s1 size is: " << s1.size() << std::endl;
std::cout << "s2 size is: " << s2.size() << std::endl;

输出结果：

s1 size is: 4
s2 size is: 3

erase_if

删除满足条件的元素。代码示例：

std::set<int> s = {2, 3, 5, 7, 11, 13, 17};
std::cout << "s size = " << s.size() << std::endl;
std::erase_if(s,
              [](int a)
              {
                  return a > 11;
              });
std::cout << "s size = " << s.size() << std::endl;

输出结果：

s size = 7
s size = 5


http://www.kler.cn/a/231820.html

相关文章：

  • mybatis 动态SQL语句
  • uniapp微信小程序接入airkiss插件进行WIFI配网
  • Ceph PG(归置组)的状态说明
  • 大数据如何助力干部选拔的公正性
  • 【目标检测】【Ultralytics-YOLO系列】Windows11下YOLOV5人脸目标检测
  • 前后端请求响应
  • Codeforces Round 260 (Div. 1)A. Boredom（dp）
  • springboot172基于springboot的二手车交易系统的设计与实现
  • Rust开发WASM，WASM Runtime运行
  • 蓝桥杯-求阶乘-python
  • elk之search API
  • Apollo2.2.0 arm 达梦 人大金仓 适配
  • 华为认证 | 2024了，华为HCIA还有必要考？
  • CSS 控制 video 标签的控制栏组件的显隐
  • C语言实现网络爬虫
  • 【C++】C++的简要介绍
  • Stable Diffusion 模型下载：Samaritan 3d Cartoon SDXL（撒玛利亚人 3d 卡通 SDXL）
  • Nginx+React在Docker中实现项目部署
  • Pinia的使用与原理
  • Rust入门1——HelloWorld
  • Golang数据库编程详解 | 深入浅出Go语言原生数据库编程
  • C语言：操作符详解
  • LabVIEW高精度主动模拟肺系统的开发与应用
  • 华为机考入门python3--（11）牛客11-数字颠倒
  • 【C语言自定义类型详解进阶】结构体（补充结构体的对齐和位段，一口气看完系列，央妈都点赞的博文）
  • 【Java 数据结构】反射