在初期我们接触到的vector、list、deque、queue等,这些容器都称为序列式容器,因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？
关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高
用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。
就好比一个单词对应的他应有的一个中文意思,这种一 一对应的关系,就是KV值关系
SGI-STL的键值对的定义:
template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1& a, const T2& b): first(a), second(b)
{}
};
根据应用场景的不同,STL实现了两种不同结构的管理式容器: 一个是树型结构与哈希结构。
树型结构的关联式容器主要有四种:map、multimap、set、multiset。
其这上面的四种容器都是由平衡搜索树(红黑树)作为其底层结果,容器中的元素是一个有序的序列。
可以通过文档提取重要的一下几点:
1.set存储的value值不能重复，所以可以用set进行去重
2.set存储的value值不能修改，因为value被const修饰，修改value值可能会破坏树结构（但可以删除或插入节点）
3.set中的value以弱排序的顺序进行存储，set默认弱排序是小于
4.与map/multimap不同，set只存储value而不是<key, value>的键值对，但set的底层是由<value, value>这样的键值对实现，所以插入数据不用构造键值对
5.用set的迭代器遍历容器，得到的是有序数列
6.set查找某个元素的时间复杂度为O(logN)
先来看第一点:
可以通过insert这个函数接口来证明:
#include<iostream>
#include<set>
using namespace std;
int main()
{
set<int> Set;
Set.insert(1);
cout << Set.insert(1).second << endl;;
return 0;
}
可以观察第一条的insert的返回值是pair<iterator, bool>,我们可以通过重复插入相同的值,并获取第二次插入的返回值的第二个参数
结果:
可以发现打印出的是0, 说明插入失败false!
第二点:
有没有发现不管是迭代器是const类型的 还是不是const类型的迭代器其实都是const_iterator来实现的,改不了set中储存的value值,其实要想若是能随意更改的话,其底层结构也不存在了。
第三点:
set(constructor)中:
第五点:
#include<iostream>
#include<set>
using namespace std;
int main()
{
set<int> Set;
Set.insert(2);
Set.insert(1);
Set.insert(3);
Set.insert(5);
Set.insert(6);
Set.insert(9);
Set.insert(8);
auto it = Set.begin();
while (it != Set.end())
{
cout << *it << " ";
it++;
}
return 0;
}
其实底层就是通过平衡二叉树中序遍历出的有序元素数列
在set中find一般都用来判断val是否在set实例化对象中
而没找到返回的是对象的end();
#include<iostream>
#include<set>
using namespace std;
int main()
{
set<int> Set;
Set.insert(2);
Set.insert(1);
Set.insert(3);
auto it1 = Set.find(2);
auto it2 = Set.find(4);
if (it1 != Set.end())
cout << 2 << " " << "在" << endl;
else
cout << 2 << " " << "不在" << endl;
if (it2 != Set.end())
cout << 4 << " " << "在" << endl;
else
cout << 4 << " " << "不在" << endl;
return 0;
}
#include<iostream>
#include<set>
using namespace std;
int main()
{
set<int> Set;
Set.insert(2);
Set.insert(1);
Set.insert(3);
if (Set.count(2))
cout << 2 << " " << "在" << endl;
else
cout << 2 << " " << "不在" << endl;
if (Set.count(4))
cout << 4 << " " << "在" << endl;
else
cout << 4 << " " << "不在" << endl;
return 0;
}
结果都是一样的
但是代码逻辑会更简单一点
multi-:
其意义就是set中的value所对应的关系可以是多个
#include<iostream>
#include<set>
using namespace std;
int main()
{
multiset<int> multi_Set;
multi_Set.insert(2);
multi_Set.insert(2);
multi_Set.insert(2);
multi_Set.insert(1);
multi_Set.insert(1);
multi_Set.insert(1);
multi_Set.insert(3);
multi_Set.insert(3);
for (auto& num : multi_Set)
{
cout << num << " ";
}
return 0;
}
multiset跟set没什么大区别,需要注意的是multiset中的find返回的iterator实际是中序的第一个
int main()
{
multiset<int> multi_Set;
multi_Set.insert(2);
multi_Set.insert(2);
multi_Set.insert(2);
multi_Set.insert(1);
multi_Set.insert(1);
multi_Set.insert(1);
multi_Set.insert(3);
multi_Set.insert(3);
auto it = multi_Set.find(1);
while (it != multi_Set.end() && *it == 1)
{
cout << *it << " ";
it++;
}
return 0;
}
前面的set存的是value,而map存的是键值对
map<string, int> m; //创建一个对象
m.insert(make_pair("hello", 1));
m.insert(pair<string, int>("world", 2));
上面用了两种方式插入,make_pair其实封装了pair<>的调用函数
map存储的值是键值对,pair<T1,T2>中的T1类型变量是const,T2类型的变量可以更改
map存储比较规则:
可以知道mapped_type不会参与比较,仅仅只有Key(key_type)
用map就可以统计字符串的次数
void test()
{
string arr[] = { "香蕉","梨子", "芒果",
"草莓", "苹果", "苹果",
"西瓜", "苹果", "香蕉",
"苹果", "香蕉" };
map<string, int> Map;
for (auto& str : arr)
{
auto it = Map.find(str); // 在map中查找字符串
if (it != Map.end()) // map中有这个键值对
{
it->second++;
}
else
{
Map.insert(make_pair(str, 1));
}
}
for (auto kv : count)
{
cout << kv.first << ':' << kv.second << endl;
}
}
这里count此时就能发挥作用统计次数了
void test()
{
string arr[] = { "香蕉","梨子", "芒果",
"草莓", "苹果", "苹果",
"西瓜", "苹果", "香蕉",
"苹果", "香蕉" };
map<string, int> Map;
for (auto& str : arr)
{
Map[str]++;
}
for (auto kv : Map)
{
cout << kv.first << ':' << kv.second << endl;
}
}
效果跟上面的一样
[]的原理:
简化一下
auto ret = insert(make_pair(k, mapped_type());
//ret类型是pair<iterator, bool>
return ret.first->second; //-> (这里返回的是iterator->second的引用)
multimap与map就像multiset与set一样,但是multimap没有map的operator[]重载
void test()
{
string arr[] = { "香蕉","梨子", "芒果",
"草莓", "苹果", "苹果" };
multimap<string, int> multi_Map;
for (auto& str : arr)
{
multi_Map.insert(make_pair(str, 1));
}
for (auto kv : multi_Map)
{
cout << kv.first << ':' << kv.second << endl;
}
}
