c++的vector源码实现

我可以回答这个问题。C++的vector是一个动态数组，它可以根据需要改变大小。它的实现方式是使用一个指向数组的指针，同时记录当前数组的大小和容量。当需要添加元素时，如果当前容量不足，则会重新分配更大的内存空间，并将原来的元素复制到新的内存空间中。如果需要删除元素，它会将该元素后面的所有元素向前移动一个位置，并缩小当前的大小。这种实现方式保证了vector的高效性和灵活性。

相关问题

c++vector源码

C++中的vector是一个动态数组，它的源码实现在标准头文件<vector>中。下面是vector的一些关键实现细节：

// vector的定义
template <typename _Tp, typename _Alloc = std::allocator<_Tp>>
class vector {
public:
    // 构造函数
    vector() noexcept(noexcept(_Alloc())) : vector(_Alloc()) {}
    explicit vector(const _Alloc& __a) noexcept;
    explicit vector(size_type __n);
    vector(size_type __n, const value_type& __value,
           const _Alloc& __a = _Alloc());
    template <typename _InputIterator>
    vector(_InputIterator __first, _InputIterator __last,
           const _Alloc& __a = _Alloc());
    vector(const vector& __x);
    vector(vector&& __x) noexcept;
    vector(initializer_list<value_type> __l, const _Alloc& __a = _Alloc());
    // 析构函数
    ~vector();
    // 元素访问
    reference operator[](size_type __n) { return *(this->_M_impl._M_start + __n); }
    const_reference operator[](size_type __n) const { return *(this->_M_impl._M_start + __n); }
    reference at(size_type __n);
    const_reference at(size_type __n) const;
    reference front() { return *begin(); }
    const_reference front() const { return *begin(); }
    reference back() { return *(end() - 1); }
    const_reference back() const { return *(end() - 1); }
    pointer data() noexcept { return pointer_traits<pointer>::pointer_to(this->_M_impl._M_start); }
    const_pointer data() const noexcept { return pointer_traits<const_pointer>::pointer_to(this->_M_impl._M_start); }
    // 迭代器
    iterator begin() noexcept { return iterator(this->_M_impl._M_start); }
    const_iterator begin() const noexcept { return const_iterator(this->_M_impl._M_start); }
    iterator end() noexcept { return iterator(this->_M_impl._M_finish); }
    const_iterator end() const noexcept { return const_iterator(this->_M_impl._M_finish); }
    reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
    const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
    reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
    const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }
    const_iterator cbegin() const noexcept { return const_iterator(this->_M_impl._M_start); }
    const_iterator cend() const noexcept { return const_iterator(this->_M_impl._M_finish); }
    const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(cend()); }
    const_reverse_iterator crend() const noexcept { return const_reverse_iterator(cbegin()); }
    // 容量
    bool empty() const noexcept { return begin() == end(); }
    size_type size() const noexcept { return static_cast<size_type>(end() - begin()); }
    size_type max_size() const noexcept;
    void reserve(size_type __n);
    size_type capacity() const noexcept { return static_cast<size_type>(this->_M_impl._M_end_of_storage - this->_M_impl._M_start); }
    void shrink_to_fit() noexcept;
    // 修改器
    void clear() noexcept { _M_erase_at_end(this->_M_impl._M_start); }
    iterator insert(const_iterator __position, const value_type& __x);
    iterator insert(const_iterator __position, value_type&& __x);
    iterator insert(const_iterator __position, size_type __n, const value_type& __x);
    template <typename _InputIterator>
    iterator insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
    iterator insert(const_iterator __position, initializer_list<value_type> __l) { return insert(__position, __l.begin(), __l.end()); }
    template <typename... _Args>
    iterator emplace(const_iterator __position, _Args&&... __args);
    iterator erase(const_iterator __position);
    iterator erase(const_iterator __first, const_iterator __last);
    void push_back(const value_type& __x);
    void push_back(value_type&& __x);
    template <typename... _Args>
    reference emplace_back(_Args&&... __args);
    void pop_back();
    void resize(size_type __new_size) { resize(__new_size, value_type()); }
    void resize(size_type __new_size, const value_type& __x);
    void swap(vector& __x) noexcept(_Alloc_traits::_S_nothrow_swap());
};

C++ vector源码

以下是一个简单的 C 语言动态数组实现，类似于 C++ 的 std::vector：

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *arr;  // 存储数据的指针
    int size;  // 当前容量
    int count; // 当前元素个数
} Vector;

// 初始化动态数组
void initVector(Vector *v) {
    v->arr = (int *)malloc(sizeof(int) * 10);
    v->size = 10;
    v->count = 0;
}

// 添加元素
void pushBack(Vector *v, int val) {
    if (v->count == v->size) {
        v->size *= 2;
        v->arr = (int *)realloc(v->arr, sizeof(int) * v->size);
    }
    v->arr[v->count++] = val;
}

// 删除元素
void popBack(Vector *v) {
    if (v->count > 0) {
        v->count--;
    }
}

// 获取元素个数
int size(Vector *v) {
    return v->count;
}

// 获取指定下标的元素
int at(Vector *v, int index) {
    if (index >= 0 && index < v->count) {
        return v->arr[index];
    }
    return -1;
}

// 释放动态数组内存
void freeVector(Vector *v) {
    free(v->arr);
    v->arr = NULL;
    v->size = 0;
    v->count = 0;
}

int main() {
    Vector v;
    initVector(&v);

    pushBack(&v, 1);
    pushBack(&v, 2);
    pushBack(&v, 3);
    pushBack(&v, 4);
    pushBack(&v, 5);

    printf("size: %d\n", size(&v));
    printf("at(0): %d\n", at(&v, 0));
    printf("at(2): %d\n", at(&v, 2));

    popBack(&v);
    popBack(&v);

    printf("size: %d\n", size(&v));
    printf("at(2): %d\n", at(&v, 2));

    freeVector(&v);

    return 0;
}

这个动态数组的实现在初始化时会分配一块大小为 10 的内存，当添加元素时，如果当前元素个数已经等于容量大小，则将容量大小扩大一倍，并重新分配内存。删除元素时只需将元素个数减一即可。

这只是一个简单的实现，实际上还有许多细节需要考虑，例如内存分配失败的情况、插入元素时需要移动后续元素的问题等等。