面试题：C++ vector容量收缩机制与内存管理的深度剖析

C++ STL中vector实现容量收缩的底层机制

内存分配策略
- vector采用动态数组的方式存储元素。当元素数量超过当前容量（capacity）时，会重新分配内存。通常新的容量是当前容量的两倍（不同实现可能有差异）。
- 对于容量收缩，vector并不会在每次删除元素后就立即收缩内存。这是为了避免频繁的内存分配和释放带来的性能开销。vector提供了shrink_to_fit成员函数来主动请求容量收缩。当调用shrink_to_fit时，vector会尝试将容量减少到与当前元素数量（size）相同。如果内存分配器支持，会重新分配一块大小刚好能容纳当前元素数量的内存，并将原数据拷贝到新内存，然后释放原内存。
迭代器失效情况
- 当vector进行容量收缩（例如调用shrink_to_fit且成功重新分配内存）时，所有指向vector元素的迭代器、指针和引用都会失效。这是因为内存位置发生了改变。
- 例如：
```
std::vector<int> v = {1, 2, 3};
auto it = v.begin();
v.shrink_to_fit();
// 此时it失效，不能再使用it指向v中的元素
```
与其他STL容器在内存管理上的差异
- list：list是双向链表，每个节点单独分配内存。它的内存管理是以节点为单位，不存在容量的概念，也就没有容量收缩的机制。插入和删除操作只影响相邻节点的指针，不会使其他迭代器失效（除了指向被删除节点的迭代器）。
- deque：deque（双端队列）采用分段连续的内存存储元素。它的内存管理相对复杂，由多个缓冲区组成。deque的容量是动态的，但它的迭代器失效规则与vector不同。在deque两端插入或删除元素通常不会使其他迭代器失效，只有在中间插入或删除元素时，可能会使部分迭代器失效。而且deque没有类似vector的shrink_to_fit操作，因为其内存管理方式与vector基于连续内存块的方式不同。

设计自定义容器借鉴vector容量收缩思想的关键问题和实现步骤

关键问题
- 内存管理：需要设计一种动态内存分配策略，既能满足元素添加时的空间需求，又能在元素减少时合理收缩内存。可以选择类似vector的以倍数增长的策略来分配内存，同时要考虑内存分配和释放的效率，例如使用内存池技术来减少系统调用的开销。
- 迭代器管理：要定义迭代器，并明确在容量收缩等操作下迭代器的失效规则。迭代器需要能够正确地遍历容器中的元素，并且在容器发生变化（如容量收缩）时，要保证迭代器的一致性和安全性。
- 数据迁移：当进行容量收缩重新分配内存时，需要将原数据迁移到新的内存位置。要确保数据迁移过程中数据的完整性和正确性，并且尽量减少数据拷贝的开销，例如可以使用移动语义。
- 性能权衡：容量收缩虽然可以节省内存，但频繁的容量收缩会带来性能开销。需要在内存使用和性能之间找到平衡，例如设置合适的收缩阈值，只有当元素数量减少到一定程度时才进行容量收缩。

实现步骤

定义数据结构：
- 定义一个类来表示自定义容器，例如MyVector。
- 包含一个指针成员变量来指向动态分配的内存块，以及表示当前元素数量（size）和容量（capacity）的成员变量。

template<typename T>
class MyVector {
private:
    T* data;
    size_t size_;
    size_t capacity_;
public:
    // 构造函数、析构函数等
};

内存分配与释放：

在构造函数中分配初始内存，例如：

template<typename T>
MyVector<T>::MyVector() : size_(0), capacity_(8) {
    data = new T[capacity_];
}

在析构函数中释放内存：

template<typename T>
MyVector<T>::~MyVector() {
    delete[] data;
}

元素添加与容量增长：

实现push_back等添加元素的函数，当元素数量超过容量时，重新分配内存并拷贝数据。

template<typename T>
void MyVector<T>::push_back(const T& value) {
    if (size_ == capacity_) {
        capacity_ *= 2;
        T* newData = new T[capacity_];
        for (size_t i = 0; i < size_; ++i) {
            newData[i] = data[i];
        }
        delete[] data;
        data = newData;
    }
    data[size_++] = value;
}

容量收缩：

实现类似shrink_to_fit的函数，当元素数量减少且满足一定条件时，重新分配内存以收缩容量。

template<typename T>
void MyVector<T>::shrink_to_fit() {
    if (size_ < capacity_ / 4 && capacity_ > 8) {
        capacity_ = size_;
        T* newData = new T[capacity_];
        for (size_t i = 0; i < size_; ++i) {
            newData[i] = data[i];
        }
        delete[] data;
        data = newData;
    }
}

迭代器实现：

定义迭代器类，实现++、--、*等操作符，并且在容器容量收缩等操作时更新迭代器的状态以确保其有效性。

template<typename T>
class MyVectorIterator {
private:
    T* ptr;
public:
    MyVectorIterator(T* p) : ptr(p) {}
    T& operator*() { return *ptr; }
    MyVectorIterator& operator++() { ++ptr; return *this; }
    bool operator!=(const MyVectorIterator& other) { return ptr != other.ptr; }
};
template<typename T>
MyVectorIterator<T> MyVector<T>::begin() {
    return MyVectorIterator<T>(data);
}
template<typename T>
MyVectorIterator<T> MyVector<T>::end() {
    return MyVectorIterator<T>(data + size_);
}

星途面试题库

面试题：C++ vector容量收缩机制与内存管理的深度剖析

知识考点

面试题答案

C++ STL中vector实现容量收缩的底层机制

设计自定义容器借鉴vector容量收缩思想的关键问题和实现步骤