网站付费功能描述,描述对于营销型网站建设很重要飘红效果更佳,广告销售如何寻找客户,大丰做网站价格文章目录 一、关联式容器二、pair键值对三、set1. set的介绍2. set的部分接口以及应用3. count4. lower_bound和upper_bound5. equal_range6. multiset容器 四、map1. map的介绍2. map的一些常见接口以及使用3. map的[]运算符重载4. 使用map改进一些题5. multimap容器 五、map和… 文章目录 一、关联式容器二、pair键值对三、set1. set的介绍2. set的部分接口以及应用3. count4. lower_bound和upper_bound5. equal_range6. multiset容器 四、map1. map的介绍2. map的一些常见接口以及使用3. map的[]运算符重载4. 使用map改进一些题5. multimap容器 五、map和set相关力扣题总结 一、关联式容器
STL中的部分容器比如vector、list、deque、forward_list(C11)等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身。
那什么是关联式容器它与序列式容器有什么区别
关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是key, value结构的键值对在数据检索时比序列式容器效率更高
二、pair键值对
用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息
stl里面对于pair的定义是这样的
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){}
};pair有三种构造函数不难看出分别是无参的构造拷贝构造以及通过两个值来进行构造 除了三种构造函数以外它还有一种方式也可以生成pair对象。这个不是一个成员函数所以可以直接使用。 如上的一些构造函数的使用将在map中进行演示 三、set
1. set的介绍
如下图所示
我们可以注意到它的模板参数是要比其他容器多一个的这个容器我们也可以看到是一个仿函数。我们使用优先级队列的时候也用过这个仿函数 集合是按照特定顺序存储唯一元素的容器。
在一个集合中元素的值也标识它(值本身就是键类型为 T)并且每个值必须是唯一的。集合中元素的值在容器中不能修改(元素总是 const 类型的)但是可以从容器中插入或删除元素。
在内部集合中的元素总是按照其内部比较对象(类型为 Compare )指示的特定严格弱排序标准排序。
在通过键访问单个元素时set 容器通常比 unordered_set 容器慢但是它们允许基于次序对子集进行直接迭代。
集合通常以二叉搜索树的形式实现。这颗二叉搜索树是红黑树。
set其实就相当于key模型的二叉搜索树
注意set里面的值是不可以被修改的它实现这一点的原理就是将迭代器和const迭代器都是const迭代器没有任何区别。 2. set的部分接口以及应用 可以注意到一共有三个构造函数第一个是全缺省的默认构造函数第二个是迭代器区间构造第三个是拷贝构造。
不过这个拷贝构造的代价比较大因为它是一个树的拷贝而且析构也一样有很大的代价。
还有一个接口是insert 这里的value_type就是T 还有很多接口其实看一眼就大概知道啥意思 比如如下代码可以简单的测试一下代码
void test_set1()
{setint s;s.insert(1);s.insert(5);s.insert(2);s.insert(2);s.insert(2);s.insert(2);s.insert(4);s.insert(4);s.insert(4);s.insert(3);setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;
}
int main()
{test_set1();return 0;
}我们可以发现set可以自动去重和排序
而它的去重原理就是一个值已经有了我们就不插入即可 同时我们也可以试一下set的删除 auto pos s.find(3);s.erase(pos);s.erase(4);for (auto e : s){cout e ;}cout endl;如上有演示了两种删除从表面来看看上去好像没有什么大的区别。我们可以认为下面的是通过上面的进行实现的。
不过在find中如果没有找到的话是会直接报错的。 而下面如果没有找到是什么也不会发生的 不过我们可以加一个判断来解决这个问题 这是因为find找不到会返回一个end迭代器导致的 在容器中搜索与val等效的元素如果找到则返回一个迭代器否则返回一个迭代器给set::end。
但是我们知道算法库里面也有一个find这个find似乎也能完成这个操作 其实这两个find是存在一定的差异的set里面的find是根据二叉搜索树的性质来进行查找的其实是红黑树效率更优时间复杂度为O(logN)而算法库里面的find是一个一个查找的时间复杂度为O(N)。
3. count count的作用是给一个值然后返回它出现了几次。不过因为set容器里面的值是唯一的所以一个元素在这里面返回1否则返回0
如下的代码可以演示find和count寻找一个数据的使用
void test_set2()
{setint s;s.insert(1);s.insert(5);s.insert(2);s.insert(4);s.insert(4);s.insert(3);setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;if (s.find(5) ! s.end()){cout 找到了 endl;}if (s.count(5)){cout 找到了 endl;}
}
int main()
{test_set2();return 0;
}4. lower_bound和upper_bound 返回迭代器到下界
返回一个迭代器该迭代器指向容器中的第一个元素该元素不被认为位于val之前(即它要么等价要么在val之后)。
该函数使用其内部比较对象(key_comp)来确定这一点并返回一个迭代器指向key_comp(element,val)将返回false的第一个元素。
如果用默认比较类型(less)实例化set类则该函数返回一个指向不小于val的第一个元素的迭代器。
类似的成员函数upper_bound具有与lower_bound相同的行为只是set包含一个与val等效的元素:在这种情况下lower_bound返回一个指向该元素的迭代器而upper_bound返回一个指向下一个元素的迭代器。 返回迭代器到上界
返回一个迭代器该迭代器指向容器中被认为在val之后的第一个元素。
该函数使用其内部比较对象(key_comp)来确定这一点并返回一个迭代器指向key_comp(val,element)将返回true的第一个元素。
如果用默认比较类型(less)实例化set类则该函数返回指向第一个大于val的元素的迭代器。
类似的成员函数lower_bound具有与upper_bound相同的行为只是set包含一个与val等效的元素:在这种情况下lower_bound返回一个指向该元素的迭代器而upper_bound返回一个指向下一个元素的迭代器。
我们可以使用这段代码来进行验证
void test_set3()
{std::setint myset;std::setint::iterator itlow, itup;for (int i 1; i 10; i) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90itlow myset.lower_bound(30); itup myset.upper_bound(60); myset.erase(itlow, itup); // 10 20 70 80 90for (auto e : myset){cout e ;}cout endl;
}
int main()
{test_set3();return 0;
}lower_bound和upper_bound一个设置为一个设置为。这样刚好可以将我们输入值所处的区间进行控制刚好满足左闭右开。无论是构造也好删除也好插入也好都是刚好十分方便的。
5. equal_range 获取相等元素的范围
返回一个范围的边界该范围包括容器中与val等效的所有元素。
因为set容器中的所有元素都是唯一的所以返回的范围最多只包含一个元素。
如果没有找到匹配项则返回的范围长度为0两个迭代器都指向容器内部比较对象(key_comp)认为在val之后的第一个元素。
如果容器的比较对象自反性地返回false(即无论元素作为参数传递的顺序如何)则认为集合中的两个元素相等。
该函数返回一个pair其成员pair::first是范围的下界(与lower_bound相同)pair::second是上界(与upper_bound相同)。
成员类型iterator和 const_iterator是指向元素的双向迭代器类型。
我们可以看这段代码
void test_set4()
{std::setint myset;for (int i 1; i 5; i) myset.insert(i * 10); // myset: 10 20 30 40 50std::pairstd::setint::const_iterator, std::setint::const_iterator ret;ret myset.equal_range(35);std::cout the lower bound points to: *(ret.first) \n;std::cout the upper bound points to: *(ret.second) \n;myset.erase(ret.first, ret.second);for (auto e : myset){cout e ;}cout endl;
}
int main()
{test_set4();return 0;
}这是因为这段区间内并不存在35所以会返回一个比他大的数值所在的区间。且这两个是相等的。
如果我们要找的是等于30的区间的话就是这样的 由于set里面没有重复元素所以其实只能找到那一个元素从这个容器的角度来看似乎这个寻找相等区间的函数并没有什么太大的用处还不如find呢
其实关于这些函数主要还是为了另外一个容器设置的
6. multiset容器
在库里面set还有一种是multiset。 这个容器是是一个允许键值冗余的一个容器其接口和set一模一样。所以我们可以认为刚刚的关于一些范围的容器都是为了它而设计的
我们可以使用一下这个容器
void test_set5()
{multisetint s;s.insert(1);s.insert(5);s.insert(2);s.insert(2);s.insert(2);s.insert(2);s.insert(4);s.insert(4);s.insert(4);s.insert(3);multisetint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;//找到的是中序的第一个2即排序的第一个2auto pos s.find(2);while (pos ! s.end()){cout *pos ;pos;}cout endl;cout s.count(2) endl;auto ret s.equal_range(2);cout *ret.first *ret.second endl;s.erase(ret.first, ret.second);for (auto e : s){cout e ;}cout endl;
}
int main()
{test_set5();return 0;
}关于上面这段代码作出如下解释
首先这个是一个允许键值冗余的容器所以相比于set就不会进行去重了。其余的功能和set是一样的。
由于find找的是中序的第一个2所以我们从找到的那个开始进行打印就会将从2以后的全部打印
其次我们的count也就可以计算出2的数量了。之前的在set中的count由于set天然的去重了所以只能用于检测是否存在某个值而现在的话就可以统计数量了。
然后关于我们的找某个数的范围这个函数也就可以查找2的所有范围了。于是我们就可以删除掉2所在的区间了。
所以count和equal_range这两个函数对于multiset容器而言更有意义。
四、map
1. map的介绍
如下所示这个容器一共有四个参数Key和T 映射是关联容器存储由键值和映射值按照特定顺序组合而成的元素。
在map中键值通常用于排序和唯一标识元素而映射值存储与该键相关联的内容。键和映射值的类型可能不同组合在成员类型value_type中这是一种组合了两者的pair类型:
typdef pairconst Key, T value_type;在内部map中的元素总是按照键进行严格的弱排序排序标准由内部比较对象(类型为Compare)表示。
在通过键访问各个元素时Map容器通常比unordered_map容器慢但它们允许根据键的顺序直接迭代子集。
映射后的值可以通过方括号运算符((operator[])直接访问。
映射通常以二叉查找树的形式实现。
这里的模板参数中Key和T类似于key-val模型中的key和val的模板参数。这些模板类型都被define为了key_type和mapped_type。
同时还有value_type就相当于将这两个给结合到一块放到了pair容器中。方便我们操控里面的数据并且里面的key_type给的是const类型这就说明了map中的key是不可以被修改的但是value是可以被修改的 2. map的一些常见接口以及使用
首先来看下insert这个函数有三个重载后两个是使用迭代器区间进行插入的。第一个是直接插入一个value_type类型的数据。value_type其实就是键值对因为他是key-val模型的. 通过插入新元素扩展容器实际上是插入元素的数量增加了容器的大小。 因为map中元素的键是唯一的所以插入操作会检查每个被插入元素的键是否与容器中已经存在的元素的键相等如果相等则不插入该元素并返回一个指向该元素的迭代器(如果该函数有返回值)。 有关允许重复元素的类似容器请参阅multimap。 在map中插入元素的另一种方法是使用成员函数map::operator[]。 在内部map容器按照比较对象指定的标准对所有元素的键进行排序。元素总是按照这种顺序插入到其各自的位置。 这些参数决定了有多少个元素被插入以及它们被初始化到哪些值 在这里我们可能会好奇的是为什么我们插入的值必须且最好是pair类型的呢将这两个数据连接到一起有什么好处吗?而我们在实现key-val模型的二叉搜索树的时候却不需要呢其实这是因为我们的二叉搜索树并没有去实现迭代器。我们如果要写迭代器一定会涉及到这个迭代器的解引用问题。而此时我们的key-val模型里面有两种数据而c并不支持返回多个参数所以只能将这两个数据给合并起来从而得以实现。 对于这个函数的返回值他返回的也是一个pair类型的对象。 如果插入的时候key已经在树里面那么返回pair树里面key的迭代器false 如果插入的时候key并未在树里面那么返回pair新插入key的迭代器true 所以insert从某种程度上也具有了查找的功能 如下代码所示该段代码演示了我们对map里面插入数据的几种用法我们可以直接传一个pair对象过去也可以传pair的匿名对象也可以使用make_pair函数来进行当然我们可能会认为make_pair函数要通过调用一个函数来进行创建对象对否开销有点大其实不是的在这里编译器会直接将这个变成内联函数进行优化实际效率相当于直接传入一个对象。除了前面三种以外C11还支持了多参数的构造函数隐式类型转换。所以我们可以直接使用多参数的构造函数隐式类型转换。
上面几种方式都是非常不错的但是比较建议使用make_pair函数来创建。这个比较简洁且有的C编译器如果不支持C11的话这个函数也是可以直接使用的。
在map里面我们取出的数据都是pair类型的这是因为C只能返回一个值不能返回多个值。所以我们必须使用pair对象进行返回。然后C也不支持pair的流插入和流提取因为并没有进行重载。所以我们需要解引用后拿到的只是一个结构体我们还需要在访问里面的值。或者我们可以直接使用-也是很方便的。
void test_map1()
{mapstring, string dict;pairstring, string kv1(insert, 插入);dict.insert(kv1);dict.insert(pairstring, string(sort, 排序));dict.insert(make_pair(remove, 改革));dict.insert({ process,过程 });//C11 多参数的构造函数隐式类型转换mapstring, string::iterator it dict.begin();while (it ! dict.end()){cout (*it).first (*it).second endl;cout it-first it-second endl;it;}for (const auto e : dict){cout e.first e.second endl;}
}int main()
{test_map1();return 0;
}还需要注意的是如果插入的时候key相同但是val不相同是不会插入进去的也不会覆盖进去的。即插入过程中只比较key。key相同就不插入了。 上面是关于map的一些插入接口还有一些接口是删除接口。也比较常见三种删除分别是直接删除某个迭代器位置的删除或者给一个key去删除注意不是val只需要一个key就可以删除了。第三种就是删除一个迭代器区间。 我们也可以注意到查找和删除都只与key有关系与其他无关。 还有如findcount这些接口也都是属于set的设计十分类似的 获取元素的迭代器 在容器中搜索键值等于k的元素如果找到则返回到该元素的迭代器否则返回到map::end的迭代器。 如果容器的比较对象反射返回false则认为两个键是等效的(即无论元素作为参数传递的顺序如何)。 另一个成员函数map::count可以用来检查特定键是否存在。 如果找到具有指定键的元素则返回该元素的迭代器否则返回map::end。 如果map对象是const限定的该函数返回一个const_iterator对象。否则它返回一个迭代器。 计算具有特定键的元素数量 在容器中搜索键等于 k 的元素并返回匹配的数量。 由于 map 容器中的所有元素都是唯一的因此该函数只能返回 1(如果找到元素)或 0(否则)。 如果容器的 comparison 对象反射返回 false则认为两个键是等效的(即无论作为参数传递的键的顺序如何)。 3. map的[]运算符重载
当我们使用map的insert接口和find接口的时候我们可以来实现在之前二叉搜索树中的统计水果个数的代码。
void test_map2()
{string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (auto e : arr){mapstring, int::iterator pos countMap.find(e);if (pos countMap.end()){countMap.insert(make_pair(e, 1));}else{pos-second;}}mapstring, int::iterator it countMap.begin();while (it ! countMap.end()){cout it-first : it-second endl;it;}
}int main()
{test_map2();return 0;
} 但是事实上我们可以将代码变得更加简洁。
我们来看一下map的[]运算符重载 访问元素 如果k与容器中某个元素的键匹配则该函数返回对其映射值的引用。 如果k与容器中任何元素的键不匹配则该函数用该键插入一个新元素并返回对其映射值的引用。注意这总是将容器的大小增加1即使没有将映射值赋给元素(元素是使用其默认构造函数构造的)。 类似的成员函数map::at在具有键的元素存在时具有相同的行为但在不存在时抛出异常。 调用此函数相当于: (*((this-insert(make_pair(k,mapped_type()))).first)).second简而言之就是给一个key如果这个key在map中存在返回它的val如果不存在那么就创建一个pair对象插入进去这个pair对象的first是key,pair中的second是val类型的默认构造函数。
这样我们就可以将上面代码简化为下面代码了。countMap对象中它的两个参数是string和int第一次的时候不存在所以会创建一个pairstring,int对象。int则会调用它的默认构造函数即结果为0。然后有一个所以最终会将这个值给插入进去。
void test_map3()
{string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (auto e : arr){countMap[e];}mapstring, int::iterator it countMap.begin();while (it ! countMap.end()){cout it-first : it-second endl;it;}
}
int main()
{test_map3();return 0;
}这个[]运算符重载其实就是靠插入函数实现的因为无论插入成功与否insert会返回一个pair对象pair对象的first就是就是新插入进去结点或者已有结点的迭代器。然后我们直接访问这个迭代器指向的second即可。
除了上面的统计个数的场景我们还可以试一下下面的单词翻译的场景
void test_map4()
{mapstring, string dict;pairstring, string kv1(insert, 插入);dict.insert(kv1);dict.insert(pairstring, string(sort, 排序));dict.insert(make_pair(remove, 改革));dict.insert({ process,过程 });//C11 多参数的构造函数隐式类型转换dict[remov] xxx;dict[process] 进程;dict[access] 接受道路;cout (dict[set] 集合) endl;for (auto e : dict){cout e.first e.second endl;}
}
int main()
{test_map4();return 0;
} 我们可以注意到通过[]运算符重载我们可以实现对原来的值进行修改如果原来没有可以插入。也可以进行查找插入等等一系列操作。
4. 使用map改进一些题 力扣链接有效的括号 对于下面这道题我们之前就是直接一个一个匹配但是现在我们已经可以使用map来进行维护了这样的话如果还有更多的括号需要进行匹配的话只需要改变map里面存储的值即可
class Solution {
public:bool isValid(string s) {stackchar st;mapchar,char matchMap;matchMap[(] );matchMap[[] ];matchMap[{] };for(auto ch : s){if(matchMap.count(ch)){st.push(ch);}else{if(st.empty()){return false;}char top st.top();st.pop();if(matchMap[top]!ch){return false;}}}if(!st.empty())return false;elsereturn true;}
};力扣链接复杂链表的复制 这道题如果有了map的话简直是太简单了。直接建立一个映射关系然后先复制好每一个结点然后利用[]运算符重载就可以很好的处理好每一个之间的关系。
/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val _val;next NULL;random NULL;}
};
*/
class Solution {
public:Node* copyRandomList(Node* head) {Node* cur head;mapNode*,Node* listMap;while(cur){listMap[cur] new Node(cur-val);cur cur-next;}cur head;while(cur){listMap[cur]-next listMap[cur-next];listMap[cur]-random listMap[cur-random];cur cur-next;}return listMap[head];}
};5. multimap容器
这个容器与map之间的关系就好像set与multiset之间的关系一样。接口都是一样的不同的就是这个容器允许重复元素出现
还有一共不同就是这个容器没有提供[]运算符重载了其实也是比较合理的因为此时一个key可以有很多个val是没法确定要哪一个的。
insert也有一些变化他的返回值就不在是一共pair了里面就没有所谓的bool了只是单纯的返回新插入结点的迭代器因为他插入永远成功 那么既然一个key可以有多个val,我们可以注意到他是可以根据key进行删除的那么它是全删除掉吗确实是这样的multimap根据一个值去删除元素会将所有与key相关的全部删除掉。 五、map和set相关力扣题 力扣链接两个数组的交集 这道题目求的是交集我们的思路就是利用set来完成最为方便。首先先将两个数组里面的值都丢到set里面可以天然的去重。然后我们再去遍历这两个set。由于正好也排好序了。所以我们就如果谁小谁就否则相等的话那么就进入数组然后两个同时即可
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {setint s1(nums1.begin(),nums1.end());setint s2(nums2.begin(),nums2.end());vectorint v;auto it1 s1.begin();auto it2 s2.begin();while(it1 ! s1.end() it2 ! s2.end()){if(*it1*it2){it2;}else if(*it1*it2){it1;}else {v.push_back(*it1);it1;it2;}}return v;}
};如果题目要让我们求差集的话也是很简单的我们还是先丢到set里面然后进行比对将较小的进入数组然后。如果相等同时即可。因为set天然的排好序了所以小的一定是独一无二的而较大的当小的以后可能就会出现重复了。 力扣链接前K个高频单词 对于这道题我们的思路也是比较简单的我们首先先创建一个map然后我们将words中的所有单词给放入map中顺便统计好次数。这样以后map中也正好天然的按照字典序排好了。接下来我们需要对map中的数据按照频率进行排序。不过这里的排序需要注意我们不能直接对map进行排序因为迭代器的类型不匹配。所以我们只能将数据都放入一个vectorpairstring,int中进行排序。在这里还有一个大坑首先我们要按照降序排列所以我们会写一个仿函数让他按照降序排其次这里我们不能直接用sort因为sort底层是一个快排它是不稳定的会将字典序顺序打乱。所以我们需要使用一个稳定的排序库里面正好提供了这个稳定的排序stable_sort。所以这下排序之后我们就能完成这个题目了。
class Solution {
public:struct Greater{bool operator()(const pairstring,int p1,const pairstring,int p2){return p1.secondp2.second;}};vectorstring topKFrequent(vectorstring words, int k) {mapstring,int countMap;vectorstring v;for(auto e : words){countMap[e];}vectorpairstring,int vpa(countMap.begin(),countMap.end());stable_sort(vpa.begin(),vpa.end(),Greater()); for(int i 0; i k; i){v.push_back(vpa[i].first);}return v;}
};上面最坑人的地方莫过于sort不是稳定的排序我们可能甚至都没用过stable_sort这个排序。那么在我们不知道的情况下该如何处理这道题呢事实上我们会发现我们的仿函数其实还可以在详细一些我们先按频率排当频率相等的时候在依据字典序排列即可
class Solution {
public:struct Greater{bool operator()(const pairstring,int p1,const pairstring,int p2){return p1.secondp2.second||((p1.secondp2.second)(p1.firstp2.first));}};vectorstring topKFrequent(vectorstring words, int k) {mapstring,int countMap;vectorstring v;for(auto e : words){countMap[e];}vectorpairstring,int vpa(countMap.begin(),countMap.end());sort(vpa.begin(),vpa.end(),Greater()); for(int i 0; i k; i){v.push_back(vpa[i].first);}return v;}
};在这里其实还有第三种方式可以完成这道题
如下代码所示我们可以先将countMap以字典序排好且统计出次数之后然后使用一个multimapint,stringgreaterint以频率在排一次。注意使用第三个模板参数即仿函数因为我们是要以频率为降序进行排序。然后最后我们依次插入vector即可
class Solution {
public:vectorstring topKFrequent(vectorstring words, int k) {mapstring,int countMap;vectorstring v;for(auto e : words){countMap[e];}multimapint,string,greaterint sMap;for(auto e : countMap){sMap.insert(make_pair(e.second,e.first));}auto it sMap.begin();while(k--){v.push_back(it-second);it;}return v;}
};总结
本节主要讲解了map与set的基本使用。希望能对大家带来帮助
