【C++100问】深度总结STL基本容器的使用
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【C++100问】深度总结STL基本容器的使用，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含16743字，纯文字阅读大概需要24分钟。
内容图文
专栏C++学习笔记
声明
1）本文仅供学术交流，非商用。
2）博主才疏学浅，文中如有不当之处，请各位指出，共同进步，谢谢。
3）此属于第一版本，若有错误，还需继续修正与增删，还望大家多多指点。
4）大家都共享一点点，一起为祖国科研的推进添砖加瓦。
文章目录
- 专栏C++学习笔记
- 声明
- 〇、前言
- 一、C++库引用（Import C++ Library）
- 二、STL（Standard Template Library）
- 三、容器（Containers）
- 四、顺序容器（Sequence containers）
- 五、关联容器（Associative containers）
- 六、适配器（Adaptor）
- 七、无序容器（Unordered associative container）
- 八、sizeof、size和capacity
- 九、总结
- 参考文章
〇、前言
近期终于粗略地学习完了C++的STL容器，决心总结一波，以便复习和记录。
因为是初学者，如果有写的不对的地方，还请各位不吝赐教。
以下是学习笔记总目录（更新中ing），和关于容器的章节习题。
- 《C++ Primer》学习笔记（三）：字符串、向量和数组
- 《C++ Primer》习题参考答案：第3章 - 字符串、向量和数组
- 《C++ Primer》学习笔记（九）：顺序容器
- 《C++ Primer》习题参考答案：第9章 - 顺序容器
- 《C++ Primer》学习笔记（十一）：关联容器
- 《C++ Primer》习题参考答案：第11章 - 关联容器
一、C++库引用（Import C++ Library）
众所周知，常用的库引用如下：
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
有些太多，所以有了一个新奇的方法：
#include <bits/stdc++.h>
一行代码解决一系列代码，方便！
其中 bits/stdc++.h 源码如下：
// C++ includes used for precompiling -*- C++ -*-
// Copyright (C) 2003-2014 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
/** @file stdc++.h
* This is an implementation file for a precompiled header.
*/
// 17.4.1.2 Headers
// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
不过 VS 会报错，网上解决办法一大堆，这里就不过多赘述了。
二、STL（Standard Template Library）
- STL（Standard Template Library），中文名 标准模板库，是一个高效的C++程序库，包含很多常用的 基本数据结构 和 基本算法，为C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。
- 从逻辑层次来看，在STL中体现了 泛型编程思想（generic programming）。
- 从实现层次看，整个STL是以一种 类型参数化（type parameterized） 的方式实现的。
STL有六大组件（容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)）。
但主要是容器、迭代器和算法三个部分：
- 容器（Containers）：用来管理某类对象的集合。对最常用的数据结构提供了支持，每一种容器都有其优点和缺点，为了应付程序中的不同需求。
- 迭代器（Iterators）：用来在一个对象集合的元素上进行遍历动作。这个对象集合或许是个容器，或许是容器的一部分，每种容器都提供了了解该种容器内部结构的迭代器。
- 算法（Algorithms）：用来处理对象集合中的元素。通过所有容器的迭代器提供一致的接口，可以多次复用算法于任意容器之上。
STL 的基本观念就是将数据和操作分离。
- 数据由 容器 进行管理;
- 操作由 算法进行;
- 而 迭代器 在两者之间充当粘合剂，使任何 算法 都可以和任何 容器 交互运作。
三、容器（Containers）
一个容器就是一些特定类型对象的集合，是用来管理某类对象的，从C++11标准以来，C++中STL定义的几种容器的效率非常高，优化的非常好，完全没有必要自己去定义类似的数据结构，了解使用它们，可以满足90%的日常编程需要！本文是 基于C++11标准，基于《C++primer》参考 完成的。
常用的STL基本容器类型分为四类：
-
顺序容器（Sequence containers），为程序员提供了控制元素存储和访问顺序的能力。顺序性容器中的每个元素均有固定的位置，取决于插入时机和地点，和元素值无关，除非用删除或插入的操作改变这个位置。
-
关联容器（Associative containers），支持高效的关键字查找和访问操作。关联容器中各元素间没有严格的物理顺序，取决于特定的排序准则以及元素值，和插入次序无关，元素是有序的集合。默认情况下，标准库使用关键字类型的
<运算符来进行比较操作。
-
无序容器（Unordered associative container），使用 哈希函数 和关键字类型的
==运算符组织元素。在关键字类型的元素没有明显的序关系的情况下，无序容器是非常有用的。在某些应用中，维护元素的序代价非常高昂， 此时无序容器也很有用。使用无序容器通常更为简单(通常也会有更好的性能) 。 -
容器适配器（Adaptor），是标准库中的一个通用概念，容器、迭代器和函数都有适配器。本质上，一个适配器是一种机制，能使某种事物的行为看起来像另外一种事物一样的一种机制。适配器是容器的接口，它本身不能直接保存元素，它保存元素的机制是调用另一种顺序容器去实现，即可以把适配器看作"它保存一个容器，这个容器再保存所有元素"。
其中，STL 提供的 最常用的：
- 四个 顺序容器：
- 向量（vector）；
- 双端队列（deque）；
- 列表（list）；
- 字符串（string）；
- 四个 关联容器：
- 集合（set）；多重集合（multiset）；
- 映射（map）；多重映射（multimap）；
- 三种 适配器：
- 栈（stack）；
- 队列（queue）；
- 优先级队列（priority_queue）；
- 四种 无序容器：
- unordered_map；
- unordered_multimap；
- unordered_set；
- unordered_multiset；
容器类自动申请和释放内存，因此无需new和delete操作。
四、顺序容器（Sequence containers）
4.1）常用操作（共同点）
1_添加元素
2_访问元素
3_删除元素
4_改变容器大小
5_容器操作可能使迭代器失效
向容器中添加或删除元素可能会使指向容器元素的指针、引用或迭代器失效。失效的指针、引用或迭代器不再表示任何元素，使用它们是一种严重的程序设计错误。
- 向容器中添加元素后：
- 如果容器是
vector或string类型，且存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。如果存储空间未重新分配，指向插入位置之前元素的迭代器、指针和引用仍然有效，但指向插入位置之后元素的迭代器、指针和引用都会失效。 - 如果容器是
deque类型，添加到除首尾之外的任何位置都会使迭代器、指针和引用失效。如果添加到首尾位置，则迭代器会失效，而指针和引用不会失效。 - 如果容器是
list或forward_list类型，指向容器的迭代器、指针和引用仍然有效。
- 如果容器是
- 从容器中删除元素后，指向被删除元素的迭代器、指针和引用失效：
- 如果容器是
list或forward_list类型，指向容器其他位置的迭代器、指针和引用仍然有效。 - 如果容器是
deque类型，删除除首尾之外的任何元素都会使迭代器、指针和引用失效。如果删除尾元素，则尾后迭代器失效，其他迭代器、指针和引用不受影响。如果删除首元素，这些也不会受影响。 - 如果容器是
vector或string类型，指向删除位置之前元素的迭代器、指针和引用仍然有效。但尾后迭代器总会失效。
- 如果容器是
4.2）向量（vector）
vector（向量）：事实上和数组差不多，但比数组更优越，一般来说数组不能动态拓展，因此在程序运行的时候不是浪费内存，就是造成越界，而 vector 正好弥补了这个缺陷，它的特征是相当于可变大小的数组（动态数组）。由于元素是连续存储的，随机访问快，在末端插入和删除快，但在中间插入和删除慢。
优缺点：
优点：支持随机访问，即
[]操作和.at()，查询效率高。
?
缺点：当向头部或中部，插入或删除元素，插入效率低。
需要导入头文件 #include <vector>。
1_定义和初始化：
2_简单vector操作
3_关键概念: vector对象能高效增长
C++标准要求 vector 应该能在运行时高效快速地添加元素，因此定义 vector 对象的大小没有必要，事实上性能可能更差，只有一种例外情况，就是所有元素的值都一样！一旦元素的值有所不同，更有效的办法是先定义一个空的 vector 对象，再在运行时向其中添加具体值。
开始的时候创建空的 vector 对象，在运行时再动态添加元素，这一做法与C语言及其他大多数语言中内置数组类型的用法不同，特别是如果用惯了C或者Java，可以预计在创建 vector 对象时顺便指定其容量是最好的，然而事实上，通常的情况是恰恰相反。
4_实例
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> ivec1;
for (int i = 0; i<9; i++)
ivec1.push_back(i);
cout << ivec1.size() << endl;
for (int i = 0; i<ivec1.size(); i++)
cout << ivec1[i] << " ";
cout << endl;
system("pause");
return 0;
}
4.3）双端队列（deque）
deque（双端队列）：是一个更为复杂的数据结构，最大任务就是在这些分段的连续空间上，维护其整体连续的假象，并提供随机存取的接口。与 vector 类似，随机访问快，不过是在两端插入和删除快，但在中间插入和删除慢。
优缺点：
优点：支持随机访问，即
[]操作和.at()，查询效率高；当向两端，插入或删除元素，插入效率高。
?
缺点：当向中部，插入或删除元素，插入效率低。
需要导入头文件 #include <deque>
1_实例
#include <iostream>
#include <deque>
using namespace std;
int main()
{
deque<int> ideq1;
for (int i = 0; i<9; i++)
ideq1.push_back(i);
cout << ideq1.size() << endl;
for (int i = 0; i<ideq1.size(); i++)
cout << ideq1[i] << " ";
cout << endl;
system("pause");
return 0;
}
4.4）列表（list）
list（列表）：由 deque 实现而成，元素也存放在堆中。设计目的是令容器任何位置的添加和删除操作都很快速，作为代价不支持元素的随机访问——为了访问一个元素，只能遍历整个容器。
优缺点：
优点：内存不连续，动态操作，可在任意位置插入或删除且效率高。
?
缺点：不支持随机访问。
需要导入头文件 #include <list>
1_实例
#include <iostream>
#include <list>
using namespace std;
int main(int argc, char* argv[])
{
list<char> ilist;
for (char c = 'a'; c <= 'z'; ++c)
ilist.push_back(c);
cout << ilist.size() << endl;
while (!ilist.empty())
{
cout << ilist.front() << " ";
ilist.pop_front();
}
system("pause");
return 0;
}
4.5）字符串（string）
string（字符串）：表示可变长的字符序列，事实上和 vector 差不多。由于元素是连续存储的，随机访问快，在末端插入和删除快，但在中间插入和删除慢。
优缺点：
优点：支持随机访问，即
[]操作和.at()，查询效率高。
?
缺点：当向头部或中部，插入或删除元素，插入效率低。
需要导入头文件 #include <string>。
1_定义和初始化：
2_简单vector操作
3_处理字符
4_额外操作
5_实例
#include <iostream>
#include <string>
using namespace std;
int main()
{
string ivec1;
for (int i = 0; i<9; i++)
ivec1.push_back('i');
cout << ivec1.size() << endl;
for (int i = 0; i<ivec1.size(); i++)
cout << ivec1[i] << " ";
cout << endl;
system("pause");
return 0;
}
4.6）容器选择
容器选择原则：
- 除非有合适的理由选择其他容器，否则应该使用
vector。 - 如果程序有很多小的元素，且空间的额外开销很重要，则不要使用
list或forward_list。 - 如果程序要求随机访问容器元素，则应该使用
vector或deque。 - 如果程序需要在容器头尾位置插入/删除元素，但不会在中间位置操作，则应该使用
deque。 - 如果程序只有在读取输入时才需要在容器中间位置插入元素，之后需要随机访问元素。则：
- 先确定是否真的需要在容器中间位置插入元素。当处理输入数据时，可以先向
vector追加数据，再调用标准库的sort函数重排元素，从而避免在中间位置添加元素。 - 如果必须在中间位置插入元素，可以在输入阶段使用
list。输入完成后将list中的内容拷贝到vector中。
- 先确定是否真的需要在容器中间位置插入元素。当处理输入数据时，可以先向
- 不确定应该使用哪种容器时，可以先只使用
vector和list的公共操作：使用迭代器，不使用下标操作，避免随机访问。这样在必要时选择vector或list都很方便。
五、关联容器（Associative containers）
5.1）常用操作（共同点）
1_类型别名
2_添加元素
3_删除元素
4_访问元素
5.2）集合（set）和多重集合（multiset）
set（集合）：由红黑树实现，其中每个元素只包含一个关键字并依据其值自动排序，支持高效的关键字查询操作，每个元素值只能出现一次，不允许重复。插入和删除效率比用其他序列容器高，因为对于关联容器来说，不需要做内存拷贝和内存移动。
multiset（多重集合）：唯一的区别是插入的元素可以相同。
优缺点：
优点：关键字查询高效，且元素唯一，以及能自动排序。
?
缺点：每次插入值的时候，都需要调整红黑树，效率有一定影响。
需要导入头文件 #include <set>。
1_实例
#include <iostream>
#include <set>
using namespace std;
int main(int argc, char* argv[])
{
set<int> iset;
iset.insert(3);
iset.insert(1);
iset.insert(2);
iset.insert(1);
set<int>::iterator it;
cout << iset.size() << endl;
for (it = iset.begin(); it != iset.end(); it++)
{
cout << *it << " ";
}
cout << endl;
system("pause");
return 0;
}
5.3）映射（map）和多重映射（multimap）
map（映射）：由红黑树实现，其中每个元素都是一些 键值对（key-value）：关键字起索引作用，值表示与索引相关联的数据。每个元素有一个键，是排序准则的基础。每一个键只能出现一次，不允许重复。插入和删除效率比用其他序列容器高，因为对于关联容器来说，不需要做内存拷贝和内存移动。
multimap（多重映射）：唯一的区别是插入的元素（值）可以相同，即同一个键可以对应多个值。
优缺点：
优点：关键字查询高效，且元素唯一，以及能自动排序。把一个值映射成另一个值，可以创建字典。
?
缺点：每次插入值的时候，都需要调整红黑树，效率有一定影响。
需要导入头文件 #include <map>。
1_实例
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main(int argc, char* argv[])
{
map<int, string> imap;
imap.insert({ 3, "张三" });
imap.insert({ 4, "李四" });
imap.insert({ 1, "王二麻子" });
imap.insert({ 2, "小淘气" });
map<int, string>::iterator it;
for (it = imap.begin(); it != imap.end(); it++)
{
printf("学号：%d 姓名：%s\n", (*it).first, (*it).second.c_str());
}
system("pause");
return 0;
}
六、适配器（Adaptor）
6.1）常用操作（共同点）
6.2）栈（stack）
stack（栈）：LIFO（后进先出）。
需要导入头文件 #include <stack>。
1_基本操作
2_实例
《C++ Primer》习题参考答案：第9章 - 顺序容器 最后一题。
6.3）队列（queue）和优先级队列（priority_queue）
queue（队列）：FIFO（先进先出），即普通的缓冲区（buffer）。
priority_queue（优先级队列）：基于程序员提供的排序准则定义不同的优先权。
需要导入头文件 #include <queue>。
1_基本操作
七、无序容器（Unordered associative container）
7.1）unordered_map/unordered_multimap
7.2）unordered_set/unordered_multiset
无序容器：在关键字类型的元素没有明显的序关系的情况下，无序容器是非常有用的。在某些应用中，维护元素的序代价非常高昂， 此时无序容器也很有用。事实上使用无序容器通常更为简单(通常也会有更好的性能) 。如果关键字类型固有就是无序的，或者性能测试发现问题可以用哈希技术解决，就可以使用无序容器。
1_常用操作（共同点）
通常可以用一个无序容器替换对应的有序容器，反之亦然。但是输出（通常）会不同。
八、sizeof、size和capacity
sizeof操作符统计的是容器vector<int>的大小；size()操作符统计的是容器（vector）内元素的大小；capacity操作符统计的是容器（vector）能存储的容量大小。
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char* argv[])
{
vector<int> ivec;
cout << sizeof(ivec) << endl;
cout << ivec.size() << endl;
cout << ivec.capacity() << endl;
for (int i = 0; i<10; i++)
ivec.push_back(1);
cout << sizeof(ivec) << endl;
cout << ivec.size() << endl;
cout << ivec.capacity() << endl;
system("pause");
return 0;
}
另外：
reserve()操作符统计的是指定容器内能存储元素的数量；resize()操作符统计的是重新指定容器内有效元素的数量；
九、总结
最后送你两张图：
- 第一张：
- 第二张：
参考文章
- 《C++primer》第五版
- 《C++ Primer》学习笔记（十一）：关联容器
- 《C++ Primer》学习笔记（九）：顺序容器
- 《C++ Primer》习题参考答案：第9章 - 顺序容器
- 《C++ Primer》学习笔记（三）：字符串、向量和数组
- https://en.cppreference.com/w/cpp/container
内容总结
以上是互联网集市为您收集整理的【C++100问】深度总结STL基本容器的使用全部内容，希望文章能够帮你解决【C++100问】深度总结STL基本容器的使用所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。