1、vector的介紹

vector文檔介紹

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

2、vector的使用

vector在實際中非常的重要，在實際中我們熟悉常見的接口就可以，下面列出了哪些接口是要重點掌握的并且會模擬實現(xiàn)。

2.1 vector的定義

代碼實現(xiàn)：

template<class T>
    class vector
    {
    public:
    	typedef T* iterator;//typedef愿意給別人用就放在public，不想就放在private
        typedef const T* const_iterator;

    	vector()
        {}

        vector(int n, const T& value = T())
        {
            reserve(n);
            for (size_t i = 0; i < n; i++)
            {
                push_back(value);
            }
        }

        template<class InputIterator>

        vector(InputIterator first, InputIterator last)
        {
            while (first != last)
            {
                push_back(*first);
                ++first;
            }   
        }

        vector(const vector<T>& v)
        {
            reserve(v.capacity());
            for (auto& e : v)
            {
                push_back(e);
            }
        }

    private:
    iterator _start = nullptr; // 指向數(shù)據(jù)塊的開始
    iterator _finish = nullptr; // 指向有效數(shù)據(jù)的尾
    iterator _endOfStorage = nullptr; // 指向存儲容量的尾
};

2.2 vector迭代器的使用

在 vector 中迭代器底層也是原生指針。

模擬實現(xiàn)：

typedef T* iterator;//typedef愿意給別人用就放在public，不想就放在private
typedef const T* const_iterator;

iterator begin()
{
    return _start;
}

iterator end()
{
    return _finish;
}

const_iterator begin() const
{
    return _start;
}

const_iterator end() const
{
    return _finish;
}

使用：
迭代器一般使用在遍歷，我們來看一下。

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> v;
	//我們這里使用push_back來插入數(shù)據(jù)
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);

	//迭代器方式遍歷
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}

	return 0;
}

2.3 vector的空間增長問題

reserve接口：
reserve只負(fù)責(zé)開辟空間，如果確定知道需要用多少空間，reserve可以緩解vector增容的代價缺陷問題。

void reserve(size_t n)//reserve只擴不縮
{
    if (n > capacity())
    {
        T* tmp = new T[n];
        size_t sz = size();//這里必須先記下sz，_finish要是直接+size()會出問題
                           //_start指的是新空間，調(diào)用size()，size()內(nèi)部會出問題
                           //因此先記下來后面用最合適
        if (_start)
        {
            //memcpy是淺拷貝，會出問題
            //memcpy(tmp, _start, sizeof(T) * sz);
            for (size_t i = 0; i < size(); i++)
            {
                tmp[i] = _start[i];
            }
            delete[] _start;
        }

        _start = tmp;
        _finish = _start + sz;
        _endOfStorage = _start + n;
    }
}

resize接口：
resize在開空間的同時還會進(jìn)行初始化，影響size。

void resize(size_t n, const T& value = T())//匿名對象/臨時對象具有常性，需要const修飾
{
    if (n <= size())//縮容
    {
        _finish = _start + n;
    }
    else
    {
        reserve(n);//這里可以不用判斷是否要擴容，reserve里面會判斷

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

其他幾個接口比較簡單，直接實現(xiàn)：

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

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

bool empty()
{
	return _finish - _start == 0;
}

注意：

在擴容的時候有一個區(qū)別，vs下capacity是按1.5倍增長的，g++是按2倍增長的。不要固化的認(rèn)為，vector增容都是2倍，具體增長多少是根據(jù)具體的需求定義的。vs是PJ版本STL，g++是SGI版本STL。
我們來測試一下：

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> v;
	size_t sz = v.capacity();

	for (size_t i = 0; i < 100; i++)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed：" << sz << endl;
		}
	}

	return 0;
}

3、vector的增刪查改

3.1 push_back（重點）

我們梳理尾插的思路：
1、先判斷容量是否滿了，如果滿了先擴容。這里注意，尾插的時候是否為空，這里使用三木操作符進(jìn)行判斷一下，如果為空先擴4個空間，否則2倍擴法。
2、尾插，再++_finish。

void push_back(const T& x)
{
    if (_finish == _endOfStorage)
    {
        reserve(capacity() == 0 ? 4 : 2 * capacity());
    }

    *_finish = x;
    ++_finish;
}

3.2 pop_back（重點）

在尾刪的時候我們依然是先判斷
這次我們需要判空，用斷言assert(_finish - _start != 0)，再去尾刪，讓_finish–就好了，下一次尾插的時候直接覆蓋。

void pop_back()
{
    assert(_finish-_start != 0);

    --_finish;
    //erase(end() - 1);
}

3.3 operator[]（重點）

[]的重載就是返回pos位置上數(shù)據(jù)就可以，比較簡單直接秒殺。
我們這里給兩個接口，一個是只讀的，一個是可以修改的。

T& operator[](size_t pos)//寫
{
    assert(pos < size());//判斷位置是否合法
    return _start[pos];
}

const T& operator[](size_t pos)const//讀
{
    assert(pos < size());
    return _start[pos];
}

3.4 insert

insert是在pos位置插入一個數(shù)據(jù)。
思路：
1、先判斷pos位置是否合法；
2、判滿，如果滿了就需要擴容，在擴容的時候需要注意迭代器失效的問題；
3、因為插入數(shù)據(jù)就存在挪動數(shù)據(jù)，因此需要先挪動數(shù)據(jù)，我們 從后往前 依次后移一個位置的數(shù)據(jù)，挪到pos位置；
4、再去給pos位置插入數(shù)據(jù)，最后返回pos位置。

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

    if (_finish == _endOfStorage)
    {
        size_t len = pos - _start;//先記下_start到pos位置的距離，因為擴容后迭代器pos就會失效
        reserve(capacity() == 0 ? 4 : 2 * capacity());
        pos = _start + len;//新的空間需要更新迭代器pos
    }

    iterator end = _finish - 1;
    //挪動數(shù)據(jù)
    while (end >= pos)
    {
        *(end + 1) = *end;
        --end;
    }

    *pos = x;
    ++_finish;

    return pos;
}

3.5 erase

erase是刪除pos位置的數(shù)據(jù)。
思路：
1、判斷pos位置是否合法；
2、挪動數(shù)據(jù)，從 pos位置到尾 依次向前挪動數(shù)據(jù)，直接用pos+1的數(shù)據(jù)覆蓋掉pos位置的數(shù)據(jù)即可；
3、–_finish，返回pos位置即可。

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

    iterator it = pos + 1;
    //挪動數(shù)據(jù)
    while (it < _endOfStorage)
    {
        *(it - 1) = *it;
        ++it;
    }
    --_finish;

    return pos;
}

3.6 swap

我們vector的swap直接套用庫函數(shù)的swap來實現(xiàn)就好了。

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

*** 本篇結(jié)束 ***文章來源地址http://www.zghlxwxcb.cn/news/detail-672071.html

到了這里，關(guān)于[C++] STL_vector使用與常用接口的模擬實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！