C++ 学习系列 -- std::vector (未完待续)

一  std::vector 是什么？

   vector 是c++ 中一种序列式容器，与前面说的 array 类似，其内存分配是连续的，但是与 array 不同的地方在于，vector 在运行时是可以动态扩容的，此外 vector 提供了许多方便的操作，比如：插入、删除、查找、排序等。

std::vector - cppreference.com

二  std::vector 的特性与常见面试问题有哪些？

1  特性

1.1  vector 底层是基于分配连续空间的数组，因此 vector的访问既可以通过 容器的迭代器的方式，也可以通过数组的下标方式来访问元素

1.2 vector 可以在运行期间根据需要，进行动态的扩容，当已分配的空间被用满时，会再重新分配一块通常是原来空间两倍的内存，接下来依次将原来内存中的元素依次拷贝过来

1.3 基于底层的原理 ，其相关操作的时间复杂度如下：

       1）访问元素的时间复杂度 与数组相同，是 O(1) ；

       2） 在 vector末尾插入元素或者删除元素 O(1)

       3)   在 vector 中间某个位置插入或者删除一个元素，O(n)

2 常见面试问题

1. vector 的扩容机制 ？

  1.1  扩容倍数一般为 2 倍或者 1.5 倍

// main.cpp
 
#include
#include
 
int main()
{
 
   std::vector<int>  vec2;
    for(int i=0; i<20; i++)
    {
        std::cout << "size: " << vec2.size() << ", capaticy: " << vec2.capacity() << std::endl;
        vec2.push_back(i);
    }
 
   return 0;
}
 
 

其实际存储的元素个数，与开辟空间可以存放的元素个数如下：

从输出结果可以看出，每当存放的元素将分配的空间耗尽以后，vector 就会再次申请两倍于当前内存大小的空间来使用

   1.2  扩容的具体过程

        当存放元素个数将 vector 分配的内存空间耗尽时，当再放入新元素时，会触发如下过程

•  重新分配新的连续内存空间，大小一般是原来的 2 倍
•  将原来内存空间的元素依次拷贝到新空间中, 此过程会触发拷贝构造函数
•  调用存放在原内存空间中各元素的析构函数
•  释放掉原空间的内存 

  我们可以通过如下代码的结果看到这个过程

#include
#include
 
class AAA
{
public:
    AAA(int i):index(i){
        std::cout << "constructor AAA index: " << index << std::endl;
    }
    ~AAA(){
        std::cout << "destructor AAA index: " << index << std::endl;
    }
    AAA(AAA& a):index(a.index){
        std::cout << "copy constructor AAA index: " << index << std::endl;
    }
    AAA(const AAA& a):index(a.index){
        std::cout << "copy constructor const AAA index: " << index << std::endl;
    }
    AAA(AAA&& a):index(a.index){
        std::cout << "move copy constructor AAA index: " << index << std::endl;
        a.index = 0;
    }
    AAA& operator=(AAA& a){
        this->index = a.index;
        std::cout << "equals AAA index: " << index << std::endl;
        return *this;
    }
 
public:
    int index;
};
 
int  main()
{
    std::vector vec2;
    for(int i=0; i<7; i++)
    {
        std::cout << "size: " << vec2.size() << ", capaticy: " << vec2.capacity() << std::endl;
        vec2.emplace_back(i);
    }
    return 0;
}

输出：

2.如何避免扩容导致的效率低下？

    2.1  可以在使用 vector 之前，预估好元素的个数，在使用 vector 之前，将内存空间分配好，而不是在一边插入一边分配新空间与拷贝旧空间的元素

   2.2  若是无法预估，可以在自定义类中实现高效的移动构造函数，然后禁用拷贝构造函数，这样vector 在扩容完毕后的拷贝元素阶段，会自动调用移动构造函数，具体如下：

（c++ 中声明移动构造函数后，会自动禁用拷贝构造函数）

#include
#include
 
class AAA
{
public:
    AAA(int i):index(i){
        std::cout << "constructor AAA index: " << index << std::endl;
    }
    ~AAA(){
        std::cout << "destructor AAA index: " << index << std::endl;
    }
    AAA(AAA&& a):index(a.index){
        std::cout << "move copy constructor AAA index: " << index << std::endl;
        a.index = 0;
    }
    AAA& operator=(AAA& a){
        this->index = a.index;
        std::cout << "equals AAA index: " << index << std::endl;
        return *this;
    }
 
public:
    int index;
};
 
int  main()
{
    std::vector vec2;
    for(int i=0; i<7; i++)
    {
        std::cout << "size: " << vec2.size() << ", capaticy: " << vec2.capacity() << std::endl;
        vec2.emplace_back(i);
    }
    return 0;
}

输出： 

3.为什么选择以1.5倍或者2倍方式进行扩容？而不是3倍4倍扩容？

    面试题：C++vector的动态扩容，为何是1.5倍或者是2倍_vector扩容_森明帮大于黑虎帮的博客-CSDN博客

4.vs为什么选择1.5倍，linux为什么选择2倍？

面试题：C++vector的动态扩容，为何是1.5倍或者是2倍_vector扩容_森明帮大于黑虎帮的博客-CSDN博客

三 std::vector 的使用

  1. vector 常见接口与操作

       std::vector - cppreference.com

     1.1  容器构造

       使用例子：

          

#include
#include
 
void printVector(std::vector& vec)
{
    for(T& v:vec)
    {
        std::cout << v << " ";
    }
    std::cout << "" << std::endl;
}
 
void testVector()
{
    std::cout << "testVector --" << std::endl;
 
    // 1. 构造空 vector
    std::vector<int>  vec1;
    for(int i=1;i<7;i++)
    {
        vec1.push_back(i);
    }
    std::cout << "------------ 1" << std::endl;
    printVector(vec1);
 
    // 2. 构造 count 个 value 到 vector 中
    std::vector<int> vec2(6, 88);
    std::cout << "------------ 2" << std::endl;
    printVector(vec2);
 
    // 3. 利用迭代器构造 vector
    std::vector<int> vec3(vec2.begin(), vec2.end());
    std::cout << "------------ 3" << std::endl;
    printVector(vec3);
 
 
    // 4. 拷贝构造函数
    std::vector<int> vec4(vec1);
    std::cout << "------------ 4" << std::endl;
    printVector(vec4);
 
    // 5. 移动构造函数
    std::vector<int> vec5(std::move(vec1));
    std::cout << "------------ 5" << std::endl;
    printVector(vec5);
}
 
int main(int argc, char *argv[])
{
   testVector();
 
   return 0;
}

输出：

  

     1.2  容器访问

      示例代码：

#include
#include
 
void testVector2()
{
    std::cout << "testVector --" << std::endl;
 
    // 构造 vector
    std::vector<int>  vec1;
    for(int i=1;i<7;i++)
    {
        vec1.push_back(i);
    }
    std::cout << "------------ 1" << std::endl;
 
    // 1. at
    int pos = 3;
    std::cout << " pos = 3, val = " << vec1.at(pos)<< std::endl;
    // 可以修改数据
    int& tmp1 = vec1.at(pos);
    tmp1 = 88;
    std::cout << " pos = 3, val = " << vec1.at(pos)<< std::endl;
 
 
    std::cout << "------------ 2" << std::endl;
    // 2. operator[]
    std::cout << " pos = 3, val = " << vec1[pos]<< std::endl;
 
 
    std::cout << "------------ 3" << std::endl;
    // 3. front
    std::cout << " front, val = " << vec1.front() << std::endl;
 
    std::cout << "------------ 4" << std::endl;
    // 4. back
    std::cout << " back, val = " << vec1.back()<< std::endl;
 
    std::cout << "------------ 5" << std::endl;
    // 5. data
 
    int*  tmp5 = vec1.data();
 
    for(int i=0; i<6;i++)
    {
        std::cout << "i = " << i <<", val = " <<*(tmp5 + i) << std::endl;
    }
}
 
int main()
{
    testVector2();
 
    return 0;
}

输出：

  

    1.3  容器空间

  示例如下

#include
#include
 
void testVector3()
{
    std::cout << "testVector --" << std::endl;
 
    std::vector<int> vec1;
    std::cout << " empty: " << vec1.empty() << ", size: " << vec1.size() << std::endl;
 
    for(int i=0; i<5; i++)
    {
        std::cout << "size: " << vec1.size() << ", capaticy: " << vec1.capacity() << std::endl;
        vec1.emplace_back(i+1);
    }
    std::cout << " empty: " << vec1.empty() << ", size: " << vec1.size() << std::endl;
 
    vec1.reserve(8);
    std::cout << "size: " << vec1.size() << ", capaticy: " << vec1.capacity() << std::endl;
}
 
int main()
{
    testVector3();
    return 0;
}

输出:

1.4  容器修改

      

      示例如下：

         

#include
#include
 
 
void testVector4()
{
    std::cout << "testVector --" << std::endl;
    std::vector<int> vec1;
    for(int i=0; i<5; i++)
    {
        vec1.emplace_back(i+1);
    }
    printVector(vec1);
    // 1. insert
    std::cout << "------------ 1" << std::endl;
    auto iter = std::find(vec1.begin(), vec1.end(), 3);
    vec1.insert(iter,666);
    printVector(vec1);
 
    // 2. emplace
    std::cout << "------------ 2" << std::endl;
    vec1.emplace(iter,888);
 
    printVector(vec1);
 
    // 3. push_back
    std::cout << "------------ 3" << std::endl;
    vec1.push_back(77);
    printVector(vec1);
 
    // 4. emplace_back
    std::cout << "------------ 4" << std::endl;
    vec1.emplace_back(778);
 
    printVector(vec1);
 
    // 5. pop_back
    std::cout << "------------ 5" << std::endl;
    vec1.pop_back();
    printVector(vec1);
 
    // 6. clear
    std::cout << "------------ 6" << std::endl;
    vec1.clear();
    std::cout << "empyt: " << vec1.empty() << std::endl;
}
 
int main()
{
    testVector4();
    return 0;
}

 输出：

 

四  std::vector 的简单实现

  接下来我们实现自己简单的  vector 

// my_iterator.h
struct input_iterator_tag {};
 
struct output_iterator_tag {};
 
struct forward_iterator_tag:public input_iterator_tag {};
 
struct bidirectional_iterator_tag: public forward_iterator_tag {};
 
struct random_access_iterator_tag: public bidirectional_iterator_tag {};
 
template<typename _Category, typename _Tp, typename Distance = long long,
         typename Pointer = _Tp*, typename _Refrence = _Tp&>
struct _IterorBase
{
    typedef _Category  iterator_category;
    typedef _Tp        value_type;
    typedef Distance   difference_type;
    typedef Pointer    poiner;
    typedef _Refrence  refrence;
};
 
template <typename T, typename Container>
struct my_iterator:public _IterorBase
{
    my_iterator():current(nullptr)
    {
 
    }
 
    my_iterator(T* t):current(t)
    {
 
    }
 
    my_iterator(my_iterator& other):current(other.current)
    {
 
    }
 
    my_iterator(const my_iterator& other):current(other.current)
    {
 
    }
 
    my_iterator(my_iterator&& other):current(other.current)
    {
        other.current = nullptr;
    }
 
    ~my_iterator()
    {
 
    }
 
    my_iterator& operator++()
    {
        current++;
        return *this;
    }
 
    my_iterator& operator++(int)
    {
        current++;
        return *this;
    }
 
    my_iterator& operator--()
    {
        current--;
        return *this;
    }
 
    T& operator*()
    {
        return *(this->current);
    }
 
    int operator-(my_iterator& other)
    {
        return current - other.current;
    }
 
    my_iterator operator-(int other)
    {
        return my_iterator(this->current - other);
    }
 
    my_iterator operator+(int other)
    {
        return my_iterator(this->current + other);
    }
 
    bool operator<(my_iterator& other)
    {
        return (this - other) < 0 ? true:false;
    }
 
    bool operator>(my_iterator& other)
    {
        return (this - other) > 0 ? true:false;
    }
 
    bool operator!=(my_iterator& other)
    {
        return this->current != other.current;
    }
 
    bool operator!=(const my_iterator& other)
    {
        return this->current != other.current;
    }
 
    bool operator==(my_iterator& other)
    {
        return this->current == other.current;
    }
 
    bool operator==(const my_iterator& other)
    {
        return this->current == other.current;
    }
 
    my_iterator& operator=(my_iterator& other)
    {
        this->current = other.current;
        return *this;
    }
 
    my_iterator& operator=(my_iterator&& other)
    {
        this->current = other.current;
        other.current = nullptr;
        return *this;
    }
 
    T* current;
};
 
 
 
 
// my_vector.h
#include
#include
#include
template<typename T>
class my_vector
{
 
public:
    typedef  my_iterator   iterator;
    typedef const iterator  cons_iterator;
 
public:
    my_vector();
 
    my_vector(int count, const T& value);
 
    my_vector(const my_vector& other);
 
    my_vector(my_vector&& other);
 
    ~my_vector();
 
    T& at(int pos);
 
    T& operator[](int pos);
 
    T& front();
 
    T& back();
 
    T* data();
 
    bool empty();
 
    int size();
 
    void reserve(int new_cap);
 
    int capacity();
 
    void clear();
 
    void insert(cons_iterator iter,T& value);
 
    template<typename ...Args>
    void emplace(cons_iterator iter, Args... args)
    {
        if(iter.current == nullptr)
        {
            return;
        }
        if(this->finish == this->end_of_stora)
        {
             reAlloc();
        }
 
        iterator tmp_iter=this->finish + 1;
        for(; tmp_iter == iter; tmp_iter++)
        {
            *tmp_iter = *(tmp_iter - 1);
        }
 
        *tmp_iter = T(std::forward(args)...);
 
        this->finish++;
    }
 
    void push_back(T& value)
    {
        std::cout << "push back: &value: "<< value << " " << this->finish.current << " == " << this->end_of_stora.current << std::endl;
 
        if(this->finish == this->end_of_stora)
        {
             reAlloc();
        }
        *this->finish = value;
        this->finish++;
    }
 
    void push_back(T&& value)
    {
        std::cout << "push back: &&value: " << value << " "<< this->finish.current << " == " << this->end_of_stora.current << std::endl;
        if(this->finish == this->end_of_stora)
        {
             reAlloc();
        }
        *this->finish = value;
        this->finish++;
    }
 
    template<typename ...Args>
    void emplace_back(Args... args)
    {
        if(this->finish == this->end_of_stora)
        {
             reAlloc();
        }
        this->finish = this->finish + 1;
        *this->finish = T(std::forward(args)...);
    }
 
    void pop_back()
    {
        delete *this->finish;
        this->finish--;
    }
 
    iterator begin()
    {
        return iterator(dataPtr);
    }
 
    iterator end()
    {
        return iterator(dataPtr + size());
    }
 
private:
 
    void reAlloc()
    {
        int reLen = (this->end_of_stora - this->start)==0 ? 1 : 2*(this->end_of_stora - this->start);
        reAlloc(reLen);
    }
    void reAlloc(int new_cap)
    {
        int reLen = (this->end_of_stora - this->start)==0 ? 1 : (this->end_of_stora - this->start);
        while (reLen < new_cap) {
            reLen *= 2;
        }
 
        if(dataPtr == nullptr)
        {
            dataPtr = new T[reLen];
            this->start = iterator(dataPtr);
            this->finish = iterator(dataPtr);
            this->end_of_stora = iterator((dataPtr+reLen));
        }
        else
        {
            T* new_data_ptr = new T[reLen];
            int numOfElements = this->finish - this->start;
            for(int i = 0; i < numOfElements; i++)
            {
                new_data_ptr[i] = this->at(i);
            }
            T* tmpPtr = dataPtr;
            dataPtr = new_data_ptr;
            delete [] tmpPtr;
            this->start = iterator(dataPtr);
            this->finish = iterator(dataPtr + numOfElements);
            this->end_of_stora = iterator((dataPtr+reLen));
        }
    }
 
    T* dataPtr = nullptr;
    iterator start;
    iterator finish;
    iterator end_of_stora;
};
 
template<typename T>
my_vector::my_vector()
{
 
}
 
template<typename T>
my_vector::my_vector(int count, const T& value)
{
    for(int i=0; i
    {
        finish++;
    }
 
    if(finish < end_of_stora)
    {
        reAlloc();
    }
 
    for(iterator iter=start; iter != finish; iter++)
    {
        *iter = value;
    }
}
 
template<typename T>
my_vector::my_vector(const my_vector& other)
{
    this->start = other.start;
    this->finish = other.finish;
    this->end_of_stora = other.end_of_stora;
    this->dataPtr = other.dataPtr;
}
 
template<typename T>
my_vector::my_vector(my_vector&& other)
{
    this->start = other.start;
    this->finish = other.finish;
    this->end_of_stora = other.end_of_stora;
    this->dataPtr = other.dataPtr;
 
    other.start = iterator();
    other.finish = iterator();
    other.end_of_stora = iterator();
    other.dataPtr = nullptr;
}
 
template<typename T>
my_vector::~my_vector()
{
    if(dataPtr)
        delete []dataPtr;
}
 
template<typename T>
T& my_vector::at(int pos)
{
    return *(this->dataPtr + pos);
}
 
template<typename T>
T& my_vector::operator[](int pos)
{
    return *(this->dataPtr + pos);
}
 
template<typename T>
T& my_vector::front()
{
    return *start;
}
 
template<typename T>
T& my_vector::back()
{
    return *finish;
}
 
template<typename T>
T* my_vector::data()
{
    return this->dataPtr;
}
 
template<typename T>
bool my_vector::empty()
{
    return this->begin() == this->end();
}
 
template<typename T>
int my_vector::size()
{
    return this->finish - this->start;
}
 
template<typename T>
void my_vector::reserve(int new_cap)
{
    if(end_of_stora - start < new_cap)
    {
        reAlloc(new_cap);
    }
}
 
template<typename T>
int my_vector::capacity()
{
    return this->end_of_stora - this->begin();
}
 
template<typename T>
void my_vector::clear()
{
    this->start = iterator();
    this->finish = iterator();
    this->end_of_stora = iterator();
 
    delete dataPtr;
    dataPtr = nullptr;
}
 
 
template<typename T>
void my_vector::insert(cons_iterator iter,T& value)
{
    if(iter.current == nullptr)
    {
        return;
    }
    if(this->finish == this->end_of_stora)
    {
         reAlloc();
    }
 
    iterator tmp_iter=this->finish + 1;
    for(; tmp_iter == iter; tmp_iter++)
    {
        *tmp_iter = *(tmp_iter - 1);
    }
 
    *tmp_iter = T(value);
 
    this->finish++;
}
 
 
 
 
// main.cpp
 
void testMyVector()
{
    std::cout << "--- testMyVector ---" << std::endl;
 
    my_vector<int> vec1;
    vec1.push_back(666);
 
    for(int i = 0; i < 20; i++)
    {
        vec1.push_back(i);
    }
    vec1.push_back(666);
 
    auto iter = vec1.begin();
    for(int i = 0; i < 22; i++)
    {
        std::cout << *(iter + i) << " --- " << vec1[i] << std::endl;
    }
}
 
int main()
{
    testMyVector();
 
    return 0;
}