向量和列表

vector

1.vector的介绍

https://legacy.cplusplus.com/reference/vector/vector/?kw=vector

点击上面链接，进去搜索vector，就会有相应的文档介绍了。

使用STL的三个境界：能用，明理，能扩展，那么学习vector，也是按照这个方法进行的。

    我们在学习CPP的时候，一定要学会看文档。其实vector就是我们再C语言学习的顺序表，只不过，我们再C学习的时候，每次都需要手撕代码。而到了C++就不用了，STL已经帮我们写好了，我们只需要去学习，并熟悉它的使用方法就行了。

2.构造和析构

下面，我们需要来熟悉一下，vector的构造，析构和赋值。

构造和赋值，都比较简单，而析构的话，编译器会自动析构，不用我们显式的调用析构。

还有就是vector也可以存储vector。

int main()
{
    //相当于二维数组
    vector<vector<int>> vv;
    //顺序表里面存的是string对象
    vector<string> tmp;


	return 0;
}

当然，不仅限于这些内置类型，容器这些。我们的自定义类型也可以存储。比如我们前面写的日期类，也可以进行使用vector存储。

3.迭代器操作

其实，我们前面讲的string类，其实底层也和顺序表类似的，说一说不仅仅是迭代器操作，还是其他的操作，接口都是类似的。我们这里就不一一演示了。

4.capacity

1.max_size

这里需要解释一下，max_size这个接口，它表示的是返回vector能够储存的最大容量大小。但是这也和内存有关系，也和栈上面的空间有联系的，它不一定能够到达最大容量。

2.shrink_to_fit

这个接口的意思是，让容器的容量缩小到适应其的长度。但这个适应的长度也和编译器有相关，也可能刚好和size一样大，也可能比size要大。

然后其他的接口相对来说比较简单，我们再string也讲过，就不说了。

5.成员接口

 由于vector底层其实就是数组，所以可以使用下标访问，前面我们说了at 其实和[ ] 访问差不多，但是我们应该都习惯使用 下标加 [ ]。

然后，front 我们应该也用的比较少，我们可以直接访问 [ 0] 就行了，这样反而更麻烦。back 相对来说可能用得多一点 ， 但是 我们也可以使用  [ size()] 来访问。 相对来说back 和 front 在 list 里使用更加方便。

6. 修改（modify）

1.assign（分配）

这个接口，就是给vector分配多少个空间，并进行初始化。 

像这样，就为vector 分配了100个空间，并用4来初始化了。

2.emplace

emplace的使用就是和insert 差不多的，我们平常使用的insert 较多一点，使用insert 也是可以的。

vector的使用我们就先说到这里，下面来看一看list。

list

1.list 的介绍

      list 就是链表，但是链表又分为 单向带头和不带头链表，双向带头和不带头链表。我们这里学习的STL中的list是双向带头链表。

       list相较于vector的使用就会复杂一点。下面我们来了解一下。

       list的使用：list中的接口比较多，只需要掌握如何正确的使用，然后再去深入了解底层是怎样实现的，已经可以达到扩展的能力。

2.构造析构赋值

析构一般也不需要我们显式调用，编译器会自动调用。

3.迭代器

迭代器的使用也和前面的容器差不多的。我们后面主要讲迭代器的底层实现。

4.capacity

5.成员接口

对于list来说，无法做到随机访问，只能访问front 和 back，如果要找某一个成员的话，就只能遍历链表了。

6.modify

modify的接口也没有什么特别的，特别的是加入了 swap 和clear。

swap 其实就是交换两个链表的值，也没有什么好说的。

clear 这个接口就是清除所有的节点，只留哨兵位，但是它的空间长度不会改变，智慧改变size（）的大小。

7.其它操作函数

1.reverse

reverse 就是将链表反转，我们只需要调用它即可。 然后，再标准库中还有一个reverse函数，那一个迭代器就需要我们传入迭代器区间进行反转。

2.merge 和 sort

这两个操作是排序，merge就是归并排序，sort 底层使用的快速排序。

3.unique

unique 这个函数是删除链表中的重复的元素，如果有多个，就只留下第一个，删除后面相同的元素。

4.splice

splice 是拼接的意思，我们可以把另一个链表，拼接到第一个链表的任何位置。

总结

     说到最后，我们来说一说list 和 vector的优缺点。

List

优点：

1. 动态大小：list 可以根据需要动态增加或减少大小，不需要预先定义大小。
2. 插入和删除操作高效：在中间位置插入或删除元素的时间复杂度为 O(1)，不需要移动其他元素。
3. 内存使用灵活：可以不连续地存储节点，特别是在大数据量需要频繁插入和删除时更具优势。

缺点：

1. 访问速度慢：与 vector 相比，随机访问（如根据索引访问元素）的时间复杂度为 O(n)，因为需要从头遍历到指定位置。
2. 内存开销大：每个节点需要额外的内存存储前驱或后继指针，相比之下，vector 的内存开销较小。
3. Cache(高速缓存） 效率低：由于节点的内存位置不连续，可能导致缓存命中率降低，影响性能。

Vector

优点：

1. 随机访问速度快：支持 O(1) 的随机访问，可以直接通过索引访问元素。
2. 内存开销小：元素存储在连续的内存块中，开销相对较小，适合存储大量数据。
3. Cache（高速缓存） 效率高：由于内存连续，可以更好地利用 CPU 缓存，提高性能。

缺点：

1. 插入和删除操作效率低：在中间位置插入或删除元素的时间复杂度为 O(n)，需要移动大量元素。
2. 容量限制：尽管 vector 支持动态扩展，但当达到容量时，可能需要重新分配更大的内存，涉及到元素的拷贝，性能消耗较大。
3. 不支持高效的链式数据结构特性：例如，无法在中间部分高效地插入或删除节点。

总结

• 选择 list：当需要频繁在集合中间插入或删除元素时，或者不在乎访问速度时。
• 选择 vector：当需要高效的随机访问和更小的内存开销，且插入和删除操作相对较少时。

根据具体的使用场景和需求来决定应该使用哪种数据结构是很重要的。