STL:关联式容器 | set的基本使用 | map的基本使用

文章目录

        • 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提供的空间配置器管理

  1. set的底层使用的是二叉搜索树(红黑树)存储,二叉搜索树中的中序遍历是有序的,而set迭代器遍历set中的元素,也可以得到有序序列;也因为是底层用的红黑树,查找的时间复杂度是O(log_2 (N))
  2. set中只放value,但在底层实际存放的是由<value, value>构成的键值对;但在set中插入元素时,只需要插入value即可,不需要构造键值对
  3. 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.练习:两个数组的交集

题目描述:

给定两个数组 nums1nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序

输入: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:通过空间配置器来申请底层空间,不需要用户传递,除非用户不想使用标准库提供的空间配置器

  1. map底层是实现是红黑树
  2. map插入到键值对是,typedef pair<const key, T> value_type;
  3. 在内部,map中的元素总是按照键值key进行比较排序的,
  4. map支持下标访问符,即在[]中放入key,就可以找到与key对应的value。
  5. 关于[]和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;
}