C++ set总结

分手后的思念是犯贱 2023-03-04 10:29 36阅读 0赞

**目录**

介绍

常用函数

函数实例

初始化及遍历

查找并删除

插入元素

修改元素

关于set的几个问题

--------------------

# **介绍** #

set集合容器实现了红黑树的平衡二叉检索树的数据结构，它会自动调整二叉树的排列，把元素放到适当的位置。set容器所包含的元素的值是唯一的，集合中的元素按一定的顺序排列。其实set的大部分操作是与vector类似的，不过set不支持随机访问，必须要使用迭代器去访问。由于set放入一个元素就会调整这个元素的位置，把它放到合适的位置，所以set中只有一个insert插入操作。

# **常用函数** #

**set****的各成员函数列表如下:**

1. begin()--返回指向第一个元素的迭代器

2. clear()--清除所有元素

3. count()--返回某个值元素的个数

4. empty()--如果集合为空，返回true

5. end()--返回指向最后一个元素的迭代器

6. equal\_range()--返回集合中与给定值相等的上下限的两个迭代器

7. erase()--删除集合中的元素

8. find()--返回一个指向被查找到元素的迭代器

9. get\_allocator()--返回集合的分配器

10. insert()--在集合中插入元素

11. lower\_bound()--返回指向大于（或等于）某值的第一个元素的迭代器

12. key\_comp()--返回一个用于元素间值比较的函数

13. max\_size()--返回集合能容纳的元素的最大限值

14. rbegin()--返回指向集合中最后一个元素的反向迭代器

15. rend()--返回指向集合中第一个元素的反向迭代器

16. size()--集合中元素的数目

17. swap()--交换两个集合变量

18. upper\_bound()--返回大于某个值元素的迭代器

19. value\_comp()--返回一个用于比较元素间的值的函数

# **函数实例** #

## **初始化及遍历** ##

\#include <iostream>

\#include <set>

\#include <algorithm>

using namespace std;

int main() \{

int arr\[5\] = \{ 0,1,2,3,4 \};

set<int> mySet(arr, arr + 5);

for (auto it = mySet.begin(); it != mySet.end(); it\++)

cout << " " << \*it;

cout << "\\n";

set<int> mySet1 = \{ 0,1,2,3,4,5 \};

for (auto it = mySet1.begin(); it != mySet1.end(); it\++)

cout << " " << \*it;

cout << "\\n";

set<int> mySet2;

mySet2.insert(11);

mySet2.insert(12);

mySet2.insert(13);

mySet2.insert(14);

mySet2.insert(15);

mySet2.insert(16);

mySet2.insert(17);

mySet2.insert(18);

for (auto it = mySet2.begin(); it != mySet2.end(); it\++)

cout << " " << \*it;

cout << "\\n";

return 0;

## **查找并删除** ##

\#include <iostream>

\#include <set>

\#include <algorithm>

using namespace std;

int main() \{

set<int> st;

for (int i = 0; i < 10; i++)

st.insert(i);

// 删除容器中值为elem的元素

st.erase(4);

// 任意位置删除一个元素

set<int>::iterator it = st.begin();

st.erase(it);

// 删除\[first,last\]之间的元素

st.erase(st.begin(), \++st.begin());

// 遍历显示

for (it = st.begin(); it != st.end(); it\++)

cout << \*it << " ";

cout << endl;

// 清空所有元素

st.clear();

// 判断set是否为空

if (st.empty())

cout << "集合为空" << endl; // 输出：集合为空

return 0;

\}// list::sort

\#include <iostream>

\#include <set>

\#include <algorithm>

using namespace std;

int main() \{

set<int> mySet2;

mySet2.insert(11);

mySet2.insert(12);

mySet2.insert(13);

mySet2.insert(18);

mySet2.insert(14);

mySet2.insert(15);

mySet2.insert(16);

mySet2.insert(17);

for (auto it = mySet2.begin(); it != mySet2.end();)

if (\*it == 15)

it = mySet2.erase(it);

else

it\++;

cout << "\\n";

for (auto it = mySet2.begin(); it != mySet2.end();it\++)

cout << " " << \*it;

cout << "\\n";

return 0;

\#include <iostream>

\#include <set>

\#include <algorithm>

using namespace std;

int main() \{

set<int> mySet2;

mySet2.insert(11);

mySet2.insert(12);

mySet2.insert(13);

mySet2.insert(18);

mySet2.insert(14);

mySet2.insert(15);

mySet2.insert(16);

mySet2.insert(17);

mySet2.insert(15);

mySet2.insert(16);

mySet2.insert(17);

set<int>::iterator iter;

iter = mySet2.find(17);

if (iter == mySet2.end())

cout << "没有找到该元素" << endl;

else

cout << "找到该元素" << \*iter << endl;

mySet2.erase(\*iter);

return 0;

查找元素的个数

// list::sort

\#include <iostream>

\#include <set>

\#include <algorithm>

using namespace std;

int main() \{

set<int> mySet2;

mySet2.insert(11);

mySet2.insert(12);

mySet2.insert(13);

mySet2.insert(18);

mySet2.insert(14);

mySet2.insert(15);

mySet2.insert(16);

mySet2.insert(17);

mySet2.insert(15);

mySet2.insert(16);

mySet2.insert(17);

int cc = mySet2.count(13);

cout << "元素的个数为：" << cc<<endl;

return 0;

## **插入元素** ##

\#include <iostream>

\#include <set>

\#include <algorithm>

using namespace std;

int main() \{

set<int> mySet;

// 在容器中插入元素

mySet.insert(4);

// 任意位置插入一个元素

set<int>::iterator it = mySet.begin();

mySet.insert(it, 2);

// 遍历显示

for (it = mySet.begin(); it != mySet.end(); it\++)

cout << \*it << " "; // 输出：2 4

cout << endl;

return 0;

## **修改元素** ##

set的迭代器it有const修饰符,那么对它元素的修改就必然不能成功了。但是有时候遇到要修改stl set元素的问题，这个问题一般的解决方法是先erase这个元素，然后再insert，这样效率很低，所以得找更有效的方法，开始的时候编译始终通不过。如果利用const\_cast(\*it)把it映射成一个引用的对象，那么就可以对它进行修改了。更加通用的方法如下：

\#include <set>

\#include <string>

\#include <iostream>

using namespace std;

class CEmployee \{

public:

CEmployee();

~CEmployee();

const string getName() const;

void setName(const string name);

const string getTitle() const;

void setTitle(string title);

int getID() const;

void setID(int id);

private:

int m\_id;

string m\_username;

string m\_title;

\};

CEmployee::CEmployee()

CEmployee::~CEmployee()

const string CEmployee::getName() const

return m\_username;

void CEmployee::setName(const string username)

m\_username = username;

const string CEmployee::getTitle() const

return m\_title;

void CEmployee::setTitle(string title)

m\_title = title;

int CEmployee::getID() const

return m\_id;

void CEmployee::setID(int id)

m\_id = id;

class sortByID

public:

bool operator() (CEmployee const &\_A, CEmployee const &\_B) const

if (\_A.getID() < \_B.getID()) return true;

if (\_A.getID() == \_B.getID()) return \_A.getName().compare(\_B.getName()) < 0;

return false;

\};

int main()

set<CEmployee, sortByID> empIDSet; // se是雇员的set，

set<CEmployee, sortByID> ::iterator  iter;

CEmployee employeeInfo;

employeeInfo.setName("employee\_one");

employeeInfo.setTitle("employee");

employeeInfo.setID(1);

empIDSet.insert(employeeInfo);

CEmployee employeeInfo2;

employeeInfo2.setName("employee\_two");

employeeInfo2.setTitle("CFO");

employeeInfo2.setID(5);

empIDSet.insert(employeeInfo2);

CEmployee employeeInfo3;

employeeInfo3.setName("employee\_three");

employeeInfo3.setTitle("manager");

employeeInfo3.setID(3);

empIDSet.insert(employeeInfo3);

// 第一步：找到要改变的元素

iter = empIDSet.find(employeeInfo2);

if (iter != empIDSet.end())

// 第二步：拷贝这个元素

CEmployee e(\*iter);

// 第三步：删除这个元素；

empIDSet.erase(iter\++);

// 自增这个迭代器以保持它有效（参见条款9）

// 第四步：修改这个副本

e.setTitle("Corporate Deity");

// 第五步：插入新值；提示它的位置

empIDSet.insert(iter, e);

// 和原先元素的一样

//不起效果

//static\_cast<CEmployee>(\*iter).setTitle("Corporate Deity");

else

cout << " Failed/n" << endl;

for (iter = empIDSet.begin(); iter != empIDSet.end(); iter\++)

cout << iter\->getID() << " " << iter\->getName() << " " << iter\->getTitle() << endl;

return 0;

//int类型的set集合，通过先删除再插入的方式。

\#include <set>

\#include <iostream>

using namespace std;

int main()

set<int> mySet = \{ 1,2,3,4,5,6,7,8,85,94,24 \};

for (auto it = mySet.begin(); it != mySet.end(); it\++)

cout << " " << \*it;

cout << "\\n";

set<int>::iterator itr;

itr = mySet.find(8);

itr = mySet.erase(itr);

mySet.insert(itr, 10);

for (auto it = mySet.begin(); it != mySet.end(); it\++)

cout << " " << \*it;

return 0;

# **关于set的几个问题** #

（1）为何map和set的插入删除效率比用其他序列容器高？

大部分人说，很简单，因为对于关联容器来说，不需要做内存拷贝和内存移动。说对了，确实如此。set容器内所有元素都是以节点的方式来存储，其节点结构和链表差不多，指向父节点和子节点。结构图可能如下：

/ \\

B C

/ \\ / \\

D E F G

因此插入的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点也OK了。这里的一切操作就是指针换来换去，和内存移动没有关系。

（2）为何每次insert之后，以前保存的iterator不会失效？

iterator这里就相当于指向节点的指针，内存没有变，指向内存的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。相对于vector来说，每一次删除和插入，指针都有可能失效，调用push\_back在尾部插入也是如此。因为为了保证内部数据的连续存放，iterator指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时push\_back的时候，容器内部空间可能不够，需要一块新的更大的内存，只有把以前的内存释放，申请新的更大的内存，复制已有的数据元素到新的内存，最后把需要插入的元素放到最后，那么以前的内存指针自然就不可用了。特别时在和find等算法在一起使用的时候，牢记这个原则：不要使用过期的iterator。

（3）当数据元素增多时，set的插入和搜索速度变化如何？

如果你知道log2的关系你应该就彻底了解这个答案。在set中查找是使用二分查找，也就是说，如果有16个元素，最多需要比较4次就能找到结果，有32个元素，最多比较5次。那么有10000个呢？最多比较的次数为log10000，最多为14次，如果是20000个元素呢？最多不过15次。看见了吧，当数据量增大一倍的时候，搜索次数只不过多了1次，多了1/14的搜索时间而已。你明白这个道理后，就可以安心往里面放入元素了。