03 容器

顺序容器:其中的元素能被顺序访问

  • vector

  • list

  • deque

  • arrays

  • forward_list

容器适配器:为顺序容器提供了不同的接口

  • queue

  • priority_queue

  • stack

关联容器:内部数据有序,支持快速搜索(O(logn)时间复杂度)

  • set

  • multiset

  • map

  • multimap

无序关联容器:内部数据无序,支持快速搜索

  • unordered_set

  • unordered_multiset

  • unordered_map

  • unordered_multimap

3.1 vector

简单来讲vector就是动态数组,会自动调整占用的内存大小。在尾部插入和删除一个元素是常量时间复杂度(如果插入时要扩容则例外)。在中间插入和删除一个元素则是线性时间复杂度。

Iterators

  • begin() - 返回指向第一个元素的迭代器

begin() – Returns an iterator pointing to the first element in the vector end() – Returns an iterator pointing to the theoretical element that follows the last element in the vector rbegin() – Returns a reverse iterator pointing to the last element in the vector (reverse beginning). It moves from last to first element rend() – Returns a reverse iterator pointing to the theoretical element preceding the first element in the vector (considered as reverse end) cbegin() – Returns a constant iterator pointing to the first element in the vector. cend() – Returns a constant iterator pointing to the theoretical element that follows the last element in the vector. crbegin() – Returns a constant reverse iterator pointing to the last element in the vector (reverse beginning). It moves from last to first element crend() – Returns a constant reverse iterator pointing to the theoretical element preceding the first element in the vector (considered as reverse end)