目錄

目前成都創(chuàng)新互聯(lián)已為近千家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)頁空間、網(wǎng)站改版維護(hù)、企業(yè)網(wǎng)站設(shè)計、華龍網(wǎng)站維護(hù)等服務(wù)，公司將堅持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

1.vector的介紹及使用 ?

1.1 vector的介紹

1.2 vector的使用

1.2.1 vector的定義

1.2.2 vector iterator 的使用

1.2.3 vector 空間增長問題

1.2.3 vector 增刪查改

1.2.4 vector 迭代器失效問題。（重點(diǎn)）

1.2.5 vector 在OJ中的使用

2.vector深度剖析及模擬實(shí)現(xiàn)

使用memcpy拷貝問題

動態(tài)二維數(shù)組理解

模擬實(shí)現(xiàn)vector：

---

1.vector的介紹及使用 ? 1.1 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ù)，因?yàn)槊慨?dāng)一個新的元素加入到容器的時候，vector 并不會每次都重新分配大小。 4. vector 分配空間策略： vector 會分配一些額外的空間以適應(yīng)可能的增長，因?yàn)榇鎯臻g比實(shí)際需要的存儲空間更大。不同的庫采用不同的策略權(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)一的迭代器和引用更好

1.2 vector的使用 1.2.1 vector的定義

以上就是vector的構(gòu)造函數(shù)，重點(diǎn)關(guān)注1和3

1.2.2 vector iterator 的使用

我們可以看到這里的iterator行為上就像指針一樣，但又不一定是指針?，而對于vector這里來說，這里的iterator就是一個原生指針，后面會講到迭代器失效的問題。

1.2.3 vector 空間增長問題

這里的resize和reserve和之前的string的含義一樣，這里就看看函數(shù)的使用方式即可：

capacity 的代碼在 vs 和 g++ 下分別運(yùn)行會發(fā)現(xiàn)， vs下capacity是按1.5倍增長的，g++是按2倍增長的。 這個問題經(jīng)常會考察，不要固化的認(rèn)為， vector 增容都是 2 倍，具體增長多少是根據(jù)具體的需求定義的。 vs是PJ版本STL，g++是SGI版本STL 。（ 也就是不同編譯器的實(shí)現(xiàn)方式不同，所以可能會導(dǎo)致有不同的結(jié)果） reserve 只負(fù)責(zé)開辟空間，如果確定知道需要用多少空間， reserve 可以緩解 vector 增容的代價缺陷問題。 resize 在開空間的同時還會進(jìn)行初始化，影響 size 。

這是vs下的擴(kuò)容：

reserve的優(yōu)勢就在于如果我們知道要開多少空間，我們就可以一次性開好，就可以避免頻繁的擴(kuò)容，因?yàn)槲覀冎李l繁擴(kuò)容是要付出代價的，所以C++在這方面做的很好。

1.2.3 vector 增刪查改

為什么不推薦使用insert以及erase呢？因?yàn)槲覀冎罃?shù)組刪除數(shù)據(jù)是要挪動數(shù)據(jù)的，這樣就導(dǎo)致花費(fèi)更多時間，所以一般情況下不推薦使用。

上述內(nèi)容很簡單，查網(wǎng)站就會使用，不過多講解，下面主要講解迭代器失效的問題；

1.2.4 vector 迭代器失效問題。（重點(diǎn)）

迭代器的主要作用就是讓算法能夠不用關(guān)心底層數(shù)據(jù)結(jié)構(gòu)，其底層實(shí)際就是一個指針，或者是對指針進(jìn)行了封裝，比如：vector的迭代器就是原生態(tài)指針T* 。因此迭代器失效，實(shí)際就是迭代器底層對應(yīng)指針?biāo)赶虻目臻g被銷毀了，而使用一塊已經(jīng)被釋放的空間，造成的后果是程序崩潰(即如果繼續(xù)使用已經(jīng)失效的迭代器，程序可能會崩潰)。 為什么會這樣呢？ 下面我們看幾個例子：

1. 會引起其底層空間改變的操作，都有可能是迭代器失效 ，比如： resize 、 reserve 、 insert 、 assign 、push_back等。 拿擴(kuò)容來說，reserve的底層實(shí)現(xiàn)是講原來的空間釋放掉，然后開辟新的空間，這樣迭代器所在的位置就發(fā)生了改變，所以最后就導(dǎo)致了迭代器失效了。 我們看看下面這段代碼：

#includeusing namespace std;
#includeint main()
{
	vectorv{ 1,2,3,4,5,6 };
	auto it = v.begin();
	v.assign(100, 3);
	//因?yàn)檫@里擴(kuò)容過，所以迭代器肯定失效
	while (it != v.end())
	{
		cout<< *it<< " ";
		++it;
	}
	cout<< endl;
	return 0;
}

結(jié)果正如我們所料：

解決這個辦法就是更新一下迭代器即可正常使用。

看看其他例子：

2. 指定位置元素的刪除操作--erase

int main()
{
	int a[] = { 1, 2, 3, 4 };
	vectorv(a, a + sizeof(a) / sizeof(int));
	// 使用find查找3所在位置的iterator
	vector::iterator pos = find(v.begin(), v.end(), 3);
	// 刪除pos位置的數(shù)據(jù)，導(dǎo)致pos迭代器失效。
	v.erase(pos);
	cout<< *pos<< endl; // 此處會導(dǎo)致非法訪問
	return 0;
}

erase 刪除 pos 位置元素后， pos 位置之后的元素會往前搬移， 沒有導(dǎo)致底層空間的改變，理論上講迭代器不應(yīng)該會失效 ，但是： 如果pos剛好是最后一個元素，刪完之后pos剛好是end的位置，而end位置是沒有元素的，那么pos就失效了。因此刪除vector中任意位置上元素時，vs就認(rèn)為該位置迭代器失效了。 我們可以看到 vs實(shí)現(xiàn)的方式是比較嚴(yán)格的 ，如果不更新迭代器這就無法使用了。后面我們會模擬實(shí)現(xiàn)vector，后面我們模擬實(shí)現(xiàn)的就可以使用。 如果要 刪除vector中所有的偶數(shù)，我們應(yīng)該怎么做呢？ 下面這樣就是有問題的：

int main()
{
	vectorv{ 1, 2, 3, 4 };
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
			v.erase(it);
		++it;
	}

	return 0;
}

不難發(fā)現(xiàn)這里肯定是有問題的，因?yàn)閯h除完4之后it又++就已經(jīng)越界訪問了。

我們可以在不是偶數(shù)的時候再++，同時更新一下it，是偶數(shù)的就不用++

int main()
{
	vectorv{ 1, 2, 3, 4 };
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
			it = v.erase(it);
		else
		{
			++it;
		}
	}
	for (auto& e : v)
	{
		cout<< e<< endl;
	}
	return 0;
}

但是在Linux底下g++編譯器就沒有檢查的那么嚴(yán)格：

看看擴(kuò)容這段代碼：

// 1. 擴(kuò)容之后，迭代器已經(jīng)失效了，程序雖然可以運(yùn)行，但是運(yùn)行結(jié)果已經(jīng)不對了
int main()
{
	vectorv{ 1,2,3,4,5 };
	for (size_t i = 0; i< v.size(); ++i)
		cout<< v[i]<< " ";
	cout<< endl;
	auto it = v.begin();
	cout<< "擴(kuò)容之前，vector的容量為: "<< v.capacity()<< endl;
	// 通過reserve將底層空間設(shè)置為100，目的是為了讓vector的迭代器失效 
	v.reserve(100);
	cout<< "擴(kuò)容之后，vector的容量為: "<< v.capacity()<< endl;

	// 經(jīng)過上述reserve之后，it迭代器肯定會失效，在vs下程序就直接崩潰了，但是linux下不會
	// 雖然可能運(yùn)行，但是輸出的結(jié)果是不對的
	while (it != v.end())
	{
		cout<< *it<< " ";
		++it;
	}
	cout<< endl;
	return 0;
}

可以看到Linux底下是沒有報錯的，因?yàn)榭臻g還是原來的空間，后序元素往前搬移了，it的位置還是有效的，但是對于剛剛那個偶數(shù)那題Linux下也會報錯：

4. 與vector類似，string在插入+擴(kuò)容操作+erase之后，迭代器也會失效

最后說說如何解決這類問題：

迭代器失效解決辦法：在使用前，對迭代器重新賦值即可 1.2.5 vector 在OJ中的使用

因?yàn)閿?shù)組在實(shí)際的應(yīng)用非常廣泛，所以C++的vector的運(yùn)用也是非常多，而且嵌套vector遠(yuǎn)遠(yuǎn)比C語言中的二維數(shù)組好用，下面我們就來看看vector在oj中的應(yīng)用：

1. 力扣

這題楊輝三角實(shí)現(xiàn)起來其實(shí)并不是很難，但是如果使用C語言來做就很難受了，因?yàn)殚_辟空間那里就會讓你非常頭疼，但是對于C++來說這又不是一件難事了。這里就體現(xiàn)了嵌套vector的優(yōu)點(diǎn)了。 思路： 先開辟好一個vector>,這樣相當(dāng)于C語言中的二維數(shù)組了。然后調(diào)整好空間，在第一行以及對角線的那一行初始化為1，其他的初始化為0，然后我們就可以遍歷這個嵌套vector，判斷是否0的元素，是就讓其加上上一行的前一個以及上一行的那個。

實(shí)現(xiàn)方式：

class Solution {
public:
    vector>generate(int numRows) {
        //先開辟空間
        vector>vv;
        vv.resize(numRows);
        for(size_t i= 0 ;i

2.力扣

這道題如果使用哈希表的話就超出了這個空間復(fù)雜度了，用暴力查找的方式又不符合題意，這里有一個思路非常巧妙：

我們可以利用位運(yùn)算來解決，因?yàn)檫@個除了這個數(shù)字其他的數(shù)字都出現(xiàn)過3次，我們可以把數(shù)組中的每一個數(shù)字的二進(jìn)制位加起來，然后讓結(jié)果%3就可以得到我們所想要的二進(jìn)制位了，（不論是0還是1，%3的結(jié)果都是我們想要的那個數(shù)的二進(jìn)制位），最后我們用ret每次接受一下要的到二進(jìn)制位，就可以得到答案。

代碼實(shí)現(xiàn)：

class Solution {
public:
    int singleNumber(vector& nums) {
        //我們可以把所有的二進(jìn)制位全部加起來，然后%3就可以得到所求的數(shù)字的二進(jìn)制位了
        int ret = 0;//我們要求的數(shù)字
        for(int i = 0;i<32;++i)
        {
            int sum = 0;
            for(auto e:nums)
            {
                sum += ((e>>i) & 1);
            }
            //把要求的數(shù)字的二進(jìn)制位找出來
            if(sum%3)
            {
                ret |= (1<

3.數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字_?？皖}霸_?？途W(wǎng)

思路：因?yàn)樗霈F(xiàn)的元素的個數(shù)超過了一般半，我們就可以通過計數(shù)的方式記錄它，如果是這個元素就++，不是就--，最后得到的那個數(shù)一定是我們想要的數(shù)，另外，我們還可以拓展一下：如果這個數(shù)不一定存在那要怎么處理？

我們可以對這個記錄一下這個數(shù)，然后再遍歷一次數(shù)組，通過計數(shù)的方式去確認(rèn)是否存在。

代碼實(shí)現(xiàn)：

class Solution {
public:
    int MoreThanHalfNum_Solution(vectornumbers) {
    //因?yàn)樗霈F(xiàn)的元素的個數(shù)超過了一般半，我們就可以通過計數(shù)的方式記錄它，如果是這個元素就++，不是就--
    //這樣的話就可以在最后的時候找到這個元素
    int tmp = numbers[0];//記錄我們要求的數(shù)據(jù)
    int times = 1;
    for(int i = 1;i

4.力扣

這一題的難度比較大，運(yùn)用到了回溯算法

思路：

我們可以通過一個數(shù)組來記錄數(shù)字與字母之間的映射關(guān)系，然后利用回溯算法（遞歸）就解決像這種組合問題，下面通過這題來大概講解一下回溯：

這個很像二叉樹的遍歷，但又復(fù)雜一點(diǎn)，這個可以看成多叉樹的遍歷方式。我們可以通過每一層的遞歸來達(dá)到一個組合的效果。

代碼實(shí)現(xiàn)：

class Solution {
    //映射數(shù)組
    string numstr[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:
    //遞歸子函數(shù)
    void combine(string& digits,int i,vector& vcombine,string retstr)
    {
        if(i == digits.size())
        {
            vcombine.push_back(retstr);
            return;
        }
        //找到對應(yīng)的字母
        int num = digits[i]- '0';
         string str = numstr[num];
         //遍歷串中的所有字符，然后進(jìn)入下一層
         for(auto ch:str)
         {
             combine(digits,i+1,vcombine,retstr+ch);
         }
    }
    vectorletterCombinations(string digits) {
        vectorvcombine;
        if(digits.empty())
        {
            return vcombine;
        }
        int i = 0;
        string retstr;//用來每次加，然后最后加到vcombine中 
        //遞歸
        combine(digits,i,vcombine,retstr);
        return vcombine;
    }
};

下面通過畫遞歸展開圖再來看看其中的細(xì)節(jié)：


2.vector深度剖析及模擬實(shí)現(xiàn) 使用memcpy拷貝問題

1. memcpy是內(nèi)存的二進(jìn)制格式拷貝，將一段內(nèi)存空間中內(nèi)容原封不動的拷貝到另外一段內(nèi)存空間中 2. 如果拷貝的是自定義類型的元素， memcpy 既高效又不會出錯，但 如果拷貝的是自定義類型元素，并且自定義類型元素中涉及到資源管理時，就會出錯，因?yàn)閙emcpy的拷貝實(shí)際是淺拷貝。

這個和之前講拷貝構(gòu)造的時候很像，都是淺拷貝導(dǎo)致的問題。?可能會引起內(nèi)存泄漏甚至程序崩潰。

動態(tài)二維數(shù)組理解

在前面就已經(jīng)看過了二維數(shù)組的題了，這里不過多介紹，還是介紹一下memcpy也會使內(nèi)存崩潰的結(jié)果：

要解決這個問題，我們還是要進(jìn)行深拷貝，這是下面的reserve的模擬實(shí)現(xiàn)代碼來解決這個問題：

我們可以通過這個一個對象賦值的方式來進(jìn)行深拷貝

模擬實(shí)現(xiàn)vector：

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

            iterator begin()
            {
                return _start;
            }
            iterator end()
            {
                return _end;
            }
            const_iterator cbegin()
            {
                return _start;
            }
            const_iterator cend() const
            {
                return _end;
            }

            // construct and destroy

            vector()
                :_start(nullptr)
                ,_end(nullptr)
                ,_endOfStorage(nullptr)
            {}

            vector(int n, const T& value = T())
                :_start(nullptr)
                , _end(nullptr)
                , _endOfStorage(nullptr)
            {
                reserve(n);
                for (int i = 0; i< n; ++i)
                {
                    push_back(value);
                }
            }

            templatevector(InputIterator first, InputIterator last)
                :_start(nullptr)
                , _end(nullptr)
                , _endOfStorage(nullptr)
            {
                while (first != last)
                {
                    push_back(*first);
                    ++first;
                }
            }

            vector(const vector& v)
                :_start(nullptr)
                , _end(nullptr)
                , _endOfStorage(nullptr)
            {
                //找個工具人
                vectortmp(v._start, v._end);
                swap(tmp);
            }

            vector& operator= (vectorv)
            {
                swap(v);
                return *this;
            }

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

            // capacity

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

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

            void reserve(size_t n)
            {
                //堅持不縮容
                if (n >capacity())
                {
                    //開辟新的空間，然后賦值過去
                    T* tmp = new T[n];
                    size_t oldsize = size();
                    if (_start)
                    {
                        for (size_t i = 0; i< oldsize; ++i)
                        {
                            tmp[i] = _start[i];
                        }
                        delete[]_start;
                    }
               
                    _start = tmp;
                    _end = _start + oldsize;
                    _endOfStorage = _start + n;
                }
            }

            void resize(size_t n, const T& value = T())
            {
                //要擴(kuò)容
                if (n >capacity())
                {
                    int newcapacity = capacity() == 0 ? 4 : 2 * capacity();
                    reserve(newcapacity);
                }
    
                if (n >size())
                {
                    while (_end != _start + n)
                    {
                        push_back(value);
                    }
                }
                else
                {
                    _end = _start + n;
                }
            }



            ///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)
            {
                if (size() == capacity())
                {
                    int newcapacity = capacity() == 0 ? 4 : 2 * capacity();
                    reserve(newcapacity);
                }
                *_end = x;
                ++_end;
            }

            void pop_back()
            {
                assert(_end >_start);
                --_end;
            }

            void swap(vector& v)
            {
                std::swap(_start, v._start);
                std::swap(_end, v._end);
                std::swap(_endOfStorage, v._endOfStorage);
            }

            iterator insert(iterator pos, const T& x)
            {
                assert(_start<= pos);
                assert(_end >pos);
                //判斷增容
                int distance = pos - _start;
                if (_end == _endOfStorage)
                {
                    int newcapacity = capacity() == 0 ? 4 : 2 * capacity();
                    reserve(newcapacity);
                    //這里的擴(kuò)容不處理會導(dǎo)致迭代器失效
                    pos = _start + distance;
                }
                //挪動數(shù)據(jù)，插入
                auto end = _end -1;
                while (end >= pos)
                {
                    *(end+1) = *end;
                    --end;
                }
                *pos = x;
                ++_end;
                return pos;
            }

            iterator erase(iterator pos)
            {
                assert(pos >= _start);
                assert(pos< _end);
                //挪動數(shù)據(jù)
                iterator  ret = pos + 1;
                while (ret< _end)
                {
                    *(ret - 1) = *ret;
                    ++ret;
                }
                --_end;
                return pos;
            }

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

其中實(shí)現(xiàn)過程中最容易錯誤的就是insert以及erase擴(kuò)容問題，這是最容易出錯的。

擴(kuò)容是防止淺拷貝，所有把利用賦值來實(shí)現(xiàn)深拷貝。insert以及erase要注意更新迭代器，防止迭代器失效。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁題目：C++vector-創(chuàng)新互聯(lián)
網(wǎng)站路徑：http://m.rwnh.cn/article6/dddpog.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供建站公司、網(wǎng)站排名、營銷型網(wǎng)站建設(shè)、Google、云服務(wù)器、網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)