std::vector
动态扩容底层实现
在 C++ 中，std::vector 是一个动态数组，它可以自动扩容以容纳更多元素。其动态扩容的底层机制涉及到内存分配和复制元素。
详细步骤：
初始内存分配：
当创建一个空的 std::vector 或者向一个已有的 std::vector 添加元素时，std::vector 会首先分配一块初始的内存空间。这个内存块的大小通常是小于或等于系统的内存页大小。这是一个较小的固定大小的内存块，称为容量（capacity），通常远远大于 std::vector 中当前元素的数量。它能容纳更多元素，以减少频繁的内存分配操作。
元素添加：
当你向 std::vector 添加元素时，如果元素数量（大小，size）等于容量（capacity），则需要触发扩容操作。
扩容操作：
std::vector的扩容操作会分配一块新的内存区域，通常是当前容量的两倍。然后，它将现有的元素从旧内存复制到新的内存中，以保留现有的数据。
接着，释放旧内存区域。
最后，将新的元素插入到新内存的末尾。
这个过程确保了容器在元素添加时具有线性复杂度，即 O(1) 的均摊时间复杂度，因为扩容操作不会频繁发生，而且每次的扩容是成倍增加的。
重新分配内存：
需要注意的是，每次扩容后，std::vector 的容量会超过实际元素的数量。这种重新分配内存和复制数据的操作可能导致性能开销。因此，在对 std::vector 进行大量元素添加操作时，可以通过 reserve() 函数来预先分配足够的内存，以避免不必要的扩容和复制操作。
两个 vector 一个放普通数据类型一个放指针，扩容有什么区别？
存储普通数据类型的
std::vector：
当
std::vector存储普通数据类型（如整数、浮点数、自定义结构体等）时，容器会在扩容时分配新的内存，并将现有数据复制到新内存中。这意味着在扩容时，每个元素都会进行拷贝构造（如果是自定义数据类型，需要调用其拷贝构造函数），因为新内存中的元素是一个完全独立的拷贝。
存储指针的
std::vector：
当
std::vector存储指针时，容器会在扩容时仅复制指针，而不会复制指针所指向的对象。这是因为指针本身的大小是固定的，通常为 4 字节或 8 字节（根据系统架构），因此拷贝指针的开销很小。但需要注意的是，原始对象（指针所指向的对象）并没有被复制，它们仍然位于原来的内存位置。这意味着，当你修改其中一个
std::vector中的指针指向的对象时，另一个std::vector中的相应指针也会反映这些修改。请特别小心，在释放内存时，不要重复释放同一个内存块。通常情况下，只需要释放一次。
std::string
请用c++ 实现stl中的string类，实现构造，拷贝构造，析构，赋值，比较，字符串相加，获取长度及子串等功能。
/*-------------------------------------
* 日期：2015-03-31
* 作者：SJF0115
* 题目: 实现string类
* 来源：百度
* 博客：
------------------------------------*/
#include <iostream>
#include <cstring>
using namespace std;
class String{
public:
// 默认构造函数
String(const char* str = NULL);
// 复制构造函数
String(const String &str);
// 析构函数
~String();
// 字符串连接
String operator+(const String & str);
// 字符串赋值
String & operator=(const String &str);
// 字符串赋值
String & operator=(const char* str);
// 判断是否字符串相等
bool operator==(const String &str);
// 获取字符串长度
int length();
// 求子字符串[start,start+n-1]
String substr(int start, int n);
// 重载输出
friend ostream & operator<<(ostream &o,const String &str);
private:
char* data;
int size;
};
// 构造函数
String::String(const char *str){
if(str == NULL){
data = new char[1];
data[0] = '\0';
size = 0;
}//if
else{
size = strlen(str);
data = new char[size+1];
strcpy(data,str);
}//else
}
// 复制构造函数
String::String(const String &str){
size = str.size;
data = new char[size+1];
strcpy(data,str.data);
}
// 析构函数
String::~String(){
delete[] data;
}
// 字符串连接
String String::operator+(const String &str){
String newStr;
//释放原有空间
delete[] newStr.data;
newStr.size = size + str.size;
newStr.data = new char[newStr.size+1];
strcpy(newStr.data,data);
strcpy(newStr.data+size,str.data);
return newStr;
}
// 字符串赋值
String & String::operator=(const String &str){
if(data == str.data){
return *this;
}//if
delete [] data;
size = str.size;
data = new char[size+1];
strcpy(data,str.data);
return *this;
}
// 字符串赋值
String& String::operator=(const char* str){
if(data == str){
return *this;
}//if
delete[] data;
size = strlen(str);
data = new char[size+1];
strcpy(data,str);
return *this;
}
// 判断是否字符串相等
bool String::operator==(const String &str){
return strcmp(data,str.data) == 0;
}
// 获取字符串长度
int String::length(){
return size;
}
// 求子字符串[start,start+n-1]
String String::substr(int start, int n){
String newStr;
// 释放原有内存
delete [] newStr.data;
// 重新申请内存
newStr.data = new char[n+1];
for(int i = 0;i < n;++i){
newStr.data[i] = data[start+i];
}//for
newStr.data[n] = '\0';
newStr.size = n;
return newStr;
}
// 重载输出
ostream & operator<<(ostream &o, const String &str){
o<<str.data;
return o;
}
int main(){
String str1("hello ");
String str2 = "world";
String str3 = str1 + str2;
cout<<"str1->"<<str1<<" size->"<<str1.length()<<endl;
cout<<"str2->"<<str2<<" size->"<<str2.length()<<endl;
cout<<"str3->"<<str3<<" size->"<<str3.length()<<endl;
String str4("helloworld");
if(str3 == str4){
cout<<str3<<" 和 "<<str4<<" 是一样的"<<endl;
}//if
else{
cout<<str3<<" 和 "<<str4<<" 是不一样的"<<endl;
}
cout<<str3.substr(6,5)<<" size->"<<str3.substr(6,5).length()<<endl;
return 0;
}std::list
实现原理
内部数据结构是一个双向链表。这意味着它是由一系列节点组成的，每个节点都包含两部分：一部分是存储实际数据的数据域，另一部分是存储指向下一个和上一个节点的指针的指针域。
list中有一个base node，此node并不存储数据，从C++11开始，此_List_node_header中包含一个
std::size_t 类型的成员变量，用来记录list的长度。
struct _List_node_base
{
_List_node_base* _M_next;
_List_node_base* _M_prev;
...
};
struct _List_node_header : public _List_node_base
{
#if _GLIBCXX_USE_CXX11_ABI
std::size_t _M_size;
#endif
...
};c++11 开始 size()的时间复杂度是O(1)，在此之前是O(N)。
如何影响性能的
（1）插入和删除操作的高效性： 由于链表节点不是连续存储的，因此在链表中间插入或删除节点不需要移动其他节点。这使得 std::list 的插入和删除操作的时间复杂度为 O(1)，即常数时间。无论链表的大小如何，这些操作的速度都是恒定的。
（2）不支持随机访问： 由于链表节点不是连续存储的，所以不能通过索引直接访问元素。这意味着你不能直接跳到链表的任意位置。要访问链表中的元素，必须从链表头或尾开始遍历，直到到达所需位置。这使得随机访问链表元素的效率较低。
（3）空间利用率较低： 每个链表节点都需要额外的空间来存储指向下一个和上一个节点的指针。这导致 std::list 的空间利用率比连续存储的容器（如 std::vector）低。然而，这种空间效率的牺牲换来的是插入和删除操作的高效性。
（4）内存分配和释放： 每次插入新节点时，都需要分配新的内存空间。同样，删除节点时会释放相应的内存。这种动态内存分配和释放可能会影响性能，尤其是在大量插入和删除操作的情况下。
总的来说，std::list 的双向链表结构使得它在插入和删除操作方面非常高效，但牺牲了随机访问和空间利用率。因此，在选择使用 std::list 还是其他容器时，需要根据具体的应用场景和需求来权衡这些性能特点。
插入和删除操作的时间复杂度
在 std::list 中，插入和删除操作的时间复杂度都是 O(1)，也就是常数时间复杂度。这是因为 std::list 是基于双向链表实现的，链表中的每个节点都包含指向前一个节点和后一个节点的指针。
对于插入操作：
如果在链表的头部或尾部插入元素，时间复杂度是 O(1)，因为可以直接修改头指针或尾指针。
如果在链表的中间插入元素，例如在第 i 个位置插入一个新元素，时间复杂度同样是 O(1)。这是因为只需更改相邻节点的指针，将新节点插入到链表中，而无需移动其他元素。
对于删除操作：
删除链表的头部或尾部元素同样具有 O(1) 的时间复杂度，因为可以直接修改头指针或尾指针。
删除链表中间的元素，如第 i 个元素，时间复杂度也是 O(1)。这是因为你只需找到要删除元素的前一个节点，然后更改其指针以跳过要删除的元素，并可能还需要更改要删除元素的后一个节点的指针。这些操作都是常数时间内的。
需要注意的是，虽然插入和删除操作的时间复杂度是 O(1)，但如果要在特定位置插入或删除多个元素，总的时间复杂度将是 O(n)，其中 n 是要插入或删除的元素数量。然而，每个单独的操作仍然是 O(1)。
添加和删除元素会导致迭代器失效吗
并不会，因为在任意位置添加和删除元素只需要改变prev/next指针指向的对象，而不需要移动元素的位置，所以不会导致迭代器失效
std::sort 和 list成员函数sort有什么区别吗？
std::sort是STL算法的一部分。它排序的容器需要有随机访问迭代器，所以只能支持vector和deque。list成员函数sort用于list排序，时间复杂度是O(N*logN)。
list的成员函数insert和forward_list的成员函数的insert_after有什么区别？
两者都可以向特定位置添加元素。不同的是insert把元素插入到当前迭代器前，而insert_after把元素插入到当前迭代器后。
std::list 和 std::vector 在性能上有哪些主要的区别
空间利用率：
std::vector：由于其内部实现为连续数组，空间利用率通常较高，因为内存分配是连续的，不容易产生内存碎片。
std::list：链表中的每个节点可能单独分配，这可能导致内存碎片，特别是在频繁插入和删除操作时。
随机访问性能：
std::vector：由于其内部使用数组实现，元素存储在连续的内存空间中，因此随机访问其任何元素的时间复杂度是 O(1)，即常数时间。这使得std::vector在需要频繁随机访问元素时表现出色。
std::list：由于元素是分散在内存中的，不能利用指针进行随机访问，只能顺序访问。这意味着访问列表中的特定元素（除头尾节点外）需要遍历整个列表，时间复杂度为 O(n)，其中 n 是列表中元素的数量。因此，std::list 在随机访问方面性能较差。
插入和删除性能：
std::vector：在向量中间插入或删除元素会导致元素移动，因为需要保持元素的连续性。这通常是一个 O(n) 的操作，因为它可能涉及大量的内存拷贝。然而，在向量末尾添加元素（使用 push_back）通常是 O(1) 操作，因为向量通常会在内部预留一些额外的空间。
std::list：由于链表结构，std::list 在任意位置插入或删除元素都是 O(1) 的操作，因为不需要移动其他元素。这使得std::list在需要频繁插入或删除元素的场景下性能更佳。
内存分配：
std::vector：一次性分配好内存，当空间不足时才进行 2 倍扩容，这可能会导致额外的内存分配和拷贝成本。
std::list：每次插入新节点时都会进行内存申请，每次删除节点时都会释放内存，这可能导致更多的内存分配和释放操作。
迭代器：
std::vector：迭代器是原生态的指针，可以直接进行指针算术运算。
std::list：迭代器是对原生态指针进行了封装，不能直接进行指针算术运算。
综上所述，std::vector 在随机访问和连续存储方面性能较好，适用于需要高效随机访问的场景；而 std::list 在插入和删除操作方面性能更佳，适用于需要频繁插入和删除的场景。在选择使用哪种容器时，应根据具体的应用需求和性能要求来决定。
std::list 和 std::forward_list 有什么不同？
内存布局和存储：
std::list：是一个双向链表，每个节点都包含指向前一个节点和后一个节点的指针。因此，其内存布局相对较大，每个节点都需要额外的空间来存储这些指针。
std::forward_list：是一个单向链表，每个节点只包含指向下一个节点的指针。因此，它的内存布局更紧凑，占用更少的内存。
插入和删除效率：
std::list：由于每个节点都有指向前一个和后一个节点的指针，插入和删除操作可能涉及修改多个指针，因此在某些情况下可能相对较慢。
std::forward_list：由于它只包含指向下一个节点的指针，插入和删除操作通常更高效，因为只需要修改一个指针。
随机访问：
std::list：不支持随机访问，只能通过迭代器顺序访问元素。
std::forward_list：同样不支持随机访问，只能通过迭代器从头部开始顺序访问元素。
接口和用法：
std::list：提供了丰富的接口，包括成员函数和操作符重载，用于执行各种操作，如排序、合并等。
std::forward_list：接口相对有限，主要关注基本的链表操作，如插入、删除和遍历。它被视为对 C 语言风格单链表的封装，并提供了 O(1) 复杂度的元素插入。
空间利用率：
当不需要双向迭代时，std::forward_list 通常具有比 std::list 更高的空间利用率，因为它不需要存储指向前一个节点的指针
std::array
vector 类的功能比数组强大，但付出的代价是效率稍低。如果您需要的是长度固定的数组，使用数组是更佳的选择，但代价是不那么方便和安全。有鉴于此，C++11 新增了模板类 array, 它也位于名称空间 std中。与数组一样，array 对象的长度也是固定的，也使用栈 (静态内存分配)，而不是自由存储区，因此其效率与数组相同，但更方便，更安全。
例：std::array<int,5> arr = {1,2,3,4,5};
array 对象和数组存储在相同的内存区域（即栈）中，而 vector 对象存储在另一个区域（自由存储区或堆）中
可以将一个 array 对象赋给另一个 array 对象 ，而对于数组，必须逐元素复制数据