威海建设集团网站,百度电脑版官网下载,各种网站开发工具,要给公司做一个网站怎么做的吗1. 序列式容器与关联式容器
前面我们已经接触过STL中的部分容器如#xff1a;string、vector、list、deque、array、forward_list等#xff0c;这些容器统称为序列式容器#xff0c;因为逻辑结构为线性序列的数据结构#xff0c;两个位置存储的值之间一般没有紧密的关联关…1. 序列式容器与关联式容器
前面我们已经接触过STL中的部分容器如string、vector、list、deque、array、forward_list等这些容器统称为序列式容器因为逻辑结构为线性序列的数据结构两个位置存储的值之间一般没有紧密的关联关系比如交换⼀下他依旧是序列式容器。
顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。
关联式容器也是用来存储数据的与序列式容器不同的是关联式容器逻辑结构通常是非线性结构两个位置有紧密的关联关系交换一下他的存储结构就被破坏了。
顺序容器中的元素是按关键字来保存和访问的。
关联式容器有map/set系列和unordered_map/unordered_set系列。
本章节讲解的map和set底层是红黑树红黑树是一颗平衡二叉搜索树。 set/multiset是key搜索场景的结构 map/multimap是key/value搜索场景的结构。 set/map不支持相同的值插入multiset/multimap支持相同的值插入。 2. pair类
在正式介绍set和map之前我们需要先了解一下pair类。
这个类也是一个类模板顾名思义它的作用就是存储两个数据也即将两个数据绑定到一起。
在需要返回两个数据的场景下我们就可以将两个数据存到pair中进行返回。
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){}// 支持隐式类型转换templateclass U, class Vpair(const pairU, V pr) : first(pr.first), second(pr.second){}
};// C11之间常用的构造pair的函数
template class T1, class T2
inline pairT1, T2 make_pair(T1 x, T2 y)
{return (pairT1, T2(x, y));
}
3. set的介绍
参考文档set - C Reference关于set的使用将其当作key搜索场景的红黑树来使用即可。
set的原型
template class T, // set::key_type/value_typeclass Compare lessT, // set::key_compare/value_compareclass Alloc allocatorT // set::allocator_type class set;
类型参数分别为key的类型比较器通过仿函数实现默认为小于比较中序遍历得到升序序列内存池。
一般来说后两个参数有缺省值的使用频率较低我们在日常使用的过程中只需要传入第一个参数即可。
3.1 常用接口
STL的容器都是大同小异这里只列出需要注意的。
3.1.1 构造函数
set();默认构造template class InputIterator set(InputIterator first, InputIterator last);迭代器区间构造set(const set x);拷贝构造
在C11之后还支持用列表构造
// initializer list (5) initializer 列表构造
set (initializer_listvalue_type il,const key_compare comp key_compare(),const allocator_type alloc allocator_type());eg:
setint mySet1({1, 2, 3, 4});
setint mySet2 {1, 2, 3, 4};
在原文档中前两个构造函数的参数列表还包括比较器和内存池 但是经过我自己的测试发现如果在定义set的时候传入比较器或内存池这个定义语句会被编译器识别成函数的声明 也就是说比较器和内存池依然只能在类型参数列表中传入。 3.1.2 迭代器
这里就不列表了set的迭代器是双向迭代器函数还是那几个函数。
正向迭代器的是按照key值从小到大进行遍历。
除此之外在set中无论是iterator还是const_iterator都不支持通过解引用修改set中的数据因为这样会破坏红黑树的底层结构。
3.1.3 增删
(1)pairiterator, bool insert(const value_type val); (2)iterator insert(iterator position, const value_type val); (3)template class InputIterator void insert(InputIterator first, InputIterator last); (1)按值插入 (2)指定位置插入 (3)将容器的迭代器区间内的值插入 (1)void erase(iterator position); (2)size_type erase(const value_type val); (3)void erase(iterator first, iterator last); (1)删除指定位置的值 (2)删除指定的值 (3)删除一个迭代器区间
insert函数(1)的返回值是一个pair 插入成功时iterator为新插入数据的迭代器bool为true 插入失败时iterator为已有的相同值的迭代器bool为false insert函数(2)的第一个参数实质上只是一个插入建议由于set的特殊的红黑树的底层结构该插入建议可能不会被采纳。 3.1.4 查找
iterator find (const value_type val) const;查找某个值size_type count (const value_type val) const;查找某个值在set中有几个
set不支持相同的值进行插入所以count的结果不是1就是0。
这样看来count似乎有点鸡肋或者说与名称不符但set中的count实际上是为了与multiset统一而存在的。
但count也并非一无是处如果只想确定某个值存不存在的话count就稍微比find方便一点
if(mySet.find(24) ! mySet.end())
{// ......
}if(mySet.count(24))
{// ......
}
3.2 multiset
基本与set相同但是支持插入相同的数据由此而引发的变化还有 1. insert一定成功插入函数(1)的返回值不再是pair而只有iterator。 2. count返回数据在set中的个数。 3. 如果有多个相同的值无论是删除还是查找都是对中序遍历的第一个进行操作。 4. map的介绍
参考文档map - C Reference关于map的使用将其当作key/value搜索场景的红黑树来使用即可。
map的原型
template class Key, // map::key_typeclass T, // map::mapped_typeclass Compare lessKey, // map::key_compareclass Alloc allocatorpairconst Key,T // map::allocator_type class map;
类型参数分别为key的类型value的类型比较器通过仿函数实现默认为小于比较中序遍历得到升序序列内存池。
除此之外pair在map中起到了将key和value绑定到一起的作用所以在map的结点中存的数据实际上是pair而没有单独存储key和value。
typedef pairconst Key, T value_type;
同样大多数情况下只需要传入前两个参数即可。
4.1 常用接口
同样此处只列出较为重要或与其他容器有所不同的。
4.1.1 构造函数
map();默认构造template class InputIterator map (InputIterator first, InputIterator last);迭代器区间构造map (const map x);拷贝构造
在C11之后支持列表构造
// initializer list (5) initializer 列表构造
map (initializer_listvalue_type il,const key_compare comp key_compare(),const allocator_type alloc allocator_type());eg:
mapstring, int myMap1({{张三, 18}, {李四, 21}, {王五, 35}});
mapstring, int myMap2 {{张三, 18}, {李四, 21}, {王五, 35}};
内层大括号会通过pair的列表构造隐式类型转换为pairstring, int类型。
关于参考文档中给出的函数原型依然存在着和set相同的问题。 4.1.2 迭代器
函数还是那些函数迭代器还是双向迭代器。
但与set不同的是map的迭代器支持对value进行修改而依然不支持对key进行修改。
由于map结点中存的是pairkey, value所以按照逻辑来说map的迭代器解引用得到的就是pairkey, value。
在pair中key对应的是firstvalue对应的是second
mapstring, int myMap(...);
mapstring, int::iterator it myMap.begin();
while(it ! myMap.end())
{cout key: (*it).first value: *(it).second endl;cout key: it-first value: it-second endl;
}4.1.3 增删
(1)pairiterator, bool insert(const value_type val); (2)iterator insert(iterator position, const value_type val); (3)template class InputIterator void insert(InputIterator first, InputIterator last); (1)按值插入 (2)指定位置插入 (3)将容器的迭代器区间内的值插入 (1)void erase(iterator position); (2)size_type erase(const key_type k); (3)void erase(iterator first, iterator last); (1)删除指定位置的值 (2)删除指定的值 (3)删除一个迭代器区间
函数原型与set完全一样除了erase函数(2)只需要key即可找到对应的数据进行删除。
但是要切记这里的value_type是pair。
insert函数(1)的返回值逻辑也与set相同但是只要key相同就不支持继续插入了。
4.1.4 查找
iterator find (const key_type k); const_iterator find (const key_type k) const;按键值key查找size_type count (const key_type k) const;查找某个键值key在set中有几个 同样这里的count函数的返回值也只能是1或0。
4.1.5 operator[]
没错map重载了[]。
但是按理来说只有支持随机迭代器的容器才可以重载[]而map不是双向迭代器吗
看了函数原型你就明白了
mapped_type operator[] (const key_type k);
所以这个[]的功能是根据key来返回value的引用而与迭代器没有关系。
但这个函数并不简单 当key存在时返回其对应的value的引用。 当key不存在时在map中插入key并给value默认值然后返回value的引用。 所以map中的[]可以说是查找修改插入三位一体。
这是由于operator[]的内部实现是基于insert函数完成的
// operator[]的内部实现
mapped_type operator[] (const key_type k)
{// 1、如果k不在map中insert会插⼊k和mapped_type默认值同时[]返回结点中存储//mapped_type值的引⽤那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊修改功能// 2、如果k在map中insert会插⼊失败但是insert返回pair对象的first是指向key结点的//迭代器返回值同时[]返回结点中存储mapped_type值的引⽤所以[]具备了查找修改的功能pairiterator, bool ret insert({ k, mapped_type() });iterator it ret.first;return it-second;
} 4.2 multimap
基本与map相同但是支持插入相同的数据由此而引发的变化还有 1. insert一定成功插入函数(1)的返回值不再是pair而只有iterator。 2. count返回数据在map中的个数。 3. 如果有多个相同的值无论是删除还是查找都是对中序遍历的第一个进行操作。 4. 不再支持operator[]因为同一个key存在多组值。
