C++ vector 全面解析：从基础用法到深度剖析

1. 通过成员变量名称猜测作用。
2. 通过构造函数和插入接口分析成员用途。
3. 先构建整体框架。

核心代码

namespace renshen {
template<class T>
class vector {
public:
    typedef T* iterator;
    typedef const T* const_iterator;

    iterator begin() { return _start; }
    iterator end() { return _finish; }
    const_iterator begin() const { return _start; }
    const_iterator end() const { return _finish; }

    vector(size_t n, const T& val = T()) 
        : _start(nullptr), _finish(nullptr), _endofstorage(nullptr) {
        resize(n, val);
    }

    template<class InputIterator>
    vector(InputIterator first, InputIterator last)
        : _start(nullptr), _finish(nullptr), _endofstorage(nullptr) {
        while(first != last) {
            push_back(*first);
            ++first;
        }
    }

    vector() : _start(nullptr), _finish(nullptr), _endofstorage(nullptr) {}

    vector(const vector<T>& v) 
        : _start(nullptr), _finish(nullptr), _endofstorage(nullptr) {
        _start = new T[v.capacity()];
        for(size_t i = 0; i < v.size(); i++) {
            _start[i] = v._start[i];
        }
        _finish = _start + v.size();
        _endofstorage = _start + v.capacity();
    }

    void swap(vector<T>& v) {
        std::swap(_start, v._start);
        std::swap(_finish, v._finish);
        std::swap(_endofstorage, v._endofstorage);
    }

    vector<T>& operator=(vector<T> v) {
        swap(v);
        return *this;
    }

    ~vector() {
        if(_start) {
            delete[] _start;
            _start = _finish = _endofstorage = nullptr;
        }
    }

    void reserve(size_t n) {
        if(n > capacity()) {
            size_t sz = size();
            T* tmp = new T[n];
            if(_start) {
                for(size_t i = 0; i < sz; i++) {
                    tmp[i] = _start[i];
                }
                delete[] _start;
            }
            _start = tmp;
            _finish = _start + sz;
            _endofstorage = _start + n;
        }
    }

    void resize(size_t n, const T& val = T()) {
        if(n < size()) {
            _finish = _start + n;
        } else {
            reserve(n);
            while(_finish != _start + n) {
                *_finish = val;
                ++_finish;
            }
        }
    }

    void push_back(const T& x) {
        insert(end(), x);
    }

    void pop_back() {
        erase(--end());
    }

    size_t capacity() const { return _endofstorage - _start; }
    size_t size() const { return _finish - _start; }

    T& operator[](size_t pos) {
        assert(pos < size());
        return _start[pos];
    }

    const T& operator[](size_t pos) const {
        assert(pos < size());
        return _start[pos];
    }

    iterator insert(iterator pos, const T& x) {
        assert(pos >= _start && pos <= _finish);
        if(_finish == _endofstorage) {
            size_t len = pos - _start;
            size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
            reserve(newcapacity);
            pos = _start + len;
        }
        iterator end = _finish - 1;
        while(end >= pos) {
            *(end + 1) = *end;
            --end;
        }
        *pos = x;
        ++_finish;
        return pos;
    }

    iterator erase(iterator pos) {
        assert(pos >= _start && pos < _finish);
        iterator it = pos + 1;
        while(it != _finish) {
            *(it - 1) = *it;
            ++it;
        }
        --_finish;
        return pos;
    }

private:
    iterator _start;
    iterator _finish; // 最后一个元素的下一个位置
    iterator _endofstorage; // 内存的末尾的下一个位置
};

void print(const vector<int>& v) {
    for(auto e : v) {
        cout << e << " ";
    }
    cout << endl;
}
}

重载与类型转换

• vector v(10, 1);：编译器调用 size_t 构造函数，因为第二个参数 1 匹配 val 类型，且 10 默认为 int 但会被隐式转换为 size_t。
• vector v1(10, "1111");：调用 size_t 构造函数。

注意事项

1. 迭代器失效：insert 后若发生扩容，原迭代器可能失效成为野指针。erase 和 insert 的返回值是指向新位置的迭代器，应优先使用返回值。
2. 通用性：代码应尽量兼容不同编译器环境，避免依赖特定编译器特性。
3. 拷贝语义：reverse 和构造函数中慎用 memcpy，遇到非 POD 类型（如 string）会导致浅拷贝错误，应使用循环赋值。
4. 默认值：int j = int(); 等价于 int j = 0;。

典型应用示例

只出现一次的数字

利用异或运算性质（相同为 0，不同为 1，符合分配律），对数组所有元素异或，结果即为只出现一次的数字。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int e = 0;
        for(int i = 0; i < nums.size(); i++) {
            e = e ^ nums[i];
        }
        return e;
    }
};

边界检查机制

在 Debug 模式下，std::vector::at 总是做边界检查，而 operator[] 不做边界检查。两者行为差异需根据需求选择。

容量与大小变化

• 容量（capacity）不会变小，resize 减小大小时仅修改 size 指针。
• reserve 增大容量时不改变 size。

int main() {
    int ar[] = {1,2,3,4,5,6,7,8,9,10};
    int n = sizeof(ar)/sizeof(int);
    vector<int> v(ar, ar+n);
    cout << v.size() << ":" << v.capacity() << endl; // 10:10
    v.reserve(100);
    v.resize(20);
    cout << v.size() << ":" << v.capacity() << endl; // 20:100
    v.reserve(50);
    v.resize(5);
    cout << v.size() << ":" << v.capacity() << endl; // 5:100
    return 0;
}

电话号码的字母组合

使用 DFS 回溯法，注意 vector 为空时直接返回空 vector 而非空字符串，传递 vector 引用避免重复拷贝。

class Solution {
public:
    string qq[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    void dfs(vector<string>& f, int level, string p, string digits) {
        if(level == digits.size()) {
            f.push_back(p);
            return;
        }
        for(int i = 0; i < qq[digits[level]-'0'].size(); i++) {
            dfs(f, level+1, p+qq[digits[level]-'0'][i], digits);
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string> a;
        if(digits == "") return a;
        dfs(a, 0, "", digits);
        return a;
    }
};

数组中出现次数超过一半的数字

排序后取中间元素即可。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        sort(numbers.begin(), numbers.end());
        return numbers[numbers.size()/2];
    }
};

只出现一次的数 II

统计二进制位出现次数，对 3 取模，剩余即为目标数字的二进制位。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for(int i = 0; i < 32; ++i) {
            int total = 0;
            for(int e : nums) {
                total += ((e >> i) & 1);
            }
            if(total % 3) {
                ret |= (1 << i);
            }
        }
        return ret;
    }
};

只出现一次的数 III

全部异或得到 sum，找出最低位 1，将数组分为两组分别异或。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        long long int sum = 0;
        for(auto e : nums) {
            sum = sum ^ e;
        }
        long long int lowbit = sum & (-sum);
        int num1 = 0, num2 = 0;
        for(auto e : nums) {
            if((lowbit & e) == 0) num1 ^= e;
            else num2 ^= e;
        }
        return {num1, num2};
    }
};