1. 概述

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

线性
- 线性表就是数据排成像一条线一样的结构
- 每个线性表上的数据最多只有前和后两个方向
连续的内存空间和相同类型的数据

2. 高效的随机访问

计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：

1	a[i]_address = base_address + i * data_type_size

其中 data_type_size 表示数组中每个元素的大小。我们举的这个例子里，数组中存储的是 int 类型数据，所以 data_type_size 就为 4 个字节。这个公式非常简单，我就不多做解释了。

数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。

3. 低效的“插入”和“删除”

假设数组的长度为 n，现在，如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来，给新来的数据，我们需要将第 k～n 这部分的元素都顺序地往后挪一位。删除操作跟插入数据类似，如果我们要删除第 k 个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。

4. 数组编码练习

例：实现STL库中vector。

#ifndef DATA_STRUCTURE_STL_VECTOR_H
#define DATA_STRUCTURE_STL_VECTOR_H

#include <memory>
#include <iostream>
#include <algorithm>

template <class T, class Alloc=std::allocator<T>> class STDVector {

public:
    typedef T						value_type;
    typedef value_type*				iterator;
    typedef const value_type*		const_iterator;
    typedef value_type&				reference;
    typedef value_type*				pointer;
    typedef	size_t					size_type;
    typedef ptrdiff_t				difference_type;

protected:
    std::allocator<value_type> _alloc;
    iterator _start;
    iterator _end;
    iterator _end_of_storage;

public:
    STDVector() :_start(0), _end(0), _end_of_storage(0){}
    STDVector(size_type n, const T& value);
    STDVector(size_type n);
    STDVector(iterator first, iterator last);
    STDVector(const STDVector& v);
    STDVector& operator=(const STDVector& rhs);
    ~STDVector() { _destroy(); }

    iterator begin() { return _start; }
    iterator end()	 { return _end; }
    const_iterator cbegin() const { return _start; }
    const_iterator cend() const { return _end; }

    size_type size()  { return size_type(end() - begin()); }
    size_type capacity() { return size_type(_end_of_storage - begin()); }
    bool empty() { return begin() == end(); }
    void swap(STDVector &other);

    reference front() { return *begin(); }
    reference back() { return *(end() - 1); }
    reference operator[] (size_type n) { return *(begin() + n); }

    void insert_aux(iterator positon, const T& x);
    void push_back(const T& value);
    void pop_back();
    void insert(iterator position, size_type n, const T& x);

    iterator erase(iterator position);
    iterator erase(iterator first, iterator last);
    void clear() { erase(begin(), end()); }

private:
    void _destroy();
    void TestSTDVector();

};

template <class T, class Alloc = std::allocator<T>>
STDVector<T, Alloc>::STDVector(size_type n, const T& value) {
    _start = _alloc.allocate(n);
    std::uninitialized_fill(_start, _start + n, value);
    _end = _end_of_storage = _start + n;
}

template <class T, class Alloc = std::allocator<T>>
STDVector<T, Alloc>::STDVector(size_type n) {
    _start = _alloc.allocate(n);
    std::uninitialized_fill(_start, _start + n, 0);
    _end = _end_of_storage = _start + n;
}

template <class T, class Alloc = std::allocator<T>>
STDVector<T, Alloc>::STDVector(iterator first, iterator last) {
    _start = _alloc.allocate(last - first);
    _end = _end_of_storage = std::uninitialized_copy(first, last, _start);
}

template <class T, class Alloc = std::allocator<T>>
STDVector<T, Alloc>::STDVector(const STDVector& v) {
    size_type n = v.cend() - v.cbegin();
    _start = _alloc.allocate(n);
    _end = _end_of_storage = std::uninitialized_copy(v.cbegin(), v.cend(), _start);
}

template <class T, class Alloc = std::allocator<T>>
void STDVector<T, Alloc>::swap(STDVector &other) {
    std::swap(_start, other._start);
    std::swap(_end, other._end);
    std::swap(_end_of_storage, other._end_of_storage);
}

template <class T, class Alloc = std::allocator<T>>
STDVector<T, Alloc> &STDVector<T, Alloc>::operator=(const STDVector &rhs) {
    if (this == &rhs)
        return *this;
    size_type n = rhs.cend() - rhs.cbegin();
    _start = _alloc.allocate(n);
    _end = _end_of_storage = std::uninitialized_copy(rhs.cbegin(), rhs.cend(), _start);
}

template <class T, class Alloc = std::allocator<T>>
void STDVector<T, Alloc>::insert(iterator position, size_type n, const T& x) {
    if (n >= 0) {
        if (_end_of_storage - _end >= n) {
            T x_copy = x;
            const size_type elem_after = _end - position;
            iterator old_end = _end;
            if (elem_after > n) {
                std::uninitialized_copy(_end - n, _end, _end);
                _end = _end + n;
                std::copy_backward(position, old_end - n, old_end);
                std::fill(position, position + n, x_copy);
            } else {
                std::uninitialized_fill_n(_end, n - elem_after, x_copy);
                _end += n - elem_after;
                std::uninitialized_copy(position, old_end, _end);
                _end += elem_after;
                std::fill(position, old_end, x_copy);
            }
        } else {
            const size_type old_size = size();
            const size_type len = old_size + std::max(old_size, n);
            iterator new_start = _alloc.allocate(len);
            iterator new_end = new_start;
            new_end = std::uninitialized_copy(_start, position , new_start);
            new_end = std::uninitialized_fill_n(new_end, n, x);
            new_end = std::uninitialized_copy(position, _end, new_end);
            _destroy();
            _start = new_start;
            _end = new_end;
            _end_of_storage = new_start + len;
        }
    }
}

template <class T, class Alloc = std::allocator<T>>
void STDVector<T, Alloc>::insert_aux(iterator positon, const T& x) {
    if (_end != _end_of_storage) {

    } else {
        const size_type old_size = size();
        const size_type len = old_size ? 2 * old_size : 1;
        iterator new_start = _alloc.allocate(len);
        iterator new_end = new_start;
        new_end = std::uninitialized_copy(_start, positon, new_start);
        _alloc.construct(new_end, x);
        ++ new_end;
        new_end = std::uninitialized_copy(positon, _end, new_end);
        _destroy();
        _start = new_start;
        _end = new_end;
        _end_of_storage = new_start + len;
    }
}

template <class T, class Alloc = std::allocator<T>>
void STDVector<T, Alloc>::push_back(const T& value) {
    if (_end != _end_of_storage) {
        _alloc.construct(_end, value);
        ++ _end;
    } else {
        insert_aux(end(), value);
    }
}

template <class T, class Alloc = std::allocator<T>>
void STDVector<T, Alloc>::pop_back() {
    --_end;
    _alloc.destroy(_end);
}

template <class T, class Alloc = std::allocator<T>>
typename STDVector<T, Alloc>::iterator STDVector<T, Alloc>::erase(iterator position) {
    if (position + 1 != end())
        std::copy(position + 1, end(), position);
    --_end;
    _alloc.destroy(_end);
    return position;
}

template <class T, class Alloc = std::allocator<T>>
typename STDVector<T, Alloc>::iterator STDVector<T, Alloc>::erase(iterator first, iterator last) {
    difference_type left = _end - last;
    std::copy(last, _end, first);
    iterator it(first + left);
    while (_end != it)
        _alloc.destroy(--_end);
    return first;
}

template <class T, class Alloc = std::allocator<T>>
void STDVector<T, Alloc>::_destroy() {
    if (_start) {
        iterator it(_end);
        while (it != _start)
            _alloc.destroy(--it);
    }
    _alloc.deallocate(_start, _end_of_storage - _start);
    _start= _end_of_storage = _end = NULL;
}

#endif //DATA_STRUCTURE_STL_VECTOR_H

以上代码参考：https://github.com/yqtaowhu/DataStructureAndAlgorithm/tree/master/DataStructure/vector

5. 参考

以上内容为《数据结构与算法之美》学习笔记
STL的vector实现