STL容器总结

2023-12-27 09:27:09

STL容器

    STL 提供有 3 类标准容器，分别是序列式容器、关联式容器和无序关联式容器，其中后两类容器有时也统称为关联容器。如图所示：

STL容器总结

    序列式容器：所谓序列式容器，即以线性排列（类似普通数组的存储方式）来存储某一指定类型（例如 int、double 等）的数据，需要特殊说明的是，该类容器并不会自动对存储的元素按照值的大小进行排序。

    关联式容器：关联式容器在存储元素值的同时，还会为各元素额外再配备一个值（又称为“键”，其本质也是一个 C++ 基础数据类型或自定义类型的元素），它的功能是在使用关联式容器的过程中，如果已知目标元素的键的值，则直接通过该键就可以找到目标元素，而无需再通过遍历整个容器的方式。使用关联式容器存储的元素，都是一个一个的“键值对”（ <key,value> ），这是和序列式容器最大的不同。除此之外，序列式容器中存储的元素默认都是未经过排序的，而使用关联式容器存储的元素，默认会根据各元素的键值的大小做升序排序。

    无序关联式容器：和关联式容器相比，无序容器具有以下 2 个特点：

1）无序容器内部存储的键值对是无序的，各键值对的存储位置取决于该键值对中的键。

2）和关联式容器相比，无序容器擅长通过指定键查找对应的值（平均时间复杂度为 O(1)）；但对于使用迭代器遍历容器中存储的元素，无序容器的执行效率则不如关联式容器。

    考虑到“键值对”并不是普通类型数据，C++ STL 标准库提供了 pair 类模板，其专门用来将 2 个普通元素 first 和 second（可以是 C++ 基本数据类型、结构体、类自定的类型）绑定在一起，创建成一个新元素。 这就为 map<T1, T2> 提供的存储的基础。pair 类模板定义在<utility>头文件中，所以在使用该类模板之前，需引入此头文件。定义如下所示：

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) {}
#ifdef __STL_MEMBER_TEMPLATES
  template <class U1, class U2>
  pair(const pair<U1, U2>& p) : first(p.first), second(p.second) {}
#endif
};
​
//重载实现
template <class T1, class T2>
inline bool operator==(const pair<T1, T2>& x, const pair<T1, T2>& y) 
{ 
  return x.first == y.first && x.second == y.second; 
}
template <class T1, class T2>
inline bool operator<(const pair<T1, T2>& x, const pair<T1, T2>& y) 
{ 
  return x.first < y.first || (!(y.first < x.first) && x.second < y.second); 
}

pair类模板中提供了以下构造函数

//1) 默认构造函数，即创建空的 pair 对象
pair();
​
//2) 直接使用 2 个元素初始化成 pair 对象
pair (const first_type& a, const second_type& b);
​
//3) 拷贝（复制）构造函数，即借助另一个 pair 对象，创建新的 pair 对象
template<class U, class V> pair (const pair<U,V>& pr);
​
//4) 移动构造函数
template<class U, class V> pair (pair<U,V>&& pr);
​
//5) 使用右值引用参数，创建 pair 对象
template<class U, class V> pair (U&& a, V&& b);

    关联式容器中，map 容器存储的都是 pair 对象，也就是用 pair 类模板创建的键值对。

 

STL容器底层实现和特点总结

    除以上容器外，STL还提供了容器适配器。简单的理解容器适配器，其就是将不适用的序列式容器（包括 vector、deque 和 list）变得适用。容器适配器的底层实现为，通过封装某个序列式容器，并重新组合该容器中包含的成员函数，使其满足某些特定场景的需要。

    STL 提供了 3 种容器适配器，分别为 stack 栈适配器、queue 队列适配器以及 priority_queue 优先权队列适配器。 其中，各适配器所使用的默认基础容器以及可供用户选择的基础容器。       所以，C++ STL一共提供了以下四种类型的容器：

    1）序列式容器：array、vector、deque、list 和 forward_list；

    2）关联式容器：map、multimap、set 和 multiset；

    3）无序关联式容器：unordered_map、unordered_multimap、unordered_set和 unordered_multiset；

    4）容器适配器：stack、queue 和 priority_queue。

（1）各个STL容器的底层实现机制和特性

序列式容器：

1）vector(底层数据结构：动态数组)

优点：

  • 在内存中是分配一块连续的内存空间进行存储，可以像数组一样操作，并且支持动态扩容。

  • 支持快速随机访问，访问的时间复杂度为O(1)。

  • 节省空间。

缺点：

  • 由于其顺序存储的特性，插入删除操作的时间复杂度为 O(n)。

  • 只能在末端进行 pop 和 push。

  • 当动态长度超过默认分配大小后，要整体重新分配、拷贝和释放空间。

2）list(底层数据结构：双向链表)

优点：

  • 在内部方便进行插入删除操作，插入删除的时间复杂度为O(1)。

  • 可在两端进行push和pop操作。

缺点：

  • 内存空间是不连续的，只能通过指针访问数据，不支持随机访问，访问的时间复杂度为O(n)。

  • 涉及对额外指针的维护，相对于 vector 占用内存多。

3）deque(底层数据结构：一个*控制器和多个缓冲区)

优点：

  • deque结合了 vector 和 list，元素的随机访问方便，访问的时间复杂度为O(1)。

  • 在内部方便进行插入删除操作，插入删除的时间复杂度为O(1)。

  • 可在两端进行 push、pop

缺点：

  • 因为涉及比较复杂，采用分段连续空间，所以占用内存相对多。

 

关联式容器：

容器名 底层实现 键值重复 插入元素 迭代器性质
set 红黑树 不允许 insert_unique const_iterator
multiset 红黑树 允许 insert_equal const_iterator
unordered_set 哈希表 不允许 insert_unique const_iterator
unordered_multiset 哈希表 允许 insert_equal const_iterator
map 红黑树 不允许 insert_unique 非const_iterator
multimap 红黑树 允许 insert_equal 非const_iterator
unordered_map 哈希表 不允许 insert_unique 非const_iterator
unordered_multimap 哈希表 允许 insert_equal 非const_iterator

 

适配器：

容器名 底层实现 特点 应用场景
stack deque 先进后出，只允许在栈顶添加和删除元素，称为出栈和入栈 常见栈的应用场景包括括号问题的求解，表达式的转换和求值，函数调用和递归实现，深度优先遍历 DFS 等
queue deque 先进先出，在队首取元素，在队尾添加元素，称为出队和入队 常见的队列的应用场景包括计算机系统中各种资源的管理，消息缓冲队列的管理和广度优先遍历 BFS 等
priority_queue deque 是以 vector 为容器以 heap为数据操作的配置器，在创建时，都制定了一种排序规则，priority_queue 容器适配器为了保证每次从队头移除的都是当前优先级最高的元素，每当有新元素进入，它都会根据既定的排序规则找到优先级最高的元素，并将其移动到队列的队头；同样，当 priority_queue 从队头移除出一个元素之后，它也会再找到当前优先级最高的元素，并将其移动到队头 。

 

（2）各个STL容器的使用场景 考虑因素如下：

1）是否需要在容器的指定位置插入新元素？如果需要，则只能选择序列式容器，而关联式容器和哈希容器 是不行的；

2）是否对容器中各元素的存储位置有要求？如果没有，则可以考虑使用哈希容器，反之就要避免使用哈希容器；

3）是否需要使用指定类型的迭代器？举个例子，如果必须是随机访问迭代器，则只能选择 array、vector、deque；如果必须是双向迭代器，则可以考虑 list 序列式容器以及所有的关联式容器；如果必须是前向迭代器，则可以考虑 forward_list 序列式容器以及所有的哈希容器；

4）当发生新元素的插入或删除操作时，是否要避免移动容器中的其它元素？如果是，则要避开 array、vector、deque，选择其它容器；

5）容器中查找元素的效率是否为关键的考虑因素？如果是，则应优先考虑哈希容器。

 

参考：

  1. 《STL源码剖析》

  2. http://c.biancheng.net/

上一篇：C++STL标准库容器


下一篇：STL模板整理