【C++】STL库set容器

1. Set的定义：set s1 = {1,6,-3}; // 内部自动递增排序

set < T > name;
set< int> name;
set< double> name;
set< char> name;
set< Node> name;//Node是结构体类型
(1)定义和写法和vector基本一样，同样typename可以是任何基本类型，结构体，STL容器类型。
(2)同样，typename是容器的时候，>>后要加空格，避免编译器当成位运算出错。

1. Set：集合，一个内部自动有序而且不重复元素的容器。
2. set内的元素，自动递增排序，并且去重。
3. set只能通过迭代器iterator访问；
4. 定义和写法和vector基本一样，<数据类型>以是任何基本类型；
5. iterator 不支持 “+”运算符重载，但支持++、- -；

   
   

1、构造函数

1. set < T > s; // 创建空集合
2. set < T > s1=s; // 拷贝构造函数
   set < T > s1(s);

#include "stdafx.h"
#include <iostream>
#include <set>
using namespace std;

int main() {
	//------------------ set 的定义
	set <int> s1 = {1,6,-3}; // 内部自动递增排序
	for (auto it = s1.begin(); it != s1.end(); ++it) {
		cout << *it << " "; // -3 1 6
	}


	//------------------ set() 构造函数
	set <char> s2;
	cout << s2.size() << endl; // 0

	
	//------------------  拷贝构造函数
	set <char> s3;
	s3.insert('a');
	s3.insert('b');
	s3.insert('1');
	s3.insert('@');

	set<char> s4(s3); // set<char> s4=s3;
	for (auto it = s4.begin(); it != s4.end(); ++it) {
		cout << *it << " "; // 1 @ a b
	}


	return 0;
}

2、增

2.1 insert() 去重+排序

insert(x)：将x插入set容器中，并且自动递增排序和去重。时间复杂度为O(logN)，N为元素个数。

2.2 emplace() 去重+排序

emplace(x)：将x插入set容器中，并且自动递增排序和去重。

2.3 代码演示

int main() {
	//------------------ insert( ) 插入——去重+排序
	set <char> s1;
	s1.insert('a');
	s1.insert('a');
	s1.insert('b');
	s1.insert('1');
	s1.insert('a');
	s1.insert('@');
	s1.insert('a');
	for (auto it = s1.begin(); it != s1.end(); ++it) {
		cout << *it << " "; // 1 @ a b
	}


	//------------------ emplace()  去重 + 排序
	set <int> s2;
	s2.emplace(99);
	s2.emplace(1);
	s2.emplace(0);
	s2.emplace(-5);
	s2.emplace(0);
	s2.emplace(33);
	s2.emplace(0);
	s2.emplace(25);
	s2.emplace(0);
	for (auto it = s2.begin(); it != s2.end(); ++it) {
		cout << *it << " "; // -5 0 1 25 33 99
	}

	return 0;
}

3、删

3.1 erase()函数

1. erase(x)：删除单个元素，时间复杂度为O(logN)。返回值是 void，调用 erase 之后，当前迭代器会失效，无法再用于获取下一个迭代器。因此需要 erase 之前就获取指向下一个元素的迭代器。
2. erase(a,b);删除左闭右开区间内[a,b)的元素，时间复杂度为O(b-a)。返回值是返回值是指向删除元素下一个元素的迭代器。

3.1.1 erase() ——list与vector

set只能通过迭代器iterator访问；
list与vector中的erase用法相同，它们的 erase 函数会返回指向下一个元素的迭代器，因此在遍历时，只需要 it = c.erase(it); 即可。

vector<int>::iterator it = vec.begin();  
for (; it != vec.end();)  
{  
    if (*it == 10) {  
        it = vec.erase(it);  
    }  
    else {  
        ++it;  
    }  
} 

3.1.2 erase() ——map与set

map与set中的erase用法相同，它们的 erase 函数返回值是 void，调用 erase 之后，当前迭代器会失效，无法再用于获取下一个迭代器。因此需要 erase 之前就获取指向下一个元素的迭代器。

map<int, int>::iterator it = m.begin();  
for (; it != m.end();)  
{  
    if (it->fist == 10) {  
        m.erase(it++);  
    }  
    else {  
        ++it;  
    }  
}

3.2 clear()函数

clear()：用来清空set所有元素，时间复杂度为O(N)

3.3 代码演示

#include "stdafx.h"
#include <iostream>
#include <set>
using namespace std;

int main() {
	//------------------ erase(x) ( ) 删除x
	set <char> s1;
	s1.insert('a');
	s1.insert('a');
	s1.insert('b');
	s1.insert('1');
	s1.insert('a');
	s1.insert('@');
	s1.insert('d');
	s1.insert('3');
	s1.insert('f');
	s1.insert('-');

	for (auto it = s1.begin(); it != s1.end(); ++it) {
		cout << *it << " "; // - 1 3 @ a b d f
	}

	int next = s1.erase('@'); 
	cout << "next="<< next << endl; // next=1

	for (auto it = s1.begin(); it != s1.end(); ++it) {
		cout << *it << " "; //  - 1 3 a b d f
	}



	//------------------ erase(first，last) ( ) 删除x
	set<int> s2 = {1,2,3,4,5,6};
	auto it = ++s2.begin();
	auto it1 = --s2.end();
	auto itorReturn = s2.erase(it, it1);
	cout << "itorReturn=" << *itorReturn << endl; // itorReturn=6 返回值是指向删除元素下一个元素的迭代器
	for (auto it2 = s2.begin(); it2 != s2.end(); ++it2) {
		cout << *it2 << " "; // 1 6

	return 0;
}

4、改

4.1 swap（）交换

#include "stdafx.h"
#include <iostream>
#include <set>
using namespace std;

int main() {
	//------------------ swap( ) 交换
	set <char> s1;
	s1.insert('a');
	s1.insert('a');
	s1.insert('b');
	s1.insert('1');
	s1.insert('a');

	set<char> s2;
	s2.insert('@');
	s2.insert('d');
	s2.insert('3');
	s2.insert('f');
	s2.insert('-');

	s2.swap(s1);

	for (auto it = s1.begin(); it != s1.end(); ++it) {
		cout << *it << " "; // - 3 @ d f
	}

	for (auto it = s2.begin(); it != s2.end(); ++it) {
		cout << *it << " "; //  1 a b
	}

	return 0;
}

5、查

5.1 for循环+迭代器 （遍历）

set只能通过迭代器iterator访问，因为除了vector和string之外的STL的容器都不支持以下标的方式访问。

5.2 find()函数

find(value)：查找值为value的元素，返回它的迭代器。时间复杂度为O(logN),N为元素个数。

int main() {
	//------------------ 1. 迭代器遍历
	set <char> s1;
	s1.insert('a');
	s1.insert('a');
	s1.insert('b');
	s1.insert('1');
	s1.insert('a');
	s1.insert('@');
	s1.insert('d');
	s1.insert('3');
	s1.insert('f');
	s1.insert('-');

	for (auto it = s1.begin(); it != s1.end(); ++it) {
		cout << *it << " "; // - 1 3 @ a b d f
	}


	//------------------ 2. find (val ) 查找val的迭代器
	set<int> s2 = {1,2,2,2,2,3,4,5,6,2};
	auto it = s2.find(2);
	cout << "val的迭代器指向的元素值是："<< *it << endl; //  val的迭代器指向的元素值是：2
	
	return 0;
}

6、大小

6.1 size()函数

用来获得set内元素的个数，时间复杂度为O(1)

6.2 count（val）查个数

返回元素在集合中出现的次数（去重后的结果）

6.3 max_size() 最大容量

代码演示

int main() {
	set <char> s1;
	s1.insert('a');
	s1.insert('a');
	s1.insert('b');
	s1.insert('1');
	s1.insert('a');
	s1.insert('@');
	s1.insert('d');
	s1.insert('3');
	s1.insert('f');
	s1.insert('-');


	cout << "size=" << s1.size() << endl; // size=8
	cout << "max_size=" << s1.max_size()<<endl; // max_size=268435455
	cout << "count=" << s1.count('a') << endl; // count=1
	cout << "count=" << s1.count('@') << endl; // count=1
	cout << "count=" << s1.count('!') << endl; // count=0

	return 0;
}

7、empty（）判空