课程总目录
文章目录
- 一、vector容器
- 二、deque和list容器
- 三、vector、deque、list横向对比
- 四、详解容器是配置stack、queue、priority_queue
- 五、无序关联容器
- 六、有序关联容器
- 七、迭代器
- 八、函数对象
- 九、泛型算法和绑定器
一、vector容器
底层数据结构是动态开辟的数组，每次以原来空间大小的2倍进行扩容
使用前需要包含头文件：#include <vector>
容器中对象的构造析构，内存的开辟释放，是通过空间配置器allocator实现：allocate(内存开辟)、deallocate(内存释放)、construct(对象构造)、destroy(对象析构)
使用方法：
vector<int> vec;
增加：
vec.push_back(20);，在容器末尾增加一个元素，时间复杂度O(1)，有可能会导致容器扩容vec.insert(it, 20);，在迭代器it指向的位置增加一个元素，时间复杂度O(n)，有可能会导致容器扩容
删除：
vec.pop_back();，在容器末尾删除一个元素，时间复杂度O(1)vec.erase(it);，删除迭代器it指向的元素，时间复杂度O(n)
查询：
- 提供了
operator[]重载函数，数组下标的随机访问，例如vec[5]，时间复杂度O(1) iterator，迭代器进行遍历，一定要考虑迭代器失效问题find，for_each等泛型算法- C++11提供的语法糖
foreach，其实就是通过迭代器来实现的
注意：对容器进行连续插入或者删除操作（insert/erase），一定要更新迭代器，否则第一次insert或者erase之后，迭代器就失效了，失效问题详见这里
常用方法：
size();，返回容器底层有效元素的个数empty();，判断容器是否为空reserve();，为vector预留空间，只给容器底层开辟指定大小空间并不添加新的元素resize();，扩容，不仅给容器底层开辟指定大小空间，还会添加新的元素swap();，两个容器进行元素交换
代码示例：元素遍历
vector<int> vec;
for (int i = 0; i < 20; ++i)
vec.push_back(i);
int size = vec.size();
for (int i = 0; i < size; ++i)
cout << vec[i] << " ";
cout << endl;
auto it1 = vec.begin();
for (; it1 != vec.end(); ++it1)
cout << *it1 << " ";
cout << endl;
运行结果：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
代码示例：删除所有偶数
vector<int> vec;
for (int i = 0; i < 20; ++i)
vec.push_back(i);
auto it = vec.begin();
while (it != vec.end())
{
if (*it % 2 == 0)
it = vec.erase(it);
else
++it;
}
int size = vec.size();
for (int i = 0; i < size; ++i)
cout << vec[i] << " ";
cout << endl;
运行结果：
1 3 5 7 9 11 13 15 17 19
代码示例：所有奇数前面加一个比其小1的数
vector<int> vec;
for (int i = 0; i < 20; ++i)
vec.push_back(i);
for (auto it = vec.begin(); it != vec.end(); ++it)
{
if (*it % 2 == 1)
{
it = vec.insert(it, *it - 1);
++it;
}
}
int size = vec.size();
for (int i = 0; i < size; ++i)
cout << vec[i] << " ";
cout << endl;
运行结果：
0 0 1 2 2 3 4 4 5 6 6 7 8 8 9 10 10 11 12 12 13 14 14 15 16 16 17 18 18 19
代码示例：reserve预留空间
reserve只是预留空间，只给容器底层开辟指定大小空间并不添加新的元素
默认定义的vector底层开辟空间为0，第一次push_back插入从0变更为1，再变为2,4,8,16,32…，一直进行二倍扩容，扩容频繁，效率太低，假如开始知道问题的数据量大小，即可使用reserve预留空间
vector<int> vec;
vec.reserve(20);
cout << vec.empty() << endl;
cout << vec.size() << endl;
for (int i = 0; i < 20; ++i)
vec.push_back(i);
cout << vec.empty() << endl;
cout << vec.size() << endl;
运行结果：
1
0
0
20
代码示例：resize扩容
resize扩容，不仅给容器底层开辟指定大小空间，还会添加新的元素，没有指定添加的元素值则为0
vector<int> vec;
vec.resize(10);
cout << vec.empty() << endl;
cout << vec.size() << endl;
for (int i = 0; i < 20; ++i)
vec.push_back(i);
cout << vec.empty() << endl;
cout << vec.size() << endl;
int size = vec.size();
for (int i = 0; i < size; ++i)
cout << vec[i] << " ";
cout << endl;
运行结果：
0
10
0
30
0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
若改为vec.resize(10，3);，则运行结果为：
0
10
0
30
3 3 3 3 3 3 3 3 3 3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
二、deque和list容器
deque：使用前需要包含头文件：#include <deque>
双端队列容器，底层数据结构为动态开辟的二维数组。 一维数组从2开始，以2倍的方式进行扩容，每次扩容后，原来第二维的数组，从新的第一维数组的下标oldsize/2开始存放（也就是扩容之后的中间），前后都预留相同的空行，方便支持双端的元素添加
随着元素增加：
如果继续增加呢？会对第一维扩容
使用方法：
deque<int> deq;
增加：
deq.push_back(20);，从末尾添加元素，时间复杂度O(1)，可能引起扩容deq.push_front(20);，从首部添加元素，时间复杂度O(1)，可能引起扩容。vector中没有该方法，需要使用vec.insert(vec.begin(), 20)，O(n)deq.insert(it, 20);，迭代器it指向的位置添加元素，时间复杂度O(n)
删除：
deq.pop_back();，从末尾删除元素，时间复杂度O(1)deq.pop_front();，从首部删除，时间复杂度O(1)deq.erase(it);，迭代器it指向的位置进行元素删除，时间复杂度O(n)
查询：
iterator，迭代器进行遍历，一定要考虑迭代器失效问题（连续的insert或erase）
常用方法：
size();，返回容器底层有效元素的个数empty();，判断容器是否为空resize();，扩容，不仅给容器底层开辟指定大小空间，还会添加新的元素swap();，两个容器进行元素交换
list：使用前需要包含头文件：#include <list>
底层数据结构为双向循环链表，结点中包括data、pre、next
与vector和deque不同，list允许高效地在任何位置插入和删除元素，但不支持随机访问
使用方法：
list<int> MyList;
增加：
MyList.push_back(20);，从末尾添加元素，时间复杂度O(1)，可能引起扩容MyList.push_front(20);，从首部添加元素，时间复杂度O(1)，可能引起扩容MyList.insert(it, 20);，迭代器it指向的位置添加元素，时间复杂度O(1)，但是往往要考虑搜索到指定位置的时间
删除：
MyList.pop_back();，从末尾删除元素，时间复杂度O(1)MyList.pop_front();，从首部删除，时间复杂度O(1)MyList.erase(it);，迭代器it指向的位置进行元素删除，时间复杂度O(1)，但是往往要考虑搜索到指定位置的时间
查询：
iterator，迭代器进行遍历，一定要考虑迭代器失效问题（连续的insert或erase）
常用方法：
size();，返回容器底层有效元素的个数empty();，判断容器是否为空resize();，扩容，不仅给容器底层开辟指定大小空间，还会添加新的元素swap();，两个容器进行元素交换
deque和list的使用实例与vector类似，这里就不再写了
三、vector、deque、list横向对比
vector特点：底层是动态开辟的数组，内存是连续的，以2倍的方式进行扩容。当我们默认定义一个vector时候vector<int> vec;，容器底层没有开辟空间，当添加元素时候才开始以0 -> 1 -> 2 -> 4 -> 8...这种方式进行扩容，用原来老内存上的对象在新内存的空间上进行拷贝构造，再析构老内存上的对象并释放老内存，扩容效率低下。我们可以用reserve函数预留空间，但注意reserve并未添加元素
deque特点：底层是动态开辟的二维数组空间，第二维是固定长度的数组空间，扩容时候（第一维的数组进行2倍扩容，原来的第二维的数组放入新扩容的数组中间，即oldsize/2的位置），前后插入删除操作的时间复杂度都是O(1)
那么，deque底层的内存是否是连续的呢？
并不是！deque的第二维都是独立new出来的，也就是说，每一个第二维是连续的，并不是所有的第二维连续，可以说是分段连续的
vector与deque之间的区别：
- 底层数据结构：看上面两者的特点
- 前后删除元素的时间复杂度：末尾插入删除都为O(1)，但在最前面进行元素添加删除时候
deque为O(1)，vector为O(n)。那么，如果现在需求是前后都能插入删除，就选择deque而不选择vector - 内存使用效率：
vector低，因为vector需要的内存空间必须是连续的；deque第二维内存空间分段连续就行，不用整片连续，可以分块进行数据存储，对内存使用效率更高 - 在中间进行
insert或者erase，vector与deque的效率：它们时间复杂度都为O(n)，但vector内存完全连续，在中间进行插入删除元素的时候容易移动；但deque的第二维内存不完全连续，例如在删除一个元素之后，其他元素会一个一个往前挪动，会进行不同内存片段之间的挪动，元素移动更加麻烦一些，效率不如vector
vector与list之间的区别：
- 底层数据结构：动态开辟的数组 vs 双向循环链表。那也就是在问数组和链表之间的区别
- 数组增加删除O(n)，查找O(n)，随机访问为O(1)
- 链表增加删除一个结点本身为O(1)，但查找某元素的时间为O(n)
- 那么，如果增加删除使用多，优先使用
list；如果随机访问使用多，优先使用vector
四、详解容器是配置stack、queue、priority_queue
五、无序关联容器
六、有序关联容器
七、迭代器
八、函数对象
九、泛型算法和绑定器
还有一些STL方面的总结，可以看看这篇文章：C++STL容器内容总结
