文章目录
-
-
-
- 1.关联式容器
- 2.树形结构的容器
-
- 2.1.set的基本介绍
- 2.2.set的接口使用
- 2.3.练习:两个数组的交集
- 2.4.map的基本介绍
- 2.5.map的接口使用
-
-
1.关联式容器
STL中，容器可以分为序列式容器和关联式容器；常见的vector、list、dequeue等都是序列式容器，它们底层使用线性序列的数据结构，而关联式容器，存储的是<key, value>结构的键值对；在数据检索时比序列式容器效率更高，因为它们底层用的是红黑树这样的数据结构。常见的关联式容器如：set、map、multiset和multimap等。
2.树形结构的容器
关于set和map想要更加深入理解可以查看权威文档：set，map
2.1.set的基本介绍
set的模板参数列表
template < class T,
class Compare = less<T>,
class Alloc = allocator<T>
> class set;
T: set中存放元素的类型，实际在底层存储<value, value>的键值对。
Compare：set中元素默认按照小于的方式比较
Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理
- set的底层使用的是二叉搜索树（红黑树）存储，二叉搜索树中的中序遍历是有序的，而set迭代器遍历set中的元素，也可以得到有序序列；也因为是底层用的红黑树，查找的时间复杂度是O（log_2 (N））
- set中只放value，但在底层实际存放的是由<value, value>构成的键值对；但在set中插入元素时，只需要插入value即可，不需要构造键值对
- set中的元素不可以重复(因此可以使用set进行去重)；set中的元素也不允许修改，但是可以插入和删除的方式改变它。
2.2.set的接口使用
构造函数：
explicit set (const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
构造一个空的没有存放元素的set对象。
template <class InputIterator>
set (InputIterator first, InputIterator last,
const key_compare& comp = key_compare(),
const allocator_type& = allocator_type());
使用[first, last)区间中的元素构造set。
set (const set& x)
使用拷贝构造
代码是示例：
int test1()
{
// 1.定义无参构造
set<int> first;
// 2.[first,last)区间构造
int arr[] = { 1,1,2 };
size_t length = sizeof(arr) / sizeof(arr[0]);
set<int> second(arr, arr + length);
// 3.拷贝构造
set<int> third(second);
return 0;
}
迭代器：
返回set中起始位置元素的迭代器： iterator begin() noexcept; 返回set中最后一个元素后面的迭代器 iterator end() noexcept; ...
代码示例：
int test2()
{
// 也可验证一下，不能存重复的数据，去重！
int arr[] = { 1,1,2 };
size_t length = sizeof(arr) / sizeof(arr[0]);
set<int> first(arr, arr + length);
set<int>::iterator it = first.begin();
for (;it != first.end();++it)
{
cout << *it << " " << endl;
}
return 0;
}
容量接口：
bool empty() const noexcept; 功能：检测set是否为空，空返回true，否则返回false size_type size() const noexcept; 功能：返回set中有效元素的个数
代码示例：
int test3()
{
int arr[] = { 1,1,2 };
size_t length = sizeof(arr) / sizeof(arr[0]);
set<int> first(arr, arr + length);
cout << "初始数组长度：" << length << endl;
cout << "set是否为空：" << first.empty() << endl;
cout << "set的有效长度：" << first.size() << endl;
return 0;
}
修改操作：
pair<iterator,bool> insert (const value_type& val) 功能：插入数据 说明：在set中插入元素x，实际插入的是<x, x>构成的键值对，如果插入成功，返回<该元素在set中的 位置，true>,如果插入失败，说明x在set中已经存在，返回<x在set中的位置，false> size_type erase (const value_type& val); 功能：删除set中值为x的元素，返回删除的元素的个数？ void erase ( iterator position ) 功能：删除set中position位置上的元素 void clear () 功能：将set中的元素清空 iterator find ( const key_type& x ) const 功能：返回set中值为x的元素的位置,如果找不到返回结束的位置？验证一下！ size_type count ( const key_type& x ) const 功能：返回set中值为x的元素的个数？
代码示例：
int test4()
{
int arr[] = { 1,1,2,3 };
size_t len = sizeof(arr) / sizeof(arr[0]);
set<int> first(arr, arr + len);
auto ret = first.insert(6);
if (ret.second == true)
cout << "成功插入元素：" << *ret.first << endl;
cout << first.erase(2) << endl;
set<int>::iterator it = first.find(3);
cout << "输出find查找的内容：" << *it << endl;
if (first.find(50) == first.end())
cout << "元素不存在！" << endl;
return 0;
}
2.3.练习:两个数组的交集
题目描述：
给定两个数组
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2]
解题思路1：
1.求交集重复的元素就不用重复计算，用set去一下重
2.遍历其中一个set1，通过set2.find()函数，查找set1中的元素是否在set2
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
{
vector<int> ret;
set<int> first(nums1.begin() ,nums1.end());
set<int> second(nums2.begin(), nums2.end());
for(auto it: first)
{
if(second.find(it) != second.end())
{
ret.push_back(it);
}
}
return ret;
}
};
这个方法，注意find如果查找不到返回end位置！时间复杂度O(log_2(N))*O(N)，遍历是O(N)，查找是O(log_2(N))！
解题思路2：
1.求交集重复的元素就不用重复计算，用set去一下重
2.利用set的使用迭代器遍历是有序的！
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
{
vector<int> ret;
set<int> first(nums1.begin() ,nums1.end());
set<int> second(nums2.begin(), nums2.end());
auto firstIt = first.begin();
auto secondIt = second.begin();
while(firstIt != first.end() && secondIt !=second.end())
{
if(*firstIt < *secondIt)
{
firstIt++;
}
else if(*firstIt > * secondIt)
{
secondIt++;
}
else
{
ret.push_back(*firstIt);
firstIt++;
secondIt++;
}
}
return ret;
}
};
2.4.map的基本介绍
map的模板参数说明
template < class Key,
class T,
class Compare = less<Key>,
class Alloc = allocator<pair<const Key,T> >
> class map;
key: 键值对中key的类型
T： 键值对中value的类型
Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较；如果无法比较时(自定义类型)，需要用户按照函数指针或者仿函数来传递比较规则
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器
- map底层是实现是红黑树
- map插入到键值对是，typedef pair<const key, T> value_type;
- 在内部，map中的元素总是按照键值key进行比较排序的，
- map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
- 关于[]和at函数：当key不存在时，operator[]用默认value与key构造键值对然后插入，返回该默认value，at()函数直接抛异常。
2.5.map的接口使用
构造器
explicit map (const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());
无参构造
...
代码示例：
int main()
{
map<string, string> first;
first.insert({"apple","苹果" });
first.insert({ {"Watermelon","西瓜"},{"lichee","荔枝"} });
first.insert(pair<string, string>("banana", "香蕉"));
first["pitaya"] = "火龙果";
for (auto e : first)
{
cout << e.second << " ";
}
cout << endl;
cout << first["apple"] << endl;
return 0;
}