/***************************************
 * Description:vector实现
 * Create:2019/11/22
 * Author:zhangfeng
 * History:
 *      2019-11-22 搭建基本框架和实现基本功能
 * *************************************/

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


template<class T, class Alloc=std::allocator<T>>
class mVector {
public:
    typedef T value_type; 
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef value_type* iterator;
    typedef const value_type* const_iterator;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;

public:
    mVector() : _start(0), _finish(0), _end_of_storage(0) {}
    mVector(size_type n);
    ~mVector();

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

    size_type size() const 
        {  return size_type(end() - begin()); }
    
    size_type capacity() const
        {  return size_type(_end_of_storage - begin()); }

    void push_back( const T& value );
    void pop_back();
protected:
    iterator _start; //使用起始空间
    iterator _finish; //使用结束空间
    iterator _end_of_storage; //实际空间尾
    Alloc _alloc;
protected:
    void _insert_aux(iterator _position, const T& _x);
    //对象析构
    void _destroy(iterator _first, iterator _last);
};

template<class T, class Alloc>
mVector<T, Alloc>::mVector(size_type n) : _start(0), _finish(0), _end_of_storage(0)
{
    _start = _alloc.allocate(n);
    _finish = _start;
    _end_of_storage = _start + n;
}

template<class T, class Alloc>
mVector<T, Alloc>::~mVector()
{
    std::cout << "~mVector" << std::endl;
    _destroy(_start, _finish);
    //释放内存
    _alloc.deallocate(_start, _end_of_storage-_start);
    _start = _finish = _end_of_storage = NULL;
}


template<class T, class Alloc>
void mVector<T, Alloc>::_destroy(iterator _first, iterator _last)
{
    for(; _first != _last; _first++){
        _alloc.destroy(_first);
    }
}

template<class T, class Alloc>
void mVector<T, Alloc>::_insert_aux(iterator _position, const T& _x)
{
    if(_finish != _end_of_storage){
        _alloc.construct(_finish, *(_finish - 1));
        ++_finish;
        T _x_copy = _x;
        std::copy_backward(_position, _finish - 2, _finish -1);
        *_position = _x_copy;
    }else{
        const size_type _old_size = size();
        const size_type _len = _old_size != 0 ? 2 * _old_size : 1;
        iterator _new_start = _alloc.allocate(_len);
        iterator _new_finish = _new_start;

        try{
            // 复制来自范围 [_start, _position) 的元素到始于 _new_start 的未初始化内存
            _new_finish = std::uninitialized_copy(_start, _position,  _new_start);
            _alloc.construct(_new_finish, _x);
            ++_new_finish;
            _new_finish = std::uninitialized_copy(_position, _finish, _new_finish);
        }catch(...){
            _destroy(_new_finish, _new_finish);
            _alloc.deallocate(_new_finish, _len);
        }
        _destroy(_start, _finish);
        _alloc.deallocate(_start, _end_of_storage - _start);
        _start = _new_start;
        _finish = _new_finish;
        _end_of_storage = _new_start + _len;
    }
}

template<class T, class Alloc>
void mVector<T, Alloc>::push_back( const T& value )
{
    if(_finish != _end_of_storage) {
        _alloc.construct(_finish, value);
        ++_finish;
    }else{
        _insert_aux(_finish, value);
    }
}

template<class T, class Alloc>
void mVector<T, Alloc>::pop_back()
{
    if(_start != _finish) {
        --_finish;
        _alloc.destroy(_finish);
    }
}

test

#include "m_vector.h"
#include <iostream>
#include <sys/time.h>
#include <time.h>

void test_simple();
void test_memory(int n);
long long getCurTimeUsec();

int main()
{
 
    test_memory(0);
    test_memory(20);
    return 0;
}

long long getCurTimeUsec()
{
    struct timeval tv;
    gettimeofday(&tv,0);
    return tv.tv_usec;
}
void test_simple()
{
    std::cout << "simple test..." << std::endl;
    mVector<int> vec;
    vec.push_back(10);
    vec.push_back(11);
    vec.push_back(12);
    vec.push_back(13);
    vec.pop_back();
    auto it = vec.begin();
    for(; it != vec.end(); it++)
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}

void test_memory(int n)
{
    long long start = getCurTimeUsec();
    std::cout << "memory test..." << std::endl;
    mVector<int> vec(n);
    for (int i = 0; i < 20; ++i) {
        vec.push_back(i);
        std::cout << "push: " << i <<" capacity: " << vec.capacity() << std::endl;
    }

    std::cout << "printf: ";
    for(auto it = vec.begin(); it != vec.end(); it++)
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    long long end = getCurTimeUsec();
    std::cout << "length: " << end - start << std::endl; 
}

out:

zf@eappsvr-0:~/study/stl/mvector> ./a.out 
memory test...
push: 0 capacity: 1
push: 1 capacity: 2
push: 2 capacity: 4
push: 3 capacity: 4
push: 4 capacity: 8
push: 5 capacity: 8
push: 6 capacity: 8
push: 7 capacity: 8
push: 8 capacity: 16
push: 9 capacity: 16
push: 10 capacity: 16
push: 11 capacity: 16
push: 12 capacity: 16
push: 13 capacity: 16
push: 14 capacity: 16
push: 15 capacity: 16
push: 16 capacity: 32
push: 17 capacity: 32
push: 18 capacity: 32
push: 19 capacity: 32
printf: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 
length: 329
~mVector
memory test...
push: 0 capacity: 20
push: 1 capacity: 20
push: 2 capacity: 20
push: 3 capacity: 20
push: 4 capacity: 20
push: 5 capacity: 20
push: 6 capacity: 20
push: 7 capacity: 20
push: 8 capacity: 20
push: 9 capacity: 20
push: 10 capacity: 20
push: 11 capacity: 20
push: 12 capacity: 20
push: 13 capacity: 20
push: 14 capacity: 20
push: 15 capacity: 20
push: 16 capacity: 20
push: 17 capacity: 20
push: 18 capacity: 20
push: 19 capacity: 20
printf: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 
length: 89
~mVector

测试下来vector提前分配合适的内存，效率会高很多。