1、内存管理

1、std::vector 维护了两个重要的状态信息：容量（capacity：当前 vector 分配的内存空间大小）和大小（size： vector 当前包含的元素数量）

2、当容量不足以容纳新元素时，std::vector 会分配一块新的内存空间，将原有元素复制到新的内存中，然后释放原内存
std::vector 采用了一种称为“指数增长”的策略进行动态扩容
当需要进行扩容时，std::vector 通常会将容量翻倍，以避免频繁的内存分配操作，从而减少系统开销
这种指数增长策略 确保了平均情况下的插入操作具有常数时间复杂度

3、在频繁插入或删除元素的情况下，std::vector 可能不是最佳选择，因为这样的操作可能触发频繁的动态扩容，导致性能下降
考虑使用 std::deque 或 std::list 这样的容器，对插入和删除操作有更好的性能

2、vector 工作原理

1、当调用 vector 的 push_back 等方法时，vector 可能会重新分配其底层的动态数组以适应新元素。这通常涉及申请新的更大的内存块，复制现有元素到新内存，添加新元素，然后释放旧的内存块。在 C++ 官方实现的 vector 中，这种动态内存管理通常是通过分配器来完成的，vector 使用一个默认的分配器 std::allocator，它封装了动态内存分配函数，如 new 和 delete

虚线以上的内存为 栈内存，虚线以下的内存为 堆内存
红色区域为 vector 对象控制结构存储的位置
紫色区域和灰色区域 为存储元素的数组的位置, 其中紫色区域 表示已经使用, 灰色区域 表示未使用

2、std::vector的存储位置 取决于两个方面：vector本身的对象、它管理的元素、该类对象的存储位置
1）std::vector 对象本身：这个对象是 一个轻量级的结构体，包含了 指向其元素的指针、元素的大小和容量等信息。这个结构体 本身可以存储在栈上或堆上，具体取决于 如何创建 vector

如果 在函数内部直接声明一个 vector（被直接声明为一个局部变量），它就会被分配在 栈上：

void func() {std::vector<int> vec; // vec对象在栈上
}

如果你通过 new 关键字动态分配 vector，那么它的结构体对象会被分配在 堆上：

std::vector<int>* vec = new std::vector<int>; // vec对象在堆上

2）std::vector 的元素：std::vector 管理的元素始终存储在堆上。无论 vector 对象本身在栈上还是堆上，它内部管理的元素总是 动态分配的，即在堆上。这是因为 vector 的容量可以动态扩展，因此 无法在栈上存储不确定大小的元素数组

std::vector<int> vec; // vec对象在栈上
vec.push_back(1); // 元素1存储在堆上

3）如果std::vector 是某个类的成员变量，那么它的存储位置 取决于 该类对象的存储位置。如果类对象在栈上，那么 vector 也在栈上；如果类对象在堆上，那么 vector 也在堆上。例如：

class MyClass {std::vector<int> vec; // vec的存储位置取决于MyClass对象的存储位置
};void func() {MyClass obj; // obj在栈上，因此vec在栈上MyClass* pObj = new MyClass(); // pObj指向堆上的对象，因此vec在堆上
}

2.1 不同类型的变量的存储位置

1、栈（Stack）：局部变量（在栈上分配，分配和释放速度快，局部const变量，通常存储在栈上）、函数参数、临时对象
堆（Heap）：动态分配的变量
数据段（Data Segment）：全局变量、静态变量：全局变量和静态变量 在程序开始时分配，直到程序结束时 才会被释放

int globalVar = 10; // 全局变量
static int staticVar = 20; // 静态变量

只读数据段（Read-Only Data Segment）：常量（程序运行期间一直存在）、字符串字面量

const char* str = "Hello"; // 字符串字面值

2、局部变量、函数参数、临时对象通常分配在栈上，而动态分配的变量则分配在堆上

1. 栈（Stack）的特点
   栈的内存管理 由编译器自动处理。函数调用时 会在栈上分配一个称为“栈帧”的内存区域，用于存储局部变量、函数参数和返回地址。当函数结束时，栈帧自动释放，栈指针复位，内存立即回收
   分配速度：由于栈的内存分配是 连续的且自动管理，分配和释放内存的速度非常快，适合存储短生命周期的小型数据
   限制：栈的大小通常受限于 操作系统，因此不适合存储大数据块 或 生命周期较长的对象

2. 堆（Heap）的特点
   结构：堆是一块较大的、灵活的内存区域，允许 不连续的内存分配。内存分配器（如malloc或new）管理堆上的内存分配和释放
   管理方式：堆上的内存分配 和 释放需要程序员手动管理。内存可以在程序的任何时候分配，并在不再需要时释放。堆上的内存 不依赖于函数调用的层次结构，因此适合存储需要动态大小 或 长生命周期的数据
   分配速度：由于堆 需要查找合适大小的内存块，内存分配和释放 比栈慢。堆的碎片化问题 也会影响内存分配效率
   优点：堆可以存储任意大小的数据块，且生命周期由程序员控制，因此适合 需要跨函数或线程共享的数据

3. 为什么选择栈还是堆？
   栈：
   适合生命周期短且大小固定的变量（如局部变量、函数参数）
   内存分配和释放速度快，但空间有限
   堆：
   适合需要动态大小、复杂结构 或 跨函数共享的数据（如动态数组、大对象）
   内存管理 由程序员控制，提供灵活性，但分配和释放速度较慢

2.2 更多关于堆

堆能够实现 一块较大的、灵活的内存区域，并允许 不连续的内存分配，这主要是由于 堆的结构和管理方式与栈的显著不同

1. 堆的结构
   非连续内存：堆内存不需要是连续的。与栈不同，堆内存 可以在物理地址上不连续，这意味着 堆能够利用整个可用内存空间，而不仅仅是 栈这种线性分配模式下的连续块
   自由分配：堆内存的分配是动态的，可以按需分配和释放。内存管理器 会跟踪已分配的内存块 和 可用的空闲块，从而在程序运行时 根据需要分配和回收内存
2. 内存分配器
   分配策略：堆内存的分配 通常由操作系统或运行时库中的内存分配器（如malloc、new等）管理。内存分配器会根据 不同的分配策略（如首次适配、最佳适配、最差适配）来查找 适合的空闲块并进行分配
   空闲块管理：内存分配器 维护一个空闲块列表 或 其他数据结构来管理未使用的内存。这使得 分配器可以分配不连续的内存块，而不需要 像栈那样严格按照内存顺序分配
   碎片化处理：堆的灵活性带来了 内存碎片化的可能性。内存分配器 会通过合并相邻的空闲块 或 采用更智能的分配算法来减少碎片化的影响
3. 堆的大小与灵活性
   堆的大小：堆的大小通常 远大于栈，具体取决于 操作系统和硬件配置。因为堆在进程地址空间中 占据了一大片区域，可以容纳大量数据，适合存储 需要大量内存的大对象
   灵活性：由于堆 允许非连续的内存分配，程序可以在 不同时间请求不同大小的内存块，而不受限于之前的分配。这种灵活性 使得堆能够满足复杂数据结构和应用程序的需求，如链表、树、图等，它们通常需要动态分配内存
4. 内存分配和释放的独立性
   独立分配和释放：在堆上分配的内存块 可以在任何时候独立释放，而不影响其他内存块。这与栈不同，栈只能按照 LIFO 顺序释放内存
   动态大小：由于堆 允许动态分配和释放内存，程序可以根据 实际需求调整内存使用，而无需在编译时确定大小。这种灵活性 使得堆特别适合 需要动态调整大小的数据结构

3、实现vector

3.1 功能和特性

设计一个名为 MyVector 的 Vector 类，该类应具备以下功能和特性：

1、基础成员函数：
构造函数：初始化 Vector 实例
析构函数：清理资源，确保无内存泄露
拷贝构造函数：允许通过现有的 MyVector 实例来创建一个新实例
拷贝赋值操作符：实现 MyVector 实例之间的赋值功能

2、核心功能：
添加元素到末尾：允许在 Vector 的末尾添加新元素
获取元素个数：返回 Vector 当前包含的元素数量
获取容量：返回 Vector 可以容纳的元素总数
访问指定索引处的元素：通过索引访问特定位置的元素
在指定位置插入元素：在 Vector 的特定位置插入一个新元素
删除数组末尾元素：移除 Vector 末尾的元素
清空数组：删除 Vector 中的所有元素，重置其状态

3、迭代与遍历：
使用迭代器遍历：实现迭代器以支持对 Vector 从开始位置到结束位置的遍历
遍历并打印数组元素：提供一个函数，通过迭代器遍历并打印出所有元素

4、高级特性：
容器扩容：当前容量不足以容纳更多元素时，自动扩展 Vector 的容量以存储更多元素

3.2 输入和输出

题目的包含多行输入，第一行为正整数 N, 代表后续有 N 行命令序列
输入示例：

15
push 20
push 30
push 40
print
insert 0 10
size
print
get 1
pop
print
iterator
foreach
clear
size
print

输出示例：

20 30 40 
4
10 20 30 40 
20
10 20 30 
10 20 30 
10 20 30 
0
empty

3.3 代码实现

#include <iostream>
#include <algorithm>
#include <stdexcept>
#include <string>
#include <sstream> // istringstreamtemplate <typename T>
class Vector {
private:T* elements;size_t capacity;size_t size;public:Vector() : elements(nullptr), capacity(0), size(0) {}~Vector() {delete[] elements;}Vector(Vector& vec) : capacity(vec.capacity), size(vec.size) { // 深拷贝elements = new T[capacity]; // 是capacity，不是sizestd::copy(vec.elements, vec.elements + size, elements);}Vector& operator=(Vector& vec) { // 深拷贝，跟拷贝构造函数很像if (*this != vec) { // 注意自赋值delete[] elements;elements = new T[capacity];capacity = vec.capacity;size = vec.size;std::copy(vec.elements, vec.elements + size, elements);}return *this;}void push_back(T& e) {if (size == capacity)reserve(capacity == 0 ? 1 : 2 * capacity);elements[size++] = e; // 指针可以直接用下标操作}size_t getSize() {return size;}size_t getCapacity() {return capacity;}T& operator[](size_t pos) { // 要返回T&if (pos >= size)throw std::out_of_range("index out of range");return elements[pos];}void insert(size_t pos, const T& ele) {if (capacity <= size) {reserve(capacity == 0 ? 1 : 2 * capacity);}if (pos >= size)throw std::out_of_range("index out of range");for (size_t i = size; i > pos; i--) {elements[i] = elements[i - 1];}elements[pos] = ele;++size; // 别忘了}void pop_back() {if (size > 0)size--;}void clear() {size = 0;}// 使用迭代器遍历数组的开始位置，就是指针// 非const版本的迭代器允许对容器中的元素进行修改// 例如，在一个非const的vector对象上使用begin()和end()返回的迭代器，可以对元素执行修改操作// 非const版本：// for (auto it = vec.begin(); it != vec.end(); ++it) {//      *it = *it * 2; // 修改元素值// }T* begin() {return elements;}T* end() {return elements + size;}// const版本的迭代器用于不允许修改容器内容的场景。// 在一个const的vector对象上使用begin()和end()，返回的是const版本的迭代器，它只允许读取元素，而不能修改它们// const版本:// const std::vector<int> vec = {1, 2, 3, 4, 5};// for (auto it = vec.begin(); it != vec.end(); ++it) {//      std::cout << *it << " "; // 只读，不允许修改元素// }const T* begin() const {return elements;}const T* end() const {return elements + size;}void printElements() {for (size_t i = 0; i < size; i++) {std::cout << elements[i] << " ";}std::cout << std::endl;}private:void reserve(size_t s) {if (s > capacity) { // 注意判断T* newEle = new T[s];std::copy(elements, elements + size, newEle);delete[] elements;elements = newEle;capacity = s;}}
};int main() {Vector<int> myVector;int line_num;std::cin >> line_num;// 读走回车getchar();for (int i = 0; i < line_num; i++) {// 先读取整行，再从中扣stringstd::string line;std::getline(std::cin, line);std::string command;std::istringstream iss(line);iss >> command;if (command == "push") {// 尽管 std::istringstream 是从字符串构造的，但它支持各种数据类型的提取操作，并不仅限于字符串int num;iss >> num;myVector.push_back(num);}else if (command == "size") {std::cout << myVector.getSize() << std::endl;}else if (command == "get") {size_t s;iss >> s;std::cout << myVector[s] << std::endl;}else if (command == "insert") {size_t index;int ele;iss >> index >> ele;myVector.insert(index, ele);}else if (command == "pop") {myVector.pop_back();}else if (command == "clear") {myVector.clear();}else if (command == "print") {if (myVector.getSize() == 0) { // 别忘了std::cout << "empty" << std::endl;continue;}myVector.printElements();}else if (command == "iterator") {if (myVector.getSize() == 0){std::cout << "empty" << std::endl;continue;}int* begin = myVector.begin();int* end = myVector.end();for (int* it = begin; it != end; it++) {std::cout << *it << " ";}std::cout << std::endl;}else if (command == "foreach") {if (myVector.getSize() == 0){std::cout << "empty" << std::endl;continue;}// 为了使这段代码正常工作，myVector 必须提供一个迭代器接口，即 begin() 和 end() 函数// begin() 和 end() 函数返回的是指向 elements 数组的指针，所以这个范围-based for 循环在 myVector 上的执行实际上是遍历 elements 数组中的每个元素/* 大致相当于for (int* it = myVector.begin(); it != myVector.end(); ++it) {int& element = *it;std::cout << element << " ";}*/for (auto& element : myVector) {std::cout << element << " ";}std::cout << std::endl;}}return 0;
}

本实现版本 和 C++ STL标准库实现版本的区别：
不同的实现复杂度，不同的功能覆盖范围，内存管理和性能，安全性和健壮性

4、相关面试题

1、emplace_back 是 C++ 标准库中 std::vector 和其他容器（如std::deque、std::list等）提供的一个成员函数。它的作用是 直接在容器末尾 构造一个元素，而不是 先构造元素 然后再拷贝或移动到容器中。与 push_back 相比，emplace_back 可以减少不必要的拷贝或移动操作，从而提高性能

#include <vector>
#include <string>
#include <iostream>struct MyStruct {int a;std::string b;MyStruct(int x, std::string y) : a(x), b(y) {std::cout << "Constructed MyStruct\n";}
};int main() {std::vector<MyStruct> vec;// 使用 emplace_backvec.emplace_back(10, "Hello");// 使用 push_backMyStruct obj(20, "World");vec.push_back(obj);return 0;
}

emplace_back(10, "Hello") 直接在 vec 中构造了一个 MyStruct 对象，而 push_back 则需要先创建一个 MyStruct 对象 obj，然后再将其复制或移动到 vec 中

2、使用 std::vector::empty() 方法可以检查 vector 是否没有元素。这比使用 size() 方法（比较 size() == 0）更首选
empty()：empty() 函数的实现通常是直接检查内部的大小标识（如 size 或 begin 和 end 指针的比较），因此它几乎总是 O(1) 的时间复杂度，意味着它可以在常数时间内完成

size()：虽然 size() 也是 O(1) 的时间复杂度，但在某些容器实现中，size() 可能需要 额外计算或检查以确定大小，尤其是 在某些数据结构（如 std::list）的实现中，size() 可能是 O(n) 的复杂度。不过，对于 std::vector，size() 仍然是 O(1) 的

3、可以使用 std::vector::shrink_to_fit 方法来请求移除未使用的容量，减少 vector 的内存使用。这个函数是 C++11 引入的，它会尝试压缩 std::vector 的容量，使其等于其大小。但是，这只是一个请求，并不保证容量会减少

4、如增加或删除元素，尤其是在中间插入或删除元素时，迭代器可能会失效。例如：
如果 vector 进行了重新分配，所有指向元素的迭代器都会失效
如果在 vector 中间插入或删除元素，从该点到末尾的所有迭代器都会失效

std::remove 和 std::remove_if （都不会真正删除元素，只是重新排列元素，剩下的无效元素 仍然存在于容器的末尾）结合 std::vector::erase 方法是 一种常见的模式，用于从 std::vector 中删除符合条件的元素

std::remove / std::remove_if：重新排列容器元素，将符合条件的元素移到末尾，并返回 指向新逻辑末尾的迭代器
vector::erase：使用返回的迭代器 来删除末尾的元素，从而真正移除这些元素 并调整容器的大小

#include <vector>
#include <algorithm>
#include <iostream>int main() {std::vector<int> vec = {1, 2, 3, 4, 5, 2, 6, 2};// 使用 std::remove 移除值为 2 的元素vec.erase(std::remove(vec.begin(), vec.end(), 2), vec.end());// 使用 std::remove_if 移除所有偶数vec.erase(std::remove_if(vec.begin(), vec.end(), [](int n) { return n % 2 == 0; }), vec.end());// 输出结果for (int n : vec) {std::cout << n << " ";  // 输出: 1 3 4 5 6}return 0;
}

5、如果 std::vector 存储的是原始指针，那么仅仅清空 vector 或者让 vector 被销毁，并不会释放指针所指向的内存。因此，需要确保在 vector 被销毁之前，逐个删除所有动态分配的对象

#include <vector>
#include <iostream>class MyClass {
public:MyClass(int value) : value(value) {std::cout << "MyClass constructed with value: " << value << std::endl;}~MyClass() {std::cout << "MyClass destructed with value: " << value << std::endl;}
private:int value;
};int main() {std::vector<MyClass*> vec;// 动态分配对象并存储在 vector 中for (int i = 0; i < 5; ++i) {vec.push_back(new MyClass(i));}// 清空 vector 之前手动删除动态分配的对象for (MyClass* ptr : vec) {delete ptr;}vec.clear(); // 现在可以安全地清空 vectorreturn 0;
}

为了避免手动管理内存，可以考虑使用智能指针（如 std::unique_ptr 或 std::shared_ptr）来替代原始指针。使用智能指针时，std::vector 被销毁时，智能指针会 自动管理和释放其所指向的内存，从而避免内存泄漏

#include <vector>
#include <memory>int main() {std::vector<std::unique_ptr<MyClass>> vec;// 使用 std::unique_ptr 动态分配对象for (int i = 0; i < 5; ++i) {vec.push_back(std::make_unique<MyClass>(i));}// 不需要手动删除，智能指针会自动管理内存vec.clear(); // 或者 vec 被销毁时，内存会自动释放// 使用 clear() 后，vector 的大小 (size()) 将变为 0，但它的容量 (capacity()) 不会改变return 0;
}

6、深拷贝与浅拷贝：如果 需要复制这样的 vector，就需要决定是 进行深拷贝（复制指针指向的对象，两个 vector 是完全独立的，修改或删除一个 vector 中的对象 不会影响另一个 vector）还是浅拷贝（仅复制指针本身，拷贝后的 vector 中的指针与原 vector 中的指针指向同一块内存）

7、当 vector 的元素是指针对 std::vector 元素为指针的情况，需要注意以下几点：
内存管理：如果 std::vector 存储的是原始指针，那么仅仅清空 vector 或者 让 vector 被销毁，并不会释放指针所指向的内存。因此，需要确保在 vector 被销毁之前，逐个删除所有动态分配的对象

所有权和生命周期：需要确保在 vector 所包含的指针被使用期间，指向的对象是有效的。同时，需要清楚地定义谁拥有这些对象的所有权，以及在何时何地进行释放

异常安全：如果在创建和填充 vector 的过程中遇到异常，需要有一个清晰的机制来处理已经分配的内存，以避免内存泄漏

std::vector<MyClass*> vec;
try {for (int i = 0; i < 10; ++i) {vec.push_back(new MyClass(i));}
} catch (...) {// 清理已分配的内存for (MyClass* ptr : vec) {delete ptr;}vec.clear();throw; // 重新抛出异常
}

智能指针：为了简化内存管理，推荐使用智能指针（如 std::unique_ptr 或 std::shared_ptr）作为 vector 的元素类型。这样，当 vector 被清空或销毁时，智能指针会自动释放它们所拥有的资源

避免悬垂指针：当指针指向的对象被删除或移动时，需要确保没有悬垂指针指向无效的内存地址。同样，当 vector 被重新分配时，如果存储的是指向其他元素的指针，这些指针也会失效

深拷贝与浅拷贝：如果需要复制这样的 vector，就需要决定是进行深拷贝（复制指针指向的对象）还是浅拷贝（仅复制指针本身）

https://kamacoder.com/ 手写简单版本STL，内容在此基础上整理补充