目录
C++ STL (Standard Template Library标准模板库) 是通用类模板和算法的集合,它提供给程序员一些标准的数据结构的实现如 queues(队列), lists(链表), 和 stacks(栈)等.
STL容器的提供是为了让开发者可以更高效率的去开发,同时我们应该也需要知道他们的底层实现,这样在出现错误的时候我们才知道一些原因,才可以更好的去解决问题。
C++ STL 提供给程序员以下三类数据结构的实现:
- 顺序结构 C++ Vectors
- C++ Lists
- C++ Double-Ended Queues
- 容器适配器 C++ Stacks
- C++ Queues
- C++ Priority Queues
- 联合容器 C++ Bitsets
- C++ Maps
- C++ Multimaps
- C++ Sets
- C++ Multisets
【1】Vectors容器
vector的行为和数组类似,可以理解为顺序表
vector不需要判满,动态分配内存:如果存入新的数据,会再开辟一片更大的空间,把原来的内容拷贝过去
编辑
begin和end成员函数,返回起始位置和结尾位置的迭代器
front和back函数,返回起始位置和结尾位置的引用
at(idx) 传回索引idx所指的数据,如果idx越界,抛出out_of_range。 back() 返回最后一个原始,不检查这个数据是否存在。 front() 返回第一个元素。 swap() 交换两个Vector。 push_back() 在Vector最后添加一个元素。 pop_back() 它从向量中删除最后一个元素。 empty() 判断Vector是否为空(返回true时为空) insert() 它将在指定位置插入新元素。 erase() 删除指定的元素。 resize() 它修改向量的大小。 clear() 它从向量中删除所有元素。 size() 返回Vector元素数量的大小。 capacity() 返回vector所能容纳的元素数量(在不重新分配内存的情况下) assign() 它将新值分配给向量。 operator=() 它将新值分配给向量容器。 operator[]() 它访问指定的元素。 end() 返回最末元素的迭代器(实指向最末元素的下一个位置) emplace() 它将在位置pos之前插入一个新元素。 emplace_back() 它在末尾插入一个新元素。 rend() 它指向向量的第一个元素之前的元素。 rbegin() 它指向向量的最后一个元素。 begin() 返回第一个元素的迭代器。 max_size() 返回Vector所能容纳元素的最大数量(上限)。 cend() 它指向量中的last-last-element。 cbegin() 它指向量的第一个元素。 crbegin() 它指的是向量的最后一个字符。 crend() 它指的是向量的第一个元素之前的元素。 data() 它将向量的数据写入数组。 shrink_to_fit() 它减少了容量并使它等于向量的大小。
找指定位置的迭代器:
由于容器类,只提供了找起始位置和结束位置的迭代器,所以找指定位置的迭代器,只能在已有迭代器的位置上自增,和指针的行为类似,访问元素需要解引用,但是不能和指针类型强转
容器名<数据类型> ::iterator 迭代器名;
vector会二倍扩容(代码中有详细注释)
【2】list容器
STL list 容器,又称双向链表容器,即该容器的底层是以双向链表的形式实现的。这意味着,list 容器中的元素可以分散存储在内存空间里,而不是必须存储在一整块连续的内存空间中。
1. begin() 返回指向容器中第一个元素的双向迭代器。 2. end() 返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器。 3. rbegin() 返回指向最后一个元素的反向双向迭代器。 4. rend() 返回指向第一个元素所在位置前一个位置的反向双向迭代器。 5. cbegin() 和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。 6. cend() 和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。 7. crbegin() 和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。 8. crend() 和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。 9. empty() 判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。 10. size() 返回当前容器实际包含的元素个数。 11. max_size() 返回容器所能包含元素个数的最大值。这通常是一个很大的值,一般是 232-1,所以我们很少会用到这个函数。 12. front() 返回第一个元素的引用。 13. back() 返回最后一个元素的引用。 14. assign() 用新元素替换容器中原有内容。 15. emplace_front() 在容器头部生成一个元素。该函数和 push_front() 的功能相同,但效率更高。 16. push_front() 在容器头部插入一个元素。 17. pop_front() 删除容器头部的一个元素。 18. emplace_back() 在容器尾部直接生成一个元素。该函数和 push_back() 的功能相同,但效率更高。 19. push_back() 在容器尾部插入一个元素。 20. pop_back() 删除容器尾部的一个元素。 21. emplace() 在容器中的指定位置插入元素。该函数和 insert() 功能相同,但效率更高。 22. insert() 在容器中的指定位置插入元素。 23. erase() 删除容器中一个或某区域内的元素。 24. swap() 交换两个容器中的元素,必须保证这两个容器中存储的元素类型是相同的。 25. resize() 调整容器的大小。 26. clear() 删除容器存储的所有元素。 27. splice() 将一个 list 容器中的元素插入到另一个容器的指定位置。 28. remove(val) 删除容器中所有等于 val 的元素。 29. remove_if() 删除容器中满足条件的元素。 30. unique() 删除容器中相邻的重复元素,只保留一个。 31. merge() 合并两个事先已排好序的 list 容器,并且合并之后的 list 容器依然是有序的。 32. sort() 通过更改容器中元素的位置,将它们进行排序。 33. reverse() 反转容器中元素的顺序。1
由此可以理解,list 容器中各个元素的前后顺序是靠指针来维系的,每个元素都配备了 2 个指针,分别指向它的前一个元素和后一个元素。其中第一个元素的前向指针总为 null,因为它前面没有元素;同样,尾部元素的后向指针也总为 null。
编辑
这大概就是双向链表的样子,正常的链表只有一个指针指向他的下一个元素,而双向就是再单向的前提上加上一个指针,指向他前面的元素。
基于这样的存储结构,list 容器具有一些其它容器(array、vector 和 deque)所不具备的优势,即它可以在序列已知的任何位置快速插入或删除元素(时间复杂度为O(1)
)。并且在 list 容器中移动元素,也比其它容器的效率高。
使用 list 容器的缺点是,它不能像 array 和 vector 那样,通过位置直接访问元素。举个例子,如果要访问 list 容器中的第 6 个元素,它不支持容器对象名[6]
这种语法格式,正确的做法是从容器中第一个元素或最后一个元素开始遍历容器,直到找到该位置。