【c++】vector的特性及使用

目录

一、vector的介绍及使用

1、vector迭代器的使用

2、vector的空间增长

3、vector的迭代器失效问题

二、vector的深度剖析与模拟实现

---

一、vector的介绍及使用

1、vector迭代器的使用

? ? ? ? vector的迭代器就是原生态指针。vector的迭代器使用方法与string的迭代器使用方法相同。

2、vector的空间增长

? ? ? ? （1）capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。

? ? ? ? （2）reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。

? ? ? ? （3）resize在开空间的同时还会进行初始化，影响size。

3、vector的迭代器失效问题

? ? ? ? 迭代器的主要作用就是让算法不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装。比如：vector的迭代器就是原生态指针T*，因此迭代器失效实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块被释放的空间，造成的后果是程序崩溃（即如果继续使用已经失效的迭代器，程序可能会崩溃）。对于vector可能会导致其迭代器失效的操作有：

? ? ? ? （1）会引起底层空间改变的操作，都有可能导致迭代器失效。如：resize、reserve、insert、push_back等。

? ? ? ? ? ? ? ? 以上操作都有可能导致vector扩容，即vector底层原来的旧空间被释放，而再打印时it还使用的释放之前的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放掉的空间，从而引起代码运行崩溃。如果想要继续通过迭代器操作vector中的元素，只需给it重新赋值即可。

? ? ? ? （2）指定位置元素的删除操作---erase

? ? ? ? ? ? ? ? erase删除pos位置元素后，pos位置之后的元素会往前移动，没有导致底层空间的变化，理论上讲迭代器不应该失效，但是：如果pos刚好是最后一个元素，删除掉最后一个元素之后pos就变成了end的位置，而end位置是没有有效元素的，那么pos就会失效。因此，删除vector中任意位置上元素时，vs就会认为

? ? ? ? （3）Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs那么极端：

? ? ? ? ? ? ? ? a、扩容后，迭代器已经失效了，程序虽然可以运行，但是运行结果会发生变化。

? ? ? ? ? ? ? ? b、erase删除任意位置代码后，Linux下的迭代器不会失效，因为空间还是原来的空间，后续元素整体往前移动，it的位置还是有效的。

? ? ? ? ? ? ? ? c、erase删除的迭代器如果是最后一个元素，删除之后it已经超过end，此时迭代器失效，++it导致迭代器失效。

? ? ? ? ? ? ? ? 总结：Linux中，迭代器失效后代码并不一定会崩溃，但是运行结果一定会改变，如果it不在begin和end的范围内，程序一定崩溃。

二、vector的深度剖析与模拟实现

? ? ? ? 以vector的（push_back()）尾插为例剖析其底层逻辑：

? ? ? ? vector的增删查改模拟实现：

//模拟实现vector类，并完成测试
namespace lbj
{
    template<class T>
    class vector
    {
    public:

        // Vector的迭代器是一个原生指针
        typedef T* iterator;
        typedef const T* const_iterator;

        //iterator
        iterator begin()
        {
            return _start;
        }

        iterator end()
        {
            return _finish;
        }

        const_iterator cbegin() const
        {
            return _start;
        }

        const_iterator cend() const
        {
            return _finish;
        }

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

        size_t capacity() const
        {
            return _endOfStorage - _start;
        }

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

        void resize(size_t n, const T& value = T())
        {
            if (n <= size())
            {
                _finish = _start + n;
            }
            else
            {
                reserve(n);
                while (_finish < _start + n)
                {
                    *_finish = value;
                    _finish++;
                }
            }
        }
        
        //access
        T& operator[](size_t pos)
        {
            assert(pos < size());
            return _start[pos];
        }

        const T& operator[](size_t pos)const
        {
            assert(pos < size());
            return _start[pos];
        }
        
        //modify
        void push_back(const T& x)
        {
            size_t sz = size();
            if (_finish == _endOfStorage)
            {
                reserve(capacity() == 0 ? 5 : capacity() * 2);
            }
            *_finish = x;
            _finish++;
        }

        void pop_back()
        {
           --_finish;
        }

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

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

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

        // construct and destroy
        vector()
            :_start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {}

        vector(int n, const T& value = T())
            :_start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            resize(n, value);
        }

        template<class InputIterator>   //类模板里边的模板函数
        vector(InputIterator first, InputIterator last)    //迭代器区间是左闭右开的形式
        {
            while (first != last)
            {
                push_back(*first);
                first++;
            }
        }

        vector(vector<T>& v)
            :_start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            reserve(v.capacity());
            for (auto num : v)
            {
                push_back(num);
            }
        }

        vector<T>& operator= (vector<T> v)  //传值：会调用拷贝构造，生成临时对象，函数里边改变临时对象不会改变v的值
        {
            swap(v);
            return *this;
        }

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

    private:
        iterator _start; // 指向数据块的开始
        iterator _finish; // 指向有效数据的尾
        iterator _endOfStorage; // 指向存储容量的尾
    };
}