devbox
Monodyee
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【C++标准库】你有所不知的set容器_c++ vector跟set

作者：Monodyee | 2024-05-03 09:52:34

赞

踩

c++ vector跟set

文章目录

1.set 和 vector 的区别

都是能存储一连串数据的容器。

  • set特点：自动排序、去重、过滤

区别1：set会自动给其中的元素从小到大排序，而vector会保持插入时的顺序。
区别2：set会把重复的元素去除，只保留一个，即去重。
区别3：vector中的元素在内存中是连续的，可以高效地按索引随机访问，set则不行。
区别4：set中的元素可以高效地按值查找，而 vector 则低效。

  • vector的查找复杂度是O(n)，set的查找复杂度是O(log n);

  • vector按照索引去查找，复杂度是O(1)，set按照值去查找复杂度是O(n)，内部实现是红黑树，查找过程类似二分法

  • eg：14/01_set/01.cpp

#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    vector<int> a = {9, 8, 5, 2, 1, 1};
    cout << "vector=" << a << endl;
    set<int> b = {9, 8, 5, 2, 1, 1};
    cout << "set=" << b << endl;
    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

14/01_set/printer.h

#pragma once

#include <iostream>
#include <utility>
#include <type_traits>

namespace std {

template <class T, class = const char *>
struct __printer_test_c_str {
    using type = void;
};

template <class T>
struct __printer_test_c_str<T, decltype(std::declval<T>().c_str())> {};

template <class T, int = 0, int = 0, int = 0,
         class = decltype(std::declval<std::ostream &>() << *++std::declval<T>().begin()),
         class = decltype(std::declval<T>().begin() != std::declval<T>().end()),
         class = typename __printer_test_c_str<T>::type>
std::ostream &operator<<(std::ostream &os, T const &v) {
    os << '{';
    auto it = v.begin();
    if (it != v.end()) {
        os << *it;
        for (++it; it != v.end(); ++it)
            os << ',' << *it;
    }
    os << '}';
    return os;
}

}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 测试
    在这里插入图片描述

（1）set 的排序：string 会按“字典序”来排

set 会从小到大排序，对 int 来说就是数值的大小比较。对于字符串类型 string，会按照字典序来排序。

所谓字典序就是优先比较两者第一个字符（按 ASCII 码比较），如果相等则继续比较下一个，不相等则直接以这个比较的结果返回。如果比到末尾都相等且字符串长度一样，则视为相等

警告：千万别用 set<char *> 做字符串集合。这样只会按字符串指针的地址去判断相等，而不是所指向字符串的内容。

  • eg：14/01_set/01a.cpp
#include <vector>
#include <set>
#include <string>
#include "printer.h"

using namespace std;

int main() {
    vector<string> a = {"arch", "any", "zero", "Linux"};
    cout << "vector=" << a << endl;
    set<string> b = {"arch", "any", "zero", "Linux"};
    cout << "set=" << b << endl;
    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • eg：14/01_set/01c.cpp
#include <vector>
#include <set>
#include <string>
#include <algorithm>
#include "printer.h"

using namespace std;

struct MyComp {
    bool operator()(string a, string b) const {
        std::transform(a.begin(), a.end(), a.begin(), ::tolower);
        std::transform(b.begin(), b.end(), b.begin(), ::tolower);
        return a < b;
    }
};

int main() {
    set<string, MyComp> b = {"arch", "any", "zero", "Linux", "linUX"};
    cout << "set=" << b << endl;
    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

  • 测试：
    在这里插入图片描述

  • eg：14/01_set/01d.cpp

#include <vector>
#include <set>
#include <string>
#include <algorithm>
#include "printer.h"

using namespace std;

struct MyComp {
    bool operator()(string a, string b) const {
        std::transform(a.begin(), a.end(), a.begin(), ::tolower);
        std::transform(b.begin(), b.end(), b.begin(), ::tolower);
        return a < b;
    }
};

int main() {
    set<string, MyComp> b = {"arch", "any", "zero", "Linux", "linUX"};
    cout << "set=" << b << endl;
    const_cast<string &>(*b.find("any")) = "zebra";
    cout << "set=" << b << endl;
    cout << "found=" << b.count("zebra") << endl;
    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • eg：14/01_set/01d.cpp
#include <vector>
#include <set>
#include <string>
#include <algorithm>
#include "printer.h"

using namespace std;

struct MyComp {
    bool operator()(string a, string b) const {
        std::transform(a.begin(), a.end(), a.begin(), ::tolower);
        std::transform(b.begin(), b.end(), b.begin(), ::tolower);
        return a < b;
    }
};

int main() {
    set<string, MyComp> b = {"arch", "any", "zero", "Linux", "linUX"};
    cout << "set=" << b << endl;
    const_cast<string &>(*b.find("any")) = "zebra";
    cout << "set=" << b << endl;
    cout << "found=" << b.count("zebra") << endl;
    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 测试：
    在这里插入图片描述

（2）set 的排序：自定义排序函数

set 作为模板类，其实有两个模板参数：set<T, CompT>

第一个 T 是容器内元素的类型，例如 int 或 string 等。
第二个 CompT 定义了你想要的比较函子，set 内部会调用这个函数来决定怎么排序。
如果 CompT 不指定，默认会直接用运算符 < 来比较。

  • 这里我们定义个 MyComp 作为比较函子，和默认的一样用 < 来比较，所以没有变化。
  • eg：14/01_set/01b.cpp
#include <vector>
#include <set>
#include <string>
#include "printer.h"

using namespace std;

struct MyComp {
    bool operator()(string const &a, string const &b) const {
        return a < b;
    }
};

int main() {
    set<string, MyComp> b = {"arch", "any", "zero", "Linux"};
    cout << "set=" << b << endl;
    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 测试：
    在这里插入图片描述

这里我们把比较函子 MyComp 定义成只比较字符串第一个字符 a[0] < b[0]。
神奇的一幕发生了，“any” 不见了！为什么？因为去重！

首先搞懂 set 内部是怎么确定两个元素 a 和 b 相等的：
!(a < b) && !(b < a)
也就是说他 set 内部没有用到 == 运算符，而是调用了两次比较函子来判断的。逻辑是：
若 a 不小于 b 且 b 不小于 a，则视为 a 等于 b，所以这就是为什么 set 只需要一个比较函子，不需要相等函子的原因。
所以我们这里写了 a[0] < b[0] 就相当于让相等条件变成了 a[0] == b[0]。也就是说只要第一个字符相等就视为字符串相等，所以 “arch” 和 “any” 会被视为相等的元素，从而被 set 给去重了！

  • 其实，map<K, T> 无非就是个只比较 K 无视 T 的 set<pair<K, T>>，顺手还加了一些方便的函数，比如 [] 和 at。

  • eg：set中使用自定义的lambda作为比较函数

#include <vector>
#include <set>
#include <string>
#include "printer.h"

using namespace std;

struct MyComp
{
    bool operator()(string const &a, string const &b) const
    {
        return a < b;
    }
};

int main()
{
    auto comp = [](string const &a, string const &b)
    { return a < b; };
    auto s = std::set<string, decltype(comp)>(comp);
    s = {"arch", "any", "zero", "Linux"};
    cout << "set=" << s << endl;
    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • eg：14/01_set/01b.cpp
#include <vector>
#include <set>
#include <string>
#include "printer.h"

using namespace std;

struct MyComp {
    bool operator()(string const &a, string const &b) const {
        return a[0]< b[0];
    }
};

int main() {
    set<string, MyComp> b = {"arch", "any", "zero", "Linux"};
    cout << "set=" << b << endl;
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 测试：
    在这里插入图片描述

（3）set 和 vector 迭代器的共同点

vector 具有 begin() 和 end() 两个成员函数，他们分别返回指向数组头部元素和尾部再之后一格元素的迭代器对象。

vector 作为连续数组，他的迭代器基本等效于指针。

set 也有 begin() 和 end() 函数，他返回的迭代器对象重载了 * 来访问指向的地址。

  • eg：14/01_set/02.cpp
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    vector<int> a = {1, 2, 3, 4, 5, 6, 7};
    vector<int>::iterator a_it = a.begin();
    cout << "vector[0]=" << *a_it << endl;

    set<int> b = {1, 2, 3, 4, 5, 6, 7};
    set<int>::iterator b_it = b.begin();
    cout << "set[0]=" << *b_it << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 测试：
    在这里插入图片描述

（4）迭代器的五大分类

在这里插入图片描述

std::lower_bound，二分法查找函数，它需要：具有随机访问迭代器的容器

包含关系：前向迭代器<双向迭代器<随机访问迭代器
这意味着如果一个STL模板函数（比如std::find）要求迭代器是前向迭代器即可，那么也可以给他随机访问迭代器，因为前向迭代器是随机访问迭代器的子集。

  • 例如，vector 和 list 都可以调用 std::find（set 则直接提供了 set.find 和set.lower_bound作为成员函数）

（5）set 和 vector 迭代器的不同点

set 的迭代器对象也重载了 ++ 为红黑树的遍历。
vector 提供了 + 和 += 的重载，而 set 没有。

  • 这是因为 vector 中的元素在内存中是连续的，可以随机访问。而 set 是不连续的，所以不能随机访问，只能顺序访问。

  • 所以这里调用 b.begin() + 3，就出错了。

  • eg：14/01_set/03.cpp

#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    vector<int> a = {1, 2, 3, 4, 5, 6, 7};
    vector<int>::iterator a_it = a.begin() + 3;
    cout << "vector[3]=" << *a_it << endl;

    set<int> b = {1, 2, 3, 4, 5, 6, 7};
    set<int>::iterator b_it = b.begin() + 3;
    cout << "set[3]=" << *b_it << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 测试：
    在这里插入图片描述

多次调用 ++ 实现 + 同样效果

set 迭代器没有重载 + 运算符，因为他不是随机迭代器。
那如果我确实需要让 set 迭代器向前移动 3 格怎么办？
可以调用三次 ++ 运算，实现和 + 3 同样的效果。

  • vector 迭代器的 + n 复杂度是 O(1)。而 set 迭代器模拟出来的 + n 复杂度为 O(n)。虽然低效，但至少可以用了

  • eg：14/01_set/02.cpp

#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main()
{
    vector<int> a = {1, 2, 3, 4, 5, 6, 7};
    vector<int>::iterator a_it = a.begin();
    cout << "vector[0]=" << *a_it << endl;

    set<int> b = {1, 2, 3, 4, 5, 6, 7};
    set<int>::iterator b_it = b.begin();
    ++b_it;
    ++b_it;
    ++b_it;
    cout << "set[0]=" << *b_it << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 测试：
    在这里插入图片描述

（6）std::next 等价于 +

但是这样手写三个 ++ 太麻烦了，而且是就地操作，会改变迭代器本身。

  • 因此标准库提供了 std::next 函数，他的内部实现相当于这样：
    他会自动判断迭代器是否支持 + 运算，如果不支持，会改为比较低效的调用 n 次 ++。
auto next(auto it, int n = 1)
{
	if (it is random_access)
		return it+n;
	while(n--)
	{
		++it;
	}
	return it;
	
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • eg：
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    vector<int> a = {1, 2, 3, 4, 5, 6, 7};
    vector<int>::iterator a_it = a.begin();
    a_it = std::next(a_it, 3);  // 会调用 a_it + 3
    cout << "vector[3]=" << *a_it << endl;

    set<int> b = {1, 2, 3, 4, 5, 6, 7};
    set<int>::iterator b_it = b.begin();
    b_it = std::next(b_it, 3);  // 会调用三次 ++b_it
    cout << "set[3]=" << *b_it << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 测试：
    在这里插入图片描述

（7）std::advance 等价于 +=

std::next 会返回自增后迭代器。
还有 std::advance 会就地自增作为引用传入的迭代器，他同样会判断是否支持 += 来决定要采用哪一种实现。

auto advance(auto& it, int n = 1)
{
	if (it is random_access)
		return it+n;
	while(n--)
	{
		++it;
	}
	return it;
	
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

  • 区别：advance 就地修改迭代器，没有返回值；next 修改迭代器后返回，不会改变原迭代器。

  • advance 相当于 +=，next 相当于 +。

  • eg：14/01_set/05.cpp

#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    vector<int> a = {1, 2, 3, 4, 5, 6, 7};
    vector<int>::iterator a_it = a.begin();
    std::advance(a_it, 3);  // 会调用 a_it += 3
    cout << "vector[3]=" << *a_it << endl;

    set<int> b = {1, 2, 3, 4, 5, 6, 7};
    set<int>::iterator b_it = b.begin();
    std::advance(b_it, 3);  // 会调用三次 ++b_it
    cout << "set[3]=" << *b_it << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 测试 ：
    在这里插入图片描述

next 和 advance 同样支持负数

  • next 的第二个参数 n 通常是正数，表示向前走的距离。
  • 如果迭代器类型是双向迭代器。next 的第二个参数 n 还可以是负数，这时他会让迭代器往前走一段距离，例如：

std::next(it, -3) 相当于 it - 3。
还可以用另一个专门的函数 std::prev(it, 3) 也相当于 it - 3。
(std::prev要求必须是双向迭代器）

auto prev(auto it, int n=1)
{
	return next(it,-n);
}

auto next(auto it, int n=1)
{
	if (it is random_access)
		return it + n;
	else
	{
		if (it is bidirectional && n <0)
		{
			while (n++)
			{
				--it;
			}
		}
		while(n--)
		{
			++it;
		}
		return it;
	}
	
}

void advance(auto& it, int n=1)
{
	if (it is random_access)
		return it + n;
	else
	{
		if (it is bidirectional && n <0)
		{
			while (n++)
			{
				--it;
			}
		}
		while(n--)
		{
			++it;
		}
	}
	
}



  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49

（8）std::distance 等价于 -

std::distance 会求出两个迭代器之间的距离（差值）。
std::distance(it1, it2) 相当于 it2 - it1，注意顺序和 - 相反

注意：distance 要求 it1 < it2

ptrdiff_t distance(auto it1, auto it2)
{
 if (it1 and it2 is random_access)
	return it2 - it1;
else
{
	ptrdiff_t  t=0;
	whilt(it1 != it2)
	{
		++it1;
		++t;
	}
	return n;
}


}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • eg：14/01_set/05a.cpp
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    vector<int> a = {1, 2, 3, 4, 5, 6, 7};
    vector<int>::iterator a_it1 = a.begin();
    vector<int>::iterator a_it2 = a.end();
    // 会调用 a_it2 - a_it1
    int a_size = std::distance(a_it1, a_it2);
    cout << "vector size = " << a_size << endl;

    set<int> b = {1, 2, 3, 4, 5, 6, 7};
    set<int>::iterator b_it1 = b.begin();
    set<int>::iterator b_it2 = b.end();
    // 会调用 ++b_it1 直到等于 b_it2
    int b_size = std::distance(b_it1, b_it2);
    cout << "set size = " << b_size << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 测试：
    在这里插入图片描述

（9）迭代器系列帮手函数一览

（10）打印任意 STL 容器

std::declval与decltype
std::declval() 也没什么好说的，它能返回类型 T 的右值引用。

  • 它就是用于返回一个 T 对象的伪造实例，同时又具有右值引用
  • 换句话说，它等价于下面的 objref 的编译期态：
T obj{};
T &objref = obj{};

  • 1
  • 2

首先，它在词法和语义上等价于 objref，是对象 T 的实例值，且具有 T&& 的类型；其次，它仅用于非求值的场合；再次，它并不真的存在。啥意思，说人话就是在编译期中，需要一个值对象，但并不希望这个值对象被编译为一个二进制实体，那就用 declval 虚拟地构造一个，从而彷佛获得了一个临时对象，可以在该对象上施加操作，例如调用成员函数什么的，但既然是虚拟的，就不会真的存在这么个临时对象，所以我称之为伪实例。

  • 我们常常并不真的直接需要 declval 求值求得的伪实例，更多的是需要借助于这个伪实例来求取到相应的类型描述，也就是 T。所以一般情况下 declval 之外往往包围着 decltype 计算，设法拿到 T 才是我们的真实目的
  • eg：可以看到，A 的伪实例能够“调用” A 的成员函数 t()，然后借助于 decltype 我们就可以拿到 t() 的返回类型，并用来声明一个具体的变量 a。因为 t() 的返回类型为 T，所以 main() 函数中的这条变量声明语句实际上等价于 int a{};。
#include <iostream>

namespace {
  struct base_t { virtual ~base_t(){} };

  template<class T>
    struct Base : public base_t {
      virtual T t() = 0;
    };

  template<class T>
    struct A : public Base<T> {
      ~A(){}
      virtual T t() override { std::cout << "A" << '\n'; return T{}; }
    };
}

int main() {
  decltype(std::declval<A<int>>().t()) a{}; // = int a;
  //可以借助 declval 来避开纯虚基类不能实例化的问题
  decltype(std::declval<Base<int>>().t()) b{}; // = int b;
  std::cout << a << ',' << b << '\n';
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

如果一个类没有定义默认构造函数（因为 A() 是不存在的。），例如下面的 decltype 就无法通过编译：

struct A{
  A() = delete;
  int t(){ return 1; }
}

int main(){
  decltype(A().t()) i; // BAD
}

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

但改用 declval 就能够绕过问题了：

int main(){
  decltype(std::declval<A>().t()) i; // OK
}

  • 1
  • 2
  • 3

总结：decltype必须能够实例化才可以，但是利用std::declval可以避免构造的要求（一般情况下使用的是无参构造函数的类）。

#pragma once

#include <iostream>
#include <utility>
#include <type_traits>

namespace std {

template <class T, class = const char *>
struct __printer_test_c_str {
    using type = void;
};

template <class T>
struct __printer_test_c_str<T, decltype(std::declval<T>().c_str())> {};

template <class T, int = 0, int = 0, int = 0,
         class = decltype(std::declval<std::ostream &>() << *++std::declval<T>().begin()),
         class = decltype(std::declval<T>().begin() != std::declval<T>().end()),
         class = typename __printer_test_c_str<T>::type>
std::ostream &operator<<(std::ostream &os, T const &v) {
    os << '{';
    auto it = v.begin();
    if (it != v.end()) {
        os << *it;
        for (++it; it != v.end(); ++it)
            os << ',' << *it;
    }
    os << '}';
    return os;
}

}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

2.向 set 中插入元素

（1）insert插入重复元素

可以通过调用 insert 往 set 中添加一个元素。
用户无需关心插入的位置，例如插入元素 3 时，set 会自动插入到 2 和 4 之间，从而使元素总是从小到大排列。

  • eg：14/01_set/06.cpp
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    set<int> b = {1, 4, 2, 1};
    cout << "插入之前: " << b << endl;
    b.insert(3);
    cout << "插入之后: " << b << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

返回值

pair<iterator, bool> insert(int val);

  • 1
  • 测试：
    在这里插入图片描述

set 具有自动去重的功能，如果插入的元素已经在 set 中存在，则不会完成插入。

  • 例如往集合 {1,2,4} 中插入 4 则什么也不会发生，因为 4 已经在集合中了。
  • eg：14/01_set/07.cpp
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    set<int> b = {1, 4, 2, 1};
    cout << "插入之前: " << b << endl;
    b.insert(4);
    cout << "插入之后: " << b << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 测试：
    在这里插入图片描述

（2）insert插入的第二个返回值

insert 函数的返回值是一个 pair 类型，也就是说他同时返回了两个值。其中第二个返回值是 bool 类型，指示了插入是否成功。

  • 若元素在 set 容器中已存有相同的元素，则插入失败，这个 bool 值为 false；如果元素在 set 中不存在，则插入成功，这个 bool 值为 true。
pair<iterator, bool> insert(int val);

  • 1
  • eg：14/01_set/08.cpp
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    set<int> b = {1, 4, 2, 1};
    auto res4 = b.insert(4);
    cout << "插入4成功：" << res4.second << endl;
    auto res3 = b.insert(3);
    cout << "插入3成功：" << res3.second << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 测试：
    在这里插入图片描述
    等价，看到返回值是pair，则自动把返回值翻译成pair
template <class T1, class T2>
struct pair{
	T1 first;
	T2 second;
};

pair<iterator, bool> insert(int x){
	if (插入成功)
		return {插入的位置, true};
	else
		return {已经存在的位置, false}
}

=================
template <class T1, class T2>
struct pair{
	T1 first;
	T2 second;
};

pair<iterator, bool> insert(int x){
	if (插入成功)
		return make_pair{插入的位置, true};
	else
		return make_pair{已经存在的位置, false}
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

（3）insert插入的第一个返回值

其中第一个返回值是一个迭代器，分两种情况讨论。

  • 当向 set 容器添加元素成功时，该迭代器指向 set 容器新添加的元素，bool 类型的值为 true；
  • 如果添加失败，即证明原 set 容器中已存有相同的元素，此时返回的迭代器就指向容器中相同的此元素，同时 bool 类型的值为 false。
  • eg：14/01_set/10.cpp
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    set<int> b = {1, 4, 2, 1};
    auto res1 = b.insert(3);
    cout << "插入3成功：" << res1.second << endl;
    cout << "3所在的位置：" << *res1.first << endl;
    auto res2 = b.insert(3);
    cout << "再次插入3成功：" << res2.second << endl;
    cout << "3所在的位置：" << *res2.first << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 测试：
    在这里插入图片描述

（4）glibc 中 pair 的定义

pair 类似于 python 里的元组，不过固定只能有两个元素，自从 C++11 引入了能支持任意多元素的 tuple 以来，就没 pair 什么事了……但是为了兼容 pair 还是继续存在着。pair 是个模板类，根据尖括号里你给定的类型来替换这里的 _T1 和 _T2。

  • 例如 pair<iterator, bool> 就会变成：
struct pair {
  iterator first;
  bool second;
};

  • 1
  • 2
  • 3
  • 4

在这里插入图片描述

（5）C++17 的结构化绑定来拆解 pair

C++17 提供了结构化绑定(structual binding)的语法，可以取出一个 POD 结构体的所有成员，pair 也不例外

auto [ok, it] = b.insert(3);
等价于
auto tmp = b.insert(3);
auto ok = tmp.first;
auto it = tmp.second;

  • 1
  • 2
  • 3
  • 4
  • 5
  • eg：14/01_set/10.cpp
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    set<int> b = {1, 4, 2, 1};
    auto [it1, ok1] = b.insert(3);
    cout << "插入3成功：" << ok1 << endl;
    cout << "3所在的位置：" << *it1 << endl;
    auto [it2, ok2] = b.insert(3);
    cout << "再次插入3成功：" << ok2 << endl;
    cout << "3所在的位置：" << *it2 << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 测试：
    在这里插入图片描述

（6）在 set 中查询元素是否存在

set 有一个 find 函数。

  • 只需给定一个参数，他会寻找 set 中与之相等的元素。(二分法)
    如果找到，则返回指向找到元素的迭代器。
    如果找不到，则返回 end() 迭代器。

  • 刚刚说过，end() 指向的是 set 的尾部再之后一格元素，他指向的是一个不存在的地址，不可能有任何元素在那里！
    因此 end() 常被标准库用作一个标记，来表示找不到的情况。Python 中的 find 找不到元素时会返回 -1 来表示，也是这个思想。

  • eg：14/01_set/11.cpp

#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    set<int> b = {1, 4, 2, 1};
    auto it = b.find(2);
    cout << "2所在位置：" << *it << endl;
    cout << "比2小的数：" << *prev(it) << endl;
    cout << "比2大的数：" << *next(it) << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

在这里插入图片描述

还有一种更直观的写法：

  • count 返回的是一个 int 类型，表示集合中相等元素的个数。
set.count(x) != 0

个数为 0 就说明集合中没有该元素。个数为 1 就说明集合中存在该元素；


  • 1
  • 2
  • 3
  • 4

为什么标准库让 count 计算个数而不是直接返回 bool…因为他们考虑到接口的泛用性，毕竟 multiset 就不去重。对于能去重的 set，count 只可能返回 0 或 1

  • eg：14/01_set/12.cpp
    因为 int 类型能隐式转换为 bool，所以 != 0 可以省略不写。
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    set<int> b = {1, 4, 2, 1};

    if (b.find(2) != b.end()) {
        cout << "集合中存在2" << endl;
    } else {
        cout << "集合中没有2" << endl;
    }

    if (b.find(8) != b.end()) {
        cout << "集合中存在8" << endl;
    } else {
        cout << "集合中没有8" << endl;
    }

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 测试：
    在这里插入图片描述

（7）从 set 中删除指定元素

set.erase(x) 可以删除集合中值为 x 的元素。
erase 返回一个整数，表示被他删除元素的个数。

个数为 0 就说明集合中没有该元素，删除失败。
个数为 1 就说明集合中存在该元素，删除成功。

这里的“个数”和 count 的情况很像，因为 set 中不会有重复的元素，所以 erase 只可能返回 0 或 1，表示是否删除成功。

  • eg：14/01_set/13.cpp
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    set<int> b = {1, 4, 2, 1};

    if (b.count(2)) {
        cout << "集合中存在2" << endl;
    } else {
        cout << "集合中没有2" << endl;
    }

    if (b.count(8)) {
        cout << "集合中存在8" << endl;
    } else {
        cout << "集合中没有8" << endl;
    }

    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 测试：
    在这里插入图片描述

erase 还支持迭代器作为参数。

  • set.erase(it) 可以删除集合位于 it 处的元素。

set.erase(set.find(x)) 会删除集合中值为 x 的元素，和 set.erase(x) 等价。
set.erase(set.begin()) 会删除集合中最小的元素（因为 set 具有自动排序的特性，排在最前面的元素一定是最小的那个）
set.erase(std::prev(set.end())) 会删除集合中最大的元素（因为自动排序的特性，排在最后面的元素一定是最大的那个）

  • eg：14/01_set/15.cpp
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    set<int> b = {1, 2, 3, 4, 5};

    cout << "原始集合：" << b << endl;
    b.erase(b.find(4));
    cout << "删除元素4：" << b << endl;
    b.erase(b.begin());
    cout << "删最小元素：" << b << endl;
    b.erase(std::prev(b.end()));
    cout << "删最大元素：" << b << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 测试：
    在这里插入图片描述
    在这里插入图片描述

（8）set 增删改查操作总结

在这里插入图片描述
不能改的原因是：

可能会破坏set的排序(虽然可以通过下面的方法进行强制修改，set的迭代器都是const的，本身不能修改)，
其find和count方法都是通过二分法查找的，破坏其排序，在二分查找时，arch为中点，zebra的z>arch的a，所以往后面找而不是往前找，所以找不到了。
正确做法：zebra应该是在arch的右边而不是左边

（9）从 set 中删除指定范围的元素

erase 还支持输入两个迭代器作为参数。

set.erase(beg, end) 可以删除集合中从 beg 到 end 之间的元素，包含 beg，不包含 end。也就是说他是个前开后闭区间 [beg, end)，毕竟这是标准库一贯的作风。
注意：beg 必须在 end 之前，否则崩溃。
用法举例：a.erase(a.find(2), a.find(4));
会删除 set 中所有满足 2 ≤ x＜4 的元素（因为 set 有自动排序的特性，所有元素都从小到大连续排列，所以删除 2 迭代器和 4 迭代器之间的元素其实就是删除 2 ≤ x＜4 的元素）
在这里插入图片描述

  • eg：14/01_set/16.cpp
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    set<int> b = {1, 2, 3, 4, 5};

    cout << "原始集合：" << b << endl;
    b.erase(b.find(2), b.find(4));
    cout << "删除[2,4)之间的元素：" << b << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 测试：
    在这里插入图片描述
    在这里插入图片描述

刚刚说的：a.erase(a.find(2), a.find(4));
这种写法有一个很大的问题：如果集合中没有 2 怎么办？

  • 那么 find(2) 因为找不到就会返回 end()，而 find(4) 成功找到返回了指向 4 的迭代器。这样一来 find(2) 的迭代器也就是 end() 其实在 find(4) 之后，违背了刚刚说的“beg 必须在 end 之前”这一规则，会导致标准库崩溃！

a.erase(a.find(2), a.find(4));
会删除 set 中所有满足 2 ≤ x＜4 的元素
前提是 2 和 4 这两个元素在集合中存在！

  • eg：14/01_set/17.cpp
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    set<int> b = {0, 1, 3, 4, 5};

    cout << "原始集合：" << b << endl;
    b.erase(b.find(2), b.find(4));
    cout << "删除[2,4)之间的元素：" << b << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 测试：
    在这里插入图片描述
    在这里插入图片描述

（10）lower_bound 和 upper_bound 函数

find(x) 是找第一个等于 x 的元素。
lower_bound(x) 找第一个大于等于 x 的元素。
upper_bound(x) 找第一个大于 x 的元素。

find 的条件更加严格（必须相等才算找到），lower_bound 和 upper_bound 就比较宽松。
所以如果集合中有 2：
lower_bound(2) 会返回指向 2 的迭代器。
upper_bound(2) 也会返回指向 3 的迭代器。
find(2) 会返回指向 2 的迭代器。

iterator find(int const &val) const;
iterator lower_bound(int const &val) const;
iterator upper_bound(int const &val) const;

  • 1
  • 2
  • 3
  • eg：14/01_set/18.cpp
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

static void check(bool success) {
    if (!success) throw;
    cout << "通过测试" << endl;
}

int main() {
    set<int> b = {0, 1, 3, 4, 5};

    cout << "原始集合：" << b << endl;
    check(b.find(2) == b.end());
    check(b.lower_bound(2) == b.find(3));
    check(b.upper_bound(2) == b.find(3));

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 测试：
    在这里插入图片描述
    在这里插入图片描述

从 set 中删除指定范围的元素（正确）

  • 注意这里变成 [2, 4] 两边都是闭区间了！因为 upper_bound 会返回指向大于 x 的元素，也就是等于 x 的元素再之后一个元素，所以刚好抵消了标准库的前开后闭区间效果
a.erase(a.lower_bound(2), a.upper_bound(4));
会删除 set 中所有满足 2 ≤ x ≤ 4 的元素

  • 1
  • 2
  • eg：14/01_set/19.cpp
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

static void check(bool success) {
    if (!success) throw;
    cout << "通过测试" << endl;
}

int main() {
    set<int> b = {1, 2, 3, 4, 5};

    cout << "原始集合：" << b << endl;
    check(b.find(2) != b.end());
    check(b.lower_bound(2) == b.find(2));
    check(b.upper_bound(2) == b.find(3));

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 测试：
    在这里插入图片描述
    在这里插入图片描述

（11）set 的遍历

遍历方法和上一课 vector 中的一样

  • eg：14/01_set/20.cpp
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    set<int> b = {0, 1, 3, 4, 5};

    cout << "原始集合：" << b << endl;
    b.erase(b.lower_bound(2), b.upper_bound(4));
    cout << "删除[2,4]之间的元素：" << b << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 测试：
    在这里插入图片描述

为了减少重复打代码的痛苦，C++17 引入了个语法糖：基于范围的 for 循环(range-based for loop)。

for (类型 变量名 : 可迭代对象)

  • eg：14/01_set/21.cpp
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    set<int> b = {0, 1, 3, 4, 5};

    cout << "原始集合：" << b << endl;

    for (auto it = b.begin(); it != b.end(); ++it) {
        int value = *it;
        cout << value << endl;
    }

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • eg：14/01_set/22.cpp
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    set<int> b = {0, 1, 3, 4, 5};

    cout << "原始集合：" << b << endl;

    for (int value: b) {
        cout << value << endl;
    }

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 测试：
    在这里插入图片描述

基于范围的 for 循环只是一个简写，他会遍历整个区间 [begin, end)。
有时写完整版会有更大的自由度，也就是说这里的 begin 和 end 可以替换为其他位置的迭代器（如 find/lower_bound/upper_bound）

  • eg：14/01_set/23.cpp，选择满足 2 ≤ x ≤ 4 的元素来打印。
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    set<int> b = {0, 1, 3, 4, 5};

    cout << "原始集合：" << b << endl;

    for (auto it = b.lower_bound(2); it != b.upper_bound(4); ++it) {
        int value = *it;
        cout << value << endl;
    }

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 测试：
    在这里插入图片描述
    在这里插入图片描述

（12）set 和其他容器之间的转换

vector 的构造函数也能接受两个前向迭代器作为参数，set 的迭代器符合这个要求。
所以可以把 set 中的一个区间（2 ≤ x ≤ 4）拷贝到 vector 中去。

  • 相当于过滤出所有2 ≤ x ≤ 4 的元素了。
  • vector 的构造函数可以接受任何前向迭代器。而 set 是双向迭代器，覆盖了前向迭代器，满足要求
  • eg：14/01_set/24.cpp
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    set<int> b = {0, 1, 3, 4, 5};

    cout << "原始集合：" << b << endl;

    vector<int> arr(b.lower_bound(2), b.upper_bound(4));

    cout << "结果数组：" << arr << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 测试：
    在这里插入图片描述
    在这里插入图片描述
  • 如果是 vector(b.begin(), b.end()) 那就毫无保留地把 set 的全部元素都拷贝进 vector 了，这是最常用的。
  • eg：14/01_set/25.cpp
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    set<int> b = {0, 1, 3, 4, 5};

    cout << "原始集合：" << b << endl;

    vector<int> arr(b.begin(), b.end());

    cout << "结果数组：" << arr << endl;

    return 0;
}
a

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 测试：
    在这里插入图片描述
    在这里插入图片描述

也可以反过来，把 vector 转成 set。

强制转换到 vector 容器：vector(b.begin(), b.end())
强制转换到 set 容器：set(b.begin(), b.end())

  • eg：14/01_set/25a.cpp
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    vector<int> b = {0, 1, 3, 4, 5};

    cout << "原始数组：" << b << endl;

    set<int> arr(b.begin(), b.end());

    cout << "结果集合：" << arr << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 测试：
    在这里插入图片描述

（13）set 的妙用：排序

把 vector 转成 set 会让元素自动排序(std::sort也可以排序)和去重。
我们其实可以利用这一点，把 vector 转成 set 再转回 vector，这样就实现去重了。

  • eg：14/01_set/27.cpp
#include <vector>
#include <set>
#include "printer.h"

using namespace std;

int main() {
    vector<int> arr = {9, 8, 5, 2, 1, 1};

    cout << "原始数组：" << arr << endl;
    /*
	arr.assign (v.begin(), b.end())
等价于
arr = vector(b.begin(), b.end())
*/
    set<int> b(arr.begin(), arr.end());
    arr.assign(b.begin(), b.end());

    cout << "排序&去重后的数组：" << arr << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 测试：
    在这里插入图片描述

（14）清空 set 所有元素

清空 set 有三种方式。

最常用的是调用 clear 函数。
这和 vector 的 clear 函数名字是一样的，方便记忆。

  • eg：14/01_set/28.cpp
#include <vector>
#include <set>
#include <algorithm>
#include <functional>
#include "printer.h"

using namespace std;

int main() {
    set<int> b = {1, 2, 3, 4, 5};

    cout << "原始集合：" << b << endl;

    b.clear();
    // b = {};
    // b.erase(b.begin(), b.end());

    cout << "清空后集合：" << b << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 测试：
    在这里插入图片描述

（14）set 的大小（元素个数）

和 vector 一样，set 也有个 size() 函数查询其中元素个数。

size_t size() const noexcept;


  • 1
  • 2
  • eg：14/01_set/29.cpp
#include <vector>
#include <set>
#include <algorithm>
#include <functional>
#include "printer.h"

using namespace std;

int main() {
    set<int> b = {1, 2, 3, 4, 5};

    cout << "原始集合：" << b << endl;

    cout << "元素个数：" << b.size() << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 测试：
    在这里插入图片描述

3.set 的不去重版本：multiset

set 具有自动排序，自动去重，能高效地查询的特点。

  • 其中去重和数学的集合很像。

还有一种不会去重的版本，那就是 multiset，他允许重复的元素，但仍保留自动排序，能高效地查询的特点。

特点：因为 multiset 不会去重，但又自动排序，所以其中所有相等的元素都会紧挨着，例如 {1, 2, 2, 4, 6}。

  • eg：14/04_multiset/01.cpp
#include <set>
#include "printer.h"

using namespace std;

int main() {
    set<int> a = {1, 1, 2, 2, 3};
    multiset<int> b = {1, 1, 2, 2, 3};

    cout << "set: " << a << endl;
    cout << "multiset: " << b << endl;

    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 测试：
    在这里插入图片描述

（1）查找 multiset 中的等值区间

了 multiset 里相等的元素都是紧挨着排列的。

  • 所以可以用 upper_bound 和 lower_bound 函数获取所有相等值的区间。
[lower_bound, upper_bound)

iterator lower_bound(int const &val) const;
iterator upper_bound(int const &val) const;

  • 1
  • 2
  • 3
  • 4
  • eg：14/04_multiset/02.cpp
#include <set>
#include "printer.h"

using namespace std;

int main() {
    multiset<int> b = {1, 1, 2, 2, 3};

    cout << "原始集合：" << b << endl;
    b.erase(b.lower_bound(2), b.upper_bound(2));
    cout << "删除2以后：" << b << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 测试：
    在这里插入图片描述
    在这里插入图片描述

（2）equal_range

对于 lower_bound 和 upper_bound 的参数相同的情况，可以用 equal_range 一次性求出两个边界，获得等值区间，更高效。

pair<iterator, iterator> equal_range(int const &val) const;

  • 1
  • eg：14/04_multiset/03.cpp
#include <set>
#include "printer.h"

using namespace std;

int main() {
    multiset<int> b = {1, 1, 2, 2, 3};

    cout << "原始集合：" << b << endl;
    auto r = b.equal_range(2);
    b.erase(r.first, r.second);
    cout << "删除2以后：" << b << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 测试：
    在这里插入图片描述

equal_range（等值区间）和调用两次 lower_bound（大于等于起点）upper_bound（大于起点）的不同：

当指定的值找不到时，equal_range 返回两个 end() 迭代器，代表空区间。
lower/upper_bound 却会正常返回指向大于等于/大于指定值的迭代器。

原因：equal_range 的用途都是返回一个用来遍历的区间，两个迭代器是一起用的，不会单独用。所以为了高效，找不到等值元素会直接返回空区间。

  • eg：14/04_multiset/05.cpp
#include <set>
#include "printer.h"

using namespace std;

int main() {
    multiset<int> b = {1, 1, 2, 2, 3};

    cout << "原始集合：" << b << endl;
    auto r = b.equal_range(6);

    cout << boolalpha;
    cout << (r.first == b.end()) << endl;
    cout << (r.second == b.end()) << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 测试：
    在这里插入图片描述

（3）删除 multiset 中的等值区间

erase 只有一个参数的版本，会把所有等于 2 的元素删除。

例如：b.erase(2) 等价于b.erase(b.lower_bound(2), b.upper_bound(2));

iterator erase(int const &val) const;

  • 1
  • eg：14/04_multiset/04.cpp
#include <set>
#include "printer.h"

using namespace std;

int main() {
    multiset<int> b = {1, 1, 2, 2, 3};

    cout << "原始集合：" << b << endl;
    b.erase(2);
    cout << "删除2以后：" << b << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 测试：
    在这里插入图片描述

（4）查找 multiset 中的等值区间

equal_range 返回的等值区间，可以求长度，也可以遍历。

对 multiset 而言遍历似乎没什么用，反正都是一堆相等的元素。

求长度也没什么用，可以用 count 替代

pair<iterator, iterator> equal_range(int const &val) const;

  • 1
  • eg：14/04_multiset/06.cpp
#include <set>
#include "printer.h"

using namespace std;

int main() {
    multiset<int> b = {1, 1, 2, 2, 3};

    cout << "原始集合：" << b << endl;

    auto r = b.equal_range(2);
    size_t n = std::distance(r.first, r.second);
    cout << "等于2的元素个数：" << n << endl;

    for (auto it = r.first; it != r.second; ++it) {
        int value = *it;
        cout << value << endl;
    }

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 测试：
    在这里插入图片描述

（5）求 multiset 中的等值元素个数

count(x) 返回 multiset 中等于 x 的元素个数（如果找不到则返回 0）。

刚刚说 set（具有去重功能）的 count 只会返回 0 或 1。

而 multiset（没有去重功能）的 count 可以返回任何 ≥ 0 的数。

size_t count(int const &val) const;

  • 1
  • eg：14/04_multiset/07.cpp
#include <set>
#include "printer.h"

using namespace std;

int main() {
    multiset<int> b = {1, 1, 1, 2, 2, 3};

    b.size();
    cout << "原始集合：" << b << endl;
    cout << "等于2的元素个数：" << b.count(2) << endl;
    cout << "等于1的元素个数：" << b.count(1) << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 测试：
    在这里插入图片描述

（6）multiset 也的find 函数

multiset 允许多个重复的元素存在，那么 find 会返回哪一个？

  • 第一个！

find(x) 会返回第一个等于 x 的元素的迭代器。找不到也是返回 end()。

  • eg：14/04_multiset/08.cpp
#include <set>
#include "printer.h"

using namespace std;

int main() {
    multiset<int> b = {1, 1, 1, 2, 2, 3};

    cout << "原始集合：" << b << endl;
    cout << boolalpha;
    cout << "集合中存在2：" << (b.find(2) != b.end()) << endl;
    cout << "集合中存在1：" << (b.find(1) != b.end()) << endl;
    cout << "第一个1在头部：" << (b.find(1) == b.begin()) << endl;

    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 测试：
    在这里插入图片描述

（7）multiset 增删改查操作总结

在这里插入图片描述

（8）set 系列成员函数总结

unordered_set：无序set，使用哈希散列表实现的，可查等职区间，但是无法比较大小
在这里插入图片描述

4.C++11 新增：unordered_set 容器

set 会让元素从小到大排序。

而 unordered_set 不会排序，里面的元素都是完全随机的顺序，和插入的顺序也不一样。虽然你可能注意到这里的刚好和插入的顺序相反？

  • 巧合而已，具体怎么顺序是和 glibc 实现有关的。

  • set 基于红黑树实现，相当于二分查找树，unordered_set 基于散列哈希表实现，正是哈希函数导致了随机的顺序。

  • eg：14/05_unordered/01.cpp

#include <set>
#include <unordered_set>
#include "printer.h"

using namespace std;

int main() {
    set<int> a = {1, 4, 2, 8, 5, 7};
    unordered_set<int> b = {1, 4, 2, 8, 5, 7};
    b.rehash(b.bucket(1));

    cout << "set: " << a << endl;
    cout << "unordered_set: " << b << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • eg：14/05_unordered/01.cpp，set中使用自定义的lambda作为比较函数
#include <set>
#include <vector>
#include <unordered_set>
#include "printer.h"

using namespace std;

int main() {
    vector<int> arr(100);

    auto comp = [&] (int i, int j) {
        return arr[i] < arr[j];
    };

    set<int, decltype(comp)> a({1, 4, 2, 8, 5, 7}, comp);
    unordered_set<int> b = {1, 4, 2, 8, 5, 7};

    cout << "set: " << a << endl;
    cout << "unordered_set: " << b << endl;

    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

（1）不同版本的 set 容器比较

在这里插入图片描述
在这里插入图片描述

5.查找方面各容器适合的领域

vector 适合：按索引查找。通过运算符 []。
set 适合：按值相等查找，按值大于/小于查找。分别通过函数 find、lower_bound、upper_bound。
unordered_set 只适合：按值相等查找，通过函数 find。

小贴士：unordered_set 的性能在数据量足够大（＞1000）时，平均查找时间比 set 短，但不保证稳定。
我个人推荐使用久经沙场的 set，数据量小时更高效。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/529017
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号