文章目录1 迭代器的类型2 容器的类型2.1 序列容器2.1.1 定长数组 array c112.1.2 动态数组 vector2.1.3 双端队列 deque2.2 链表容器2.2.1 双向链表 list2.2.2 单向链表 forward_list c112.3 适配器容器2.3.1 栈 stack2.3.2 队列 queue2.3.3 优先序列 priority_queue2.3.3.1 构造小顶堆2.3.3.2 使用自定义类型作为基础类型2.4 有序关联容器底层红黑树2.4.1 集合 set/multiset2.4.2 映射 map/multimap2.5 无序关联容器底层哈希表2.5.1 无序集合 unordered_set/unordered_multiset c112.5.2 无序映射 unordered_map/unordered_multimap c11CSTLStandard Library提供了一系列基于模板的容器实现了各种经典数据结构在容器中提供了迭代器作为容器的访问接口。1 迭代器的类型迭代器是STL中提供的对容器元素的访问方式可以简单地将迭代器看成指向容器中元素的指针针对不同容器提供不同类型的迭代器来控制对容器元素的访问方式迭代器有以下几种类型随机访问迭代器Random-access Iterator提供了最自由的操作以及输入输出操作。提供、--、、-、、-、[]等操作。双向迭代器Bidirectional Iterator提供了单步向前或向后操作以及输入输出操作。提供、--、、*等操作。前向迭代器Forward Iterator提供单向递增操作以及输入输出操作。提供、、*等操作。输出迭代器Output Iterator提供单向递增、写入操作。提供、等操作。输入迭代器Input Iterator提供单向递增、访问操作。提供、*等操作。2 容器的类型序列容器支持随机访问迭代器array——定长数组提供一种STL方式来创建固定长度数组。可以看成对之前版本中使用[]创建的数组的一种替代方式。vector——动态数组长度可以动态自动增长的顺序序列。优势支持快速访问元素、序列尾部的快速插入删除元素。deque——双端序列在头尾都可以进行快速操作的序列。优势支持头尾两端的快速插入删除元素访问元素比vector稍慢一些在大数据量的容量动态增减方面比vector有优势。链表容器支持前向或双向迭代器forward_list——单向链表链表中的节点只能向后搜索支持前向迭代器。list——双向链表链表中的节点可以向前和向后搜索支持双向迭代器。优势链表支持在任意位置快速插入删除元素。容器适配器不支持迭代器stack——栈先进后出LIFOLast In First Out。queue——队列先进先出FIFOFirst In First Out。priority_queue——优先序列内部维护了一个堆数据结构堆顶为极值。有序关联容器支持双向迭代器set——有序集合只包含不重复元素的有序集合。multiset——有序多重集合可以包含重复元素的有序集合。map——有序映射“键-值”对的有序集合只包含不重复的键。multimap——有序多重映射”键-值“对的有序集合可以包含重复的键。优势内部有序、支持快速查找。无序关联容器支持前向迭代器unordered_set——无序集合只包含不重复元素的无序集合。unordered_multiset——无序多重集合可以包含重复元素的无序集合。unordered_map——无序映射“键-值”对的无序集合只包含不重复的键。unordered_multimap——无序多重映射”键-值“对的无序集合可以包含重复的键。优势支持快速查找。查找速度比有序关联容器更快2.1 序列容器2.1.1 定长数组 arrayc11位于命名空间std下定义于头文件vector内部元素按照内存地址顺序连续存放。优势访问O(1)、修改O(1)迭代器begin() 返回指向容器第一个元素的迭代器操作向end()方向靠近。end() 返回指向容器最后一个元素的下一个位置的迭代器。rbegin() 返回指向容器最后一个元素的迭代器操作向rend()方向靠近。rend() 返回指向容器第一个元素的上一个位置的迭代器。cbegin()、cend()与crbegin()、crend() 上述迭代器的const版本。容量empty() 判断是否为空。size() 容器使用量的大小。访问operator[] 获取具体元素的引用越界行为不确定。at() 获取具体元素的引用有边界检查可抛出异常。front() 获取首部元素的引用。back() 获取尾部元素的引用。data() 获取底层数组的头指针可以用来进行指针操作。修改fill(value) 使用固定值填满整个数组。swap(vec) 交换两个容器内容包括使用量和容量。2.1.2 动态数组 vector位于命名空间std下定义于头文件vector内部元素按照内存地址顺序连续存放。优势访问O(1)、修改O(1)、尾部位置插入O(1)劣势非尾部位置插入O(n)迭代器begin() 返回指向容器第一个元素的迭代器操作向end()方向靠近。end() 返回指向容器最后一个元素的下一个位置的迭代器。rbegin() 返回指向容器最后一个元素的迭代器操作向rend()方向靠近。rend() 返回指向容器第一个元素的上一个位置的迭代器。cbegin()、cend()与crbegin()、crend() 上述迭代器的const版本。c11rbegin()和back()有区别一个是返回迭代器一个是元素引用容量empty() 判断是否为空。size() 容器使用量的大小。resize() 重新分配使用量大小使容器使用量变为n直接影响size()扩容超容量才会影响capacity()。capacity() 容器容量的大小包含空位。reserve() 重新分配容量大小只有扩容的时候有效任何情况不影响容器size()。shrink_to_fit() 让容量收缩至使用量的大小。c11访问operator[] 获取具体元素的引用越界行为不确定。at() 获取具体元素的引用有边界检查可抛出异常。front() 获取首部元素的引用。back() 获取尾部元素的引用。data() 获取底层数组的头指针可以用来进行指针操作。c11修改assign(n, value) 对容器赋值只有当n大于容量时会重新分配容量。push_back()、pop_back() 尾部的插入和弹出。insert(it, value) 在迭代器指向的位置位置插入元素。erase(it) 在迭代器指向的位置删除单个元素或范围内多个元素。swap(vec) 交换两个容器内容包括使用量和容量。clear() 清空容器的使用量不影响容量彻底vector可以使用。vectorint().swap(myvector)emplace(it, args…) 在迭代器指向的位置构建并插入对象由args实时构造。c11emplace_back(args…) 在尾部位置构建并插入对象由args实时构造。c112.1.3 双端队列 deque位于命名空间std下定义于头文件deque内部元素在内存地址上不能保证是完全连续的而是由多个储存块组成。优势访问O(1)、修改O(1)、首尾位置插入删除O(1)劣势非首尾位置插入删除O(n)迭代器begin() 返回指向容器第一个元素的迭代器操作向end()方向靠近end() 返回指向容器最后一个元素的下一个位置的迭代器rbegin() 返回指向容器最后一个元素的迭代器操作向rend()方向靠近rend() 返回指向容器第一个元素的上一个位置的迭代器cbegin()、cend()与crbegin()、crend() 上述迭代器的const版本c11容量empty() 判断是否为空。size() 容器大小。resize() 重新分配容器大小。shrink_to_fit() 收缩多余的内存占用至size()为支持动态扩容deque实际内存分配可能比size()大。c11访问operator[] 获取具体元素的引用越界行为不确定。at() 获取具体元素的引用有边界检查可抛出异常。front() 获取首部元素的引用。back() 获取尾部元素的引用。修改assign(n, value) 对容器赋值。push_back() 在尾部位置插入元素。push_front() 在首部位置插入元素。pop_back() 在尾部位置删除元素。pop_front() 在首部位置删除元素。insert(it, value) 根据迭代器位置位置插入元素。erase(it) 根据迭代器位置删除单个元素或范围内多个元素。swap(deque) 交换两个容器内容包括使用量和容量。clear() 清空容器。emplace(it, args…) 在迭代器指向的位置构建并插入对象由args实时构造。c11emplace_front(args…) 在首部位置构建并插入对象由args实时构造。c11emplace_back(args…) 在尾部位置构建并插入对象由args实时构造。c112.2 链表容器2.2.1 双向链表 list位于命名空间std下定义于头文件list内部元素按照双向链表的形式存放每个元素都有分别指向前、后元素的两个指针。优势插入、删除耗时O(1)劣势查找O(n)迭代器begin() 返回指向容器第一个元素的迭代器操作向end()方向靠近。end() 返回指向容器最后一个元素的下一个位置的迭代器。rbegin() 返回指向容器最后一个元素的迭代器操作向rend()方向靠近。rend() 返回指向容器第一个元素的上一个位置的迭代器。cbegin()、cend()与crbegin()、crend() 上述迭代器的const版本。c11容量empty() 判断是否为空。size() 容器大小。resize() 重新分配容器大小。访问front() 获取首元素的引用。back() 获取尾元素的引用。修改assign(n, value) 对容器赋值。emplace_front(args…) 在首部构建并插入对象由args实时构造。c11push_front() 在首部插入元素。pop_front() 在首部删除元素。emplace_back() 在尾部构建并插入对象由args实时构造。c11push_back() 在尾部插入元素。pop_back() 在尾部删除元素。empalce(it, args…) 在迭代器指向的位置构建并插入。c11insert(it, value) 在迭代器指向的位置位置插入元素。erase(it) 在迭代器指向的位置删除单个元素或范围内多个元素。swap(list) 交换两个容器内容。clear() 清空容器。操作splice(it, list, pos) 将另一个链表list中的元素链入从list中移走当前it迭代器的位置list可以是自身用于将移动自身的某一段。std::listint mylist1, mylist2; std::listint::iterator it; // set some initial values: for (int i1; i4; i){mylist1.push_back(i);} // mylist1: 1 2 3 4 for (int i1; i3; i){mylist2.push_back(i*10);} // mylist2: 10 20 30 it mylist1.begin(); it; // points to 2 // mylist1将mylist2全部链入自身 mylist1.splice (it, mylist2); // mylist1: 1 10 20 30 2 3 4 // mylist2 (empty) // it still points to 2 (the 5th element) // mylist2将mylist1中的单个元素链入自身 mylist2.splice (mylist2.begin(),mylist1, it); // mylist1: 1 10 20 30 3 4 // mylist2: 2 // it is now invalid. // 旋转自身mylist1将自身的某一段移至首部 it mylist1.begin(); std::advance(it,3); // it points now to 30 mylist1.splice ( mylist1.begin(), mylist1, it, mylist1.end()); // mylist1: 30 3 4 1 10 20remove() 删除容器中所有指定值的元素。remove_if(Predicate) 删除满足断言的所有元素对每个元素会调用pred(*i)。// a predicate implemented as a function: bool single_digit (const int value) { return (value10); } // a predicate implemented as a class: struct is_odd { bool operator() (const int value) { return (value%2)1; } }; …… int myints[] {15,36,7,17,20,39,4,1}; listint mylist (myints,myints8); // 15 36 7 17 20 39 4 1 mylist.remove_if (single_digit); // 15 36 17 20 39 mylist.remove_if (is_odd()); // 36 20unique() 去除相邻的重复元素只保留第一个如果重复元素不相邻则不会去除。一般预先做一次排序merge(list) 将list有序链入list最后为空链表。要想结果有序需要两个链表预先都有序sort() 对链表稳定排序。reverse() 翻转整个链表。merge()和sort()默认使用less比较函数可以在参数中指定greatertypename进行从大到小的排序。2.2.2 单向链表 forward_listc11位于命名空间std下定义于头文件forward_list内部元素按照单向链表的形式存放每个元素都有指向后一个元素的指针。优势插入O(1)、删除O(1)劣势查找O(n)迭代器befor_begin() 返回指向第一个元素的上一个位置的迭代器操作向end()方向靠近。begin() 返回指向容器第一个元素的迭代器操作向end()方向靠近。end() 返回指向容器最后一个元素的下一个位置的迭代器。cbegin()、cend()、cbefore_begin() 上述迭代器的const版本。容量empty() 判断是否为空。size() 容器大小。resize() 重新分配容器大小。访问front() 获取首元素的引用。修改assign(n, value) 对容器赋值。emplace_front(args…) 在首部构建并插入对象由args实时构造。push_front() 在首部插入元素。pop_front() 在首部删除元素。emplace_after() 在迭代器指向的位置之后构建并插入对象由args实时构造。insert_after() 在迭代器指向的位置之后插入元素。erase_after() 在迭代器指向的位置之后删除元素。swap(forward_list) 交换两个容器内容。clear() 清空容器。操作splice_after(it, list, pos) 将链表list中的元素链入从list中移走当前it迭代器的位置之后,ist可以是自身用于将移动自身的某一段。remove() 删除容器中所有指定值的元素。remove_if(Predicate) 删除满足断言的所有元素对每个元素会调用pred(*i)。unique() 去除相邻的重复元素只保留第一个如果重复元素不相邻则不会去除。一般预先做一次排序merge(forward_list) 将list有序链入list最后为空链表。要想结果有序需要两个链表预先都有序sort() 对链表稳定排序。reverse() 翻转整个链表。merge()和sort()默认使用less比较函数可以在参数中指定greatertypename进行从大到小的排序。2.3 适配器容器适配器容器是对容器的再次封装底层可能是序列容器或者链表。适配器容器的作用是为了提供在具体场景下能够使用的专用数据结构。2.3.1 栈 stack位于命名空间std下定义于头文件stack内部元素按照后进先出LIFO的规则运行。在栈数据结构中访问、插入、删除都只能对栈顶进行耗时都为O(1)常用于深度优先搜索以及递归中使用。stack是对容器的一种包装默认的底层容器是deque也可以换成vector、list等只要支持empty、size、back、push_back、pop_back五项操作即可。容量empty() 判断是否为空size() 容器大小访问top() 获取栈顶元素的引用修改push() 入栈。pop() 出栈。swap(stack) 交换两个容器内容调用的是底层包装的数据结构的swap操作。c11emplace(args…) 入栈对象由args实时构造而push入栈已构造完成的对象。c112.3.2 队列 queue位于命名空间std下定义于头文件queue内部元素按照先进先出FIFO的规则运行。在队列数据结构中访问可以对队列的头部和尾部进行插入是对队列尾部入队删除是对队列首部出队耗时都为O(1)常用于宽度优先搜索中使用。queue是对容器的一种包装默认的底层容器是deque也可以换成list等只要支持empty、size、front、back、push_back、pop_front六项操作即可。容量empty() 判断是否为空size() 容器大小访问front() 获取队列首部元素的引用back() 获取队列尾部元素的引用修改push() 入队pop() 出队swap(queue) 交换两个容器内容调用的是底层包装的数据结构的swap操作。c11emplace(args…) 入队对象由args实时构造而push入队已构造完成的对象。c112.3.3 优先序列 priority_queue位于命名空间std下定义于头文件queue内部元素按照有序堆大顶堆、小顶堆进行存放。因为需要实时维护堆的有序性插入、删除、修改操作耗时O(log n)。容量empty() 判断是否为空。size() 容器大小。访问top() 获取堆顶元素。修改push() 向堆中压入元素。emplace() 构建并压入元素。pop() 删除堆顶元素。2.3.3.1 构造小顶堆模版类priority_queue的定义如下template class T, class Container std::vectorT, class Compare std::lesstypename Container::value_type class priority_queue;默认构造的优先序列为大顶堆优先序列因为模版定义中使用的默认比较函数是less要构造小顶堆优先序列对于已经内置了比较函数的系统数据类型可以直接使用内置的比较函数std::greatertypenamepriority_queueint myPriorityQueue; // 默认大顶堆优先序列 priority_queueint, vectorint, greaterint myPriorityQueue; // 小顶堆优先序列2.3.3.2 使用自定义类型作为基础类型对自定义类型构建优先序列需要手动添加比较函数假设自定义类型如下class ListNode { public: int val; ListNode *next; ListNode(int val) { this-val val; this-next NULL; } };我们为ListNode *这个类型定义大顶堆优先序列有以下几种方式使用结构、或者类来重载()运算符的方式struct Cmp{ bool operator() (ListNode * left, ListNode * right){return left-val right-val;} }myCmp; priority_queueListNode *, vectorListNode *, cmp myPriorityQueue; // 使用类名 priority_queueListNode *, vectorListNode *, decltype(mycmp) myPriorityQueue; // 也可以使用类的声明对象定义Cmp类可以用struct或者class声明myCmp对象如果类定义使用class该运算符重栽的访问限定符必须为publicpriority_queue模版的第三个位置需要的是类型信息decltype()函数用于获取表达式的数据类型。使用比较函数的方式bool cmp (ListNode * left, ListNode * right){return left-val right-val;} priority_queueListNode *, vectorListNode *, decltype(cmp) myPriorityQueue(cmp);定义比较函数cmp为函数指针用decltype()函数获取函数指针的类型还需要多一个步骤优先序列初始化时传入该比较函数的地址函数名即为函数地址使用Lamda表达式的方式functionbool(ListNode *, ListNode *) cmp [](ListNode * left, ListNode * right){return left-val right-val;}; priority_queueListNode *, vectorListNode *, decltype(cmp) myPriorityQueue(cmp);定义lamda表达式用function包装的cmp为指向该lamda表达式的函数指针用decltype()函数取指针类型优先序列初始化时传入该比较函数的地址直接传入该cmp指针auto cmp[](ListNode * left, ListNode * right){return left-val right-val;}; priority_queueListNode *, vectorListNode *, decltype(comp) myPriorityQueue(cmp);用auto代替实际类型可以简化定义的过程。最后说明一下比较函数中使用大于号定义的是小端堆优先序列不要记反。2.4 有序关联容器底层红黑树2.4.1 集合 set/multiset位于命名空间std下定义于头文件set内部元素按照红黑树平衡二叉查找树有序存放。set的元素不允许重复multiset的元素可以重复元素为const不允许直接更改。优势查找O(log n)劣势插入O(log n)、删除O(log n)迭代器begin() 返回指向容器第一个元素的迭代器操作向end()方向靠近。end() 返回指向容器最后一个元素的下一个位置的迭代器。rbegin() 返回指向容器最后一个元素的迭代器操作向rend()方向靠近。rend() 返回指向容器第一个元素的上一个位置的迭代器。cbegin()、cend()与crbegin()、crend() 上述迭代器的const版本。c11容量empty() 判断是否为空。size() 容器的大小set容器因为内部维护的是一棵红黑树所以使用量即是容量。修改insert(value) 插入元素返回pairfirst代表值second代表是否插入成功。erase() 删除元素可以用值或者迭代器作参数用值时返回删除的元素个数。swap(set) 交换两个容器内容还有全局版本的std::swap(set1, set2)。clear() 清空容器emplace(args…) 插入对象由args实时构造而insert插入已构造完成的对象。c11操作find(value) 返回指向查询到的第一个匹配元素的迭代器未找到则返回set::end()/multiset::end()。count(value) 计算元素个数。lower_bound(value) 返回指向value的第一个元素的迭代器。upper_bound(value) 返回指向value的第一个元素的迭代器。equal_range(value) 返回包含两个迭代器的pair迭代器分别指向lower_bound与upper_bound。2.4.2 映射 map/multimap位于命名空间std下定义于头文件map内部元素按照红黑树平衡二叉查找树有序存放。每一个元素都有key值和value值key值用于排序map中的key不允许重复multimap的key可以重复value用于储存实际数据它们的类型可以不相同组成一个pair类型的数据结构pairconst key, value作为map的元素。查找、插入、修改、删除耗时都为O(log n)。map容器内部的key_comp用来比较key的大小以此来排序。对于multimap相同key值的元素并没有进行排序。容器也提供内部函数value_comp用来比较pairkey, value的大小。迭代器begin() 返回指向容器第一个元素的迭代器操作向end()方向靠近。end() 返回指向容器最后一个元素的下一个位置的迭代器。rbegin() 返回指向容器最后一个元素的迭代器操作向rend()方向靠近。rend() 返回指向容器第一个元素的上一个位置的迭代器。cbegin()、cend()与crbegin()、crend() 上述迭代器的const版本。c11容量empty() 判断是否为空。size() 容器大小。访问multimap不提供operator[] 获取具体元素的引用越界行为不确定。at() 获取具体元素的引用有边界检查可抛出异常。c11multimap不提供[]和at来对元素访问更多的是通过lower_bound、upper_bound、equal_range来访问对应的元素范围。修改insert() 插入元素insert(pairint, int(1, 100)); insert(make_pair(2, 200)); insert({2, 200});erase() 删除元素可以用值或者迭代器作参数用值时返回删除的元素个数。swap(map) 交换两个容器内容包括使用量和容量。clear() 清空容器。emplace(args…) 构建并插入元素对象由args实时构造。c11操作find(pair) 返回指向查询到的第一个匹配元素的迭代器未找到则返回map::end()/multimap::end()。count(pair) 计算元素个数。lower_bound(pair) 返回指向key的第一个元素的迭代器。upper_bound(pair) 返回指向key的第一个元素的迭代器。equal_range(pair) 返回包含两个迭代器的pair迭代器分别指向lower_bound与upper_bound。2.5 无序关联容器底层哈希表2.5.1 无序集合 unordered_set/unordered_multisetc11位于命名空间std下定义于头文件unordered_set内部元素按照哈希表存放。set的元素不允许重复multiset的元素可以重复元素为const不允许直接更改元素内部无序。查找、插入、删除耗时都为O(1)空间复杂度高一般比数据量大一个数量级。迭代器begin() 返回指向容器第一个元素的迭代器操作向end()方向靠近。end() 返回指向容器最后一个元素的下一个位置的迭代器。cbegin()、cend() 上述迭代器的const版本。c11容量empty() 判断是否为空。size() 容器大小。查找find(value) 查找元素是否存在。count(value) 计算元素个数。equal_range(value) 返回包含两个迭代器的pair迭代器分别指向value的第一个元素与value的第一个元素。修改insert(value) 插入元素返回pairfirst代表值second代表是否插入成功。erase() 删除元素可以用值或者迭代器作参数用值时返回删除的元素个数。swap(set) 交换两个容器内容还有全局版本的std::swap(set1, set2)。clear() 清空容器emplace(args…) 插入对象由args实时构造而insert插入已构造完成的对象。c11哈希桶bucket_count() 哈希表中桶的数量。bucket_size(n) 哈希表中第n个桶中包含的元素数量。bucket(value) 返回包含当前元素的桶序号。2.5.2 无序映射 unordered_map/unordered_multimapc11位于命名空间std下定义于头文件unordered_map内部元素按照哈希表存放。每一个元素都有key值和value值key值用于排序map中的key不允许重复multimap的key可以重复value用于储存实际数据它们的类型可以不相同组成一个pair类型的数据结构pairconst key, value作为map的元素。查找、插入、修改、删除耗时都为O(1)空间复杂度高一般比数据量大一个数量级迭代器begin() 返回指向容器第一个元素的迭代器操作向end()方向靠近。end() 返回指向容器最后一个元素的下一个位置的迭代器。cbegin()、cend() 上述迭代器的const版本。c11容量empty() 判断是否为空。size() 容器大小。访问unordered_multimap不提供operator[] 获取具体元素的引用越界行为不确定。at() 获取具体元素的引用有边界检查可抛出异常。c11multimap不提供[]和at来对元素访问更多的是通过equal_range来访问对应的元素范围。修改insert() 插入元素insert(pairint, int(1, 100)); insert(make_pair(2, 200)); insert({2, 200});erase() 删除元素可以用值或者迭代器作参数用值时返回删除的元素个数。swap(map) 交换两个容器内容包括使用量和容量。clear() 清空容器。emplace(args…) 构建并插入元素对象由args实时构造。c11哈希桶bucket_count() 哈希表中桶的数量。bucket_size(n) 哈希表中第n个桶中包含的元素数量。bucket(value) 返回包含当前元素的桶序号。操作find(pair) 返回指向查询到的第一个匹配元素的迭代器未找到则返回map::end()/multimap::end()。count(pair) 计算元素个数。equal_range(pair) 返回包含两个迭代器的pair迭代器分别指向value的第一个元素与value的第一个元素。
