查漏补缺：C++STL简述（容器部分）

查漏补缺：C++STL简述（容器部分）

STL：是Standard Template Library的简称，中文译为标准模板库，是由惠普实验室开发的一系列软件的统称，现为C++的一部分，可分为容器（containers）、迭代器（iterators）、空间配置器（allocator）、配接器（adapters）、算法（algorithms）和仿函数（functors）六部分，本文只简单阐述容器部分。

在C++标准中，STL被组织为下面的17个头文件：、、、、、、、、

容器分两大类：

一、顺序容器：元素在顺序容器中的顺序与其加入容器时的位置相对应。

标准库中的所有顺序容器都提供了快速访问元素的能力，但这些容器在一下方面都有不同的性能折中：

（1）向容器中添加或从容器中删除元素的代价

（2）非顺序访问容器中元素的代价

1、顺序容器类型

（1）vector：可变大小数组，支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢。

（2）deque：双端队列。支持快速随机访问。在头尾位置插入或删除速度很快。

（3）list：双向链表。只支持双向顺序访问。在list中任何位置进行插入或删除操作速度都很快。

（4）forward_list：单向链表。只支持单向顺序访问。在链表任何位置进行插入或删除操作速度都很快。

（5）array：固定大小的数组。支持快速随机访问。不能添加或删除元素。

（6）string：与vector相似的容器，但专门用于保存字符。随机访问快，在尾部插入或删除速度快。

2、顺序容器的选择

通常，vector是最好的选择，除非有很好的理由选择其他容器。一下是选择容器的基本原则：

（1）除非有很好的理由选择其他容器，否则应使用vector。

（2）如果你的程序有很多小的元素，且空间的额外开销很重要，则不要使用list或者forward_list。

（3）如果程序要求随机访问元素，应使用vector或者deque。

（4）如果程序要求在容器中间插入或删除元素，应使用list或forward_list。

（5）如果程序要求在容器头尾位置插入或删除元素，但不会在中间位置插入或删除元素，则使用deque。

（6）如果程序只有在读取输入时需要在容器中间位置插入元素，随后需要随机访问元素，则

----首先，确定是否真的需要在容器中间位置插入元素。当处理输入数据时，通常可以很容易的向vector中追加数据，然后再调用标准库中的sort函数来重排容器中的元素，从而避免在中间位置添加元素。

----如果必须在中间位置插入元素，考虑在输入阶段使用list，一旦输入结束，将list中的内容拷贝到一个vector中。

二、关联容器：关联容器中的元素是按关键字来保存和访问的。关联容器支持高效的关键字查找和访问，主要的两个关联容器：map和set。

map：其中的元素是一些关键字-值（key-value）对，关键字起到索引的作用，值表示与索引相关联的数据。

set：每个元素只能包含一个关键字，支持高效的关键字查询操作----检查给定的关键字是否在set中。

1、标准库中提供了8个关联容器。这8个容器的不同体现在三个维度上：

（1）每个容器或是一个map，或是一个set

（2）或要求不重复关键字，或要求重复关键字

（3）按顺序保存，或者无序保存。

按关键字有序保存的元素：

map：关联数组；保存关键字-值

set：关键字即值，即只保存关键字的容器

multimap：关键字可重复的map

multiset：关键字可重复的set

无序集合：

unordered_map：用哈希函数组织的map

unordered_set：用哈希函数组织的set

unordered_multimap：哈希组织的map，关键字可重复出现

unordered_multiset：哈希组织的set，关键字可重复出现

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。