Vector介紹

vector是STL中容器之一，特性如下：

1. vector是表示可變大小數(shù)組的序列容器。
2. 就像數(shù)組一樣，vector也采用的連續(xù)存儲空間來存儲元素。也就是意味著可以采用下標對vector的元素 進行訪問，和數(shù)組一樣高效。但是又不像數(shù)組，它的大小是可以動態(tài)改變的，而且它的大小會被容器自 動處理。
3. 本質(zhì)講，vector使用動態(tài)分配數(shù)組來存儲它的元素。當新元素插入時候，這個數(shù)組需要被重新分配大小 為了增加存儲空間。其做法是，分配一個新的數(shù)組，然后將全部元素移到這個數(shù)組。就時間而言，這是
   一個相對代價高的任務，因為每當一個新的元素加入到容器的時候，vector并不會每次都重新分配大 小。
4. vector分配空間策略：vector會分配一些額外的空間以適應可能的增長，因為存儲空間比實際需要的存 儲空間更大。不同的庫采用不同的策略權衡空間的使用和重新分配。但是無論如何，重新分配都應該是
   對數(shù)增長的間隔大小，以至于在末尾插入一個元素的時候是在常數(shù)時間的復雜度完成的。
5. 因此，vector占用了更多的存儲空間，為了獲得管理存儲空間的能力，并且以一種有效的方式動態(tài)增 長。
6. 與其它動態(tài)序列容器相比（deque, list and forward_list）， vector在訪問元素的時候更加高效，在末 尾添加和刪除元素相對高效。對于其它不在末尾的刪除和插入操作，效率更低。比起list和forward_list 統(tǒng)一的迭代器和引用更好

Vector實現(xiàn)

常見接口函數(shù)羅列：

1、定義

默認構造函數(shù)使用

int main()
{
	vector<int> first;//無參構造
	vector<int> second(4, 0);//使用4個0初始化構造
	vector<int> third(second.begin(), second.end());//迭代器區(qū)間構造
	vector<int> fourth(third);//拷貝構造，使用third構造
	return 0;
}

運行結果

實現(xiàn)

//無參構造
   			  vector()
                :_start(nullptr)
                ,_finish(nullptr)
                , _endOfStorage(nullptr)
            {
                
            }
//構造并初始化n個value
            vector(int n, const T& value = T())
                :_start(nullptr)
                , _finish(nullptr)
                , _endOfStorage(nullptr)
            {
                reserve(n);//是否需要擴容
                for (size_t i = 0; i < n; i++)
                {
                    push_back(value);
                }
            }
//迭代器區(qū)間構造
         template<class inputiterator>
         vector(inputiterator first, inputiterator last)
             :_start(nullptr)
             ,_finish(nullptr)
             ,_endofstorage(nullptr)
         {
             while (first != last)
             {
                 push_back(*first);
                 first++;
             }
         }
//拷貝構造
         vector(const vector<T>& v)
         {
             _start = new T[v.capacity()];
             for (int i = 0; i < v.size(); i++)
             {
                 _start[i] = v._start[i];
             }
             _finish = _start + v.size();
             _endOfStorage = _start + v.capacity();
       
         }

涉及資源管理一般都是開空間，拷貝數(shù)據(jù)。

2、迭代器Iterator

對于Vector內(nèi)部實現(xiàn)訪問，修改可以很實用迭代器來進行

迭代器使用

int main()
{
	vector<int> v;
	v = { 1,2,3,4,5,6,7,8 };
	vector<int>::iterator It = v.begin();
	//1、使用迭代器遍歷
	/*for (It; It != v.end(); It++)
	{
		cout << *It << " ";
	}
	cout << endl;*/
	//2
	auto it = v.begin();
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	
//修改遍歷
	for (It; It != v.end(); It++)
	{
		cout << ( * It * 2) << " ";
	}
	cout << endl;

	return 0;
}

運行結果

對于迭代器使用還有一個C++中支持的范圍for（語法糖），auto會自己識別=右邊類型，底層也是迭代器。

for(auto e:v)

3、空間增長問題

使用

int main()
{
	vector<int> ve;
	ve.resize(10, 0);
	cout <<"size:" << ve.size() << endl;
	cout <<"capacity:"<< ve.capacity() << endl;

	ve.reserve(40);
	cout << "size:" << ve.size() << endl;
	cout << "capacity:" << ve.capacity() << endl;
}

運行結果：

實現(xiàn)

		 void reserve(size_t n)
        {
            if (n > capacity())
            {
                T* tmp = new T[n];
                size_t sz = size();//保存原來size

                if (_start)
                {
                    //深拷貝
                    for (int 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& value = T())
        {
            //減小個數(shù)
            if (n < size())
            {
                _finish = _start + n;
            }
            else
            {
                //擴容
                if (n > capacity())
                {
                    reserve(n);
                }

                while (_finish!=_start+n)
                {
                    *_finish = value;
                    _finish++;
                }
            }
        }

對于vector中的size和capacity可以和數(shù)據(jù)結構中的順序表來對比實現(xiàn)。對于reserve使用一般會考慮在擴容時使用，一般不會使用縮容這個行為。縮容會對效率，和空間釋放上造成困難。不支持部分空間釋放。resize可以對于空間開辟加初始化。

迭代器

迭代器介紹

InputIterator：輸入迭代器。支持對容器元素的逐個遍歷，以及對元素的讀?。╥nput)；
OutputIterator：輸出迭代器。支持對容器元素的逐個遍歷，以及對元素的寫入（output)。
ForwardIterator：前向迭代器。向前逐個遍歷元素?？梢詫υ刈x取；
BidirectionalIterator：雙向迭代器。支持向前向后逐個遍歷元素，可以對元素讀取。
RandomAccessIterator：隨機訪問迭代器。支持O(1)時間復雜度對元素的隨機位置訪問，支持對元素的讀取。

迭代器的主要作用就是讓算法能夠不用關心底層數(shù)據(jù)結構，其底層實際就是一個指針，或者是對指針進行了封裝，比如：vector的迭代器就是原生態(tài)指針T* 。因此迭代器失效，實際就是迭代器底層對應指針所指向的空間被銷毀了，而使用一塊已經(jīng)被釋放的空間，造成的后果是程序崩潰(即如果繼續(xù)使用已經(jīng)失效的迭代器，程序可能會崩潰)。

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

         iterator begin()
        {
            return _start;
        }

        iterator end()
        {
            return _finish;
        }

        const_iterator cbegin()const 
        {
            return _start;
        }

        const_iterator cend() const
        {
            return _finish;
        }

這樣的代碼書寫只能使用在底層空間連續(xù)的數(shù)據(jù)結構中。就不太符合迭代器出現(xiàn)的意義?？梢圆捎靡粋€類來進行封裝。

迭代器實現(xiàn)

//反向迭代器
namespace uu
{
	template<class Iterator, class Ref, class Ptr>
	struct ReverseIterator
	{
		typedef ReverseIterator<Iterator, Ref, Ptr> Self;
		Iterator _cur;

		ReverseIterator(Iterator it)
			:_cur(it)//正向迭代器構造
		{}

		Ref operator*()
		{
			Iterator tmp = _cur;
			--tmp;
			return *tmp;
		}

		Self& operator++()
		{
			--_cur;
			return *this;
		}

		Self& operator--()
		{
			++_cur;
			return *this;
		}

		bool operator!=(const Self& s)
		{
			return _cur != s._cur;
		}
	};
}

迭代器失效問題主要在于對于vector中會引起其底層空間改變的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back等。

失效原因：擴容時就會改變底層空間改變，主要就是擴容會釋放舊空間，但是迭代器底層是指針，舊空間被釋放掉，但是指針指向還是在舊空間中，就會形成野指針。第二次訪問就會出錯。
解決方法：使用插入位置與頭指針的相對位置來進行新空間的位置更新。并返回插入位置。

  iterator insert(iterator pos, const T& x)
            {
                assert(_start <= pos);
                assert(pos<= _finish);

                if (_start == _endOfStorage)
                {
                    size_t len = pos - _start;//計算相對位置

                    reserve(capacity() == 0 ? 8 : capacity() * 2);

                    pos = _start + len;//防止野指針，迭代器失效，更新
                }
                iterator end = _finish - 1;
                while (end>=pos)
                {
                    *(end + 1) = *(end);
                    end--;
                }
                *(pos) = x;
                _finish++;
                
                 return pos;//解決pos再次被使用，迭代器失效
            }

失效原因：刪除指定位置后，數(shù)據(jù)會向前移，底層空間沒有改變。但是位置在最后一個數(shù)據(jù)的位置就會出現(xiàn)越界，end在有效區(qū)間外就會失效。
解決方法：返回迭代器的位置。

 iterator erase(iterator pos)
            {
                assert(pos >= _start);
                assert(pos < _finish);

                iterator start =pos + 1;//避免pos=0；頭刪越界,類型是迭代器

                while (start != _finish)
                {
                    *(start - 1) = *(start);
                    start++;
                }
                _finish--;

                return pos;
            }

對于底層空間連續(xù)的數(shù)據(jù)結構都會使用[]來進行數(shù)據(jù)訪問修改，這樣可以避免迭代器失效問題。更加便捷。文章來源地址http://www.zghlxwxcb.cn/news/detail-446823.html

到了這里，關于STL常用梳理——VECTOR常用接口及其迭代器實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！