STL——关联容器操作

Posted on | In , ,

本文将针对关联容器的操作进行总结。

关联容器有两大类，map和set，一个用于索引，一个用于判断存在性。在C++中常用四个关联容器，map & unordered_map, set & unordered_set, 其中unordered表示不排序，如果没有排序需求，尽量使用unordered提升效率。

map & unordered_map

map和multimap的底层是通过红黑树实现的，而unordered_map底层为哈希表

map相关操作

插入

map的插入共有两种形式：

1
2
3
accountMap.insert(pair<int,int>(100,100));     //插入键值对，不能覆盖
accountMap.insert(map<int, int>::value_type(100, 100)); //同上
accountMap[100] = 100;            //array 方式插入，可覆盖

查找

通过键是否存在，查找键值对是否在map中

1
2
3
4
5
6
auto iter = accountMap.find(100);

if(iter != accountMap.end())
       cout<<"the item is found and value is"<<iter->second<<endl;
else
   cout<<"the item isn't found"<<endl;

删除

1
2
3
4
iter = accountMap.find(100);
accountMap.erase(iter);                  //迭代器刪除
 
int isDeleted = accountMap.erase(100);         // 用关键字刪除,删除返回1，否则返回0

Set & unordered_set

set和multiset底层采用红黑树实现，而unordered_set采用哈希表。

Set相关操作

基本操作

初始化
1
2
vector<int> ivec;
set<int> iset(ivec.cbegin(), ivec.cend());   // 利用vector初始化set
增删查
1
2
// 查找
if(iset.find(5) == iset.end())  // 没找到

其他常用操作

  • 判断两个集合交集set_intersection函数

函数模板为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1,
                                   InputIterator2 first2, InputIterator2 last2,
                                   OutputIterator result)
{
  while (first1!=last1 && first2!=last2)
  {
    if (*first1<*first2) ++first1;
    else if (*first2<*first1) ++first2;
    else {
      *result = *first1;
      ++result; ++first1; ++first2;
    }
  }
  return result;
}

使用注意事项：待比较的两个集合必须先排序，才能正确判断交集。

例题：LeetCode 350

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

1
2
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]

示例 2:

1
2
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    vector<int> ret;
    std::sort(nums1.begin(), nums1.end());
    std::sort(nums2.begin(), nums2.end());
    std::set_intersection(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), std::back_inserter(ret)); // back_inserter, 使用push_back()添加相应元素
    return ret;
}
};

扩展操作

自定义哈希函数

在使用unordered_set和unordered_map时，我们可以使用自定义哈希函数，一个自定义哈希函数编写方式如下：

1
2
3
4
5
6
7
8
struct KeyHash {
    std::size_t operator()(const Key& k) const
    {
        return std::hash<std::string>()(k.first) ^
            (std::hash<std::string>()(k.second) << 1);  //采用stl库创建hash函数 ，前面的括号代表创建一个临时对象，尽量不要这么写，应当改为std::hash<std::string>{}(k.first);

    }
};
0%