目录
1.关联式容器
2.键值对
3.树形结构的关联式容器
4.set
5.set的特点
6.set的使用
常用接口的使用:
1.insert
2.find
3.erase
4.operator=
7.multiset
1.关联式容器
与vector,list,queue等底层为线性序列的数据结构的序列式容器有着不同,关联式容器里面存储的是<key, value>结构的键值对,在数据检索时比序列式容器效率更高。与之相对,序列式容器中的元素是按照它们在容器中的位置来顺序保存和访问的。
2.键值对
用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量key和value,key代
表键值,value表示与key对应的信息。比如:以一个人的名字为key值,再将他的手机号当作value值,这样我们就可以通关一个人的名字找到他对应的手机号。
3.树形结构的关联式容器
树形结构的关联式容器主要有四种:map, set, multimap, multiset。这四种容器的共同点是:使用平衡搜索树(红黑树)作为其底层结果,容器中的元素是一个有序的序列。
以下将主要介绍set容器。
4.set
T :set中存放元素的类型,实际在底层存储<value,value>的键值对。
Compare :set中元素默认按照小于来比较。
Alloc :set中元素空间的管理方式,使用STL提供的空间配置器管理。
5.set的特点
1. 与map/multimap不同,map/multimap中存储的是真正的键值对<key, value>,set中只放
value,但在底层实际存放的是由<value, value>构成的键值对。
2. set中插入元素时,只需要插入value即可,不需要构造键值对。
3. set中的元素不可以重复(因此可以使用set进行去重)。
4. 使用set的迭代器遍历set中的元素,可以得到有序序列
5. set中的元素默认按照小于来比较。
6. set中查找某个元素,时间复杂度为:。
7. set中的元素不允许修改,但是可以从容器中插入或删除它们。。
8. set中的底层使用二叉搜索树(红黑树)来实现。
6.set的使用
常用接口的使用:
1.insert
range:[first,last) 范围包含first和last之间的所有元素,包括first指向的元素,但不包括last指向的元素。
因为set中的元素都是唯一的,所以插入操作会检查每个插入的元素是否与容器中已经存在的元素相等,如果相等,则不插入该元素,并返回该元素的迭代器(如果该函数有返回值)。
在内部,设置容器将其所有元素按照其比较对象指定的标准排序(默认按照小于)。元素总是按照这种顺序插入到其各自的位置。
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> myset;
set<int>::iterator it;
pair<std::set<int>::iterator, bool> ret;
// 设置初始值
for (int i = 1; i <= 5; ++i) myset.insert(i * 10); // set: 10 20 30 40 50
ret = myset.insert(20); // 已有20,则不再插入,返回该元素迭代器
if (ret.second == false) it = ret.first; // it现在指向元素20
myset.insert(it, 25); // 最高效率插入
myset.insert(it, 24); // 最高效率插入
myset.insert(it, 26); // 未最高效率插入(默认按小于)
int myints[] = { 5,10,15 }; // 10已经在则不插入
myset.insert(myints, myints + 3);
cout << "myset contains:";
for (it = myset.begin(); it != myset.end(); ++it)
std::cout << ' ' << *it;
cout << endl;
return 0;
}
2.find
在容器中搜索与val相等的元素,如果找到就返回一个指向该元素的迭代器,否则返回一个迭代器set::end。
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> myset;
set<int>::iterator it;
// 设置初始值
for (int i = 1; i <= 5; i++) myset.insert(i * 10); // set: 10 20 30 40 50
it = myset.find(20);
myset.erase(it);
myset.erase(myset.find(40));
cout << "myset contains:";
for (it = myset.begin(); it != myset.end(); ++it)
cout << ' ' << *it;
cout << endl;
return 0;
}
3.erase
从set容器中移除单个元素或一系列元素[first,last)。
range:[first,last)该范围包括first和last之间的所有元素,包括first指向的元素,但不包括last指向的元素。
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> myset;
set<int>::iterator it;
// 插入一些值
// 10 20 30 40 50 60 70 80 90
for (int i = 1; i < 10; i++) myset.insert(i * 10);
it = myset.begin();
++it; // "it" 现在指向元素20
myset.erase(it);
myset.erase(40);
it = myset.find(60);
myset.erase(it, myset.end());
std::cout << "myset contains:";
for (it = myset.begin(); it != myset.end(); ++it)
cout << ' ' << *it;
cout << endl;
return 0;
}
4.operator=
将新内容赋值给容器,替换当前内容。
#include <iostream>
#include <set>
using namespace std;
int main()
{
int myints[] = { 12,82,37,64,15 };
set<int> first(myints, myints + 5); // 用5个整数设置
set<int> second; // 空集
second = first; // 现在second包含5个整数
first = set<int>(); // first变为空
cout << "Size of first: " << int(first.size()) << endl;
cout << "Size of second: " << int(second.size()) << endl;
return 0;
}
7.multiset
1. multiset是按照特定顺序存储元素的容器,其中元素是可以重复的。
2. 在multiset中,元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成
的键值对,因此value本身就是key,key就是value,类型为T). multiset元素的值不能在容器
中进行修改(因为元素总是const的),但可以从容器中插入或删除。
3. 在内部,multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则
进行排序。
4. multiset容器通过key访问单个元素的速度( )通常比unordered_multiset容器慢,但当使用迭
代器遍历时会得到一个有序序列。
5. multiset底层结构为二叉搜索树(红黑树)。
注意:multiset与set的区别是multiset中的元素可以重复。