目錄
目前成都創(chuàng)新互聯(lián)已為近千家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)頁(yè)空間、網(wǎng)站改版維護(hù)、企業(yè)網(wǎng)站設(shè)計(jì)、華龍網(wǎng)站維護(hù)等服務(wù),公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略,正道將秉承"和諧、參與、激情"的文化,與客戶和合作伙伴齊心協(xié)力一起成長(zhǎng),共同發(fā)展。1.vector的介紹及使用 ?
1.1 vector的介紹
1.2 vector的使用
1.2.1 vector的定義
1.2.2 vector iterator 的使用
1.2.3 vector 空間增長(zhǎng)問(wèn)題
1.2.3 vector 增刪查改
1.2.4 vector 迭代器失效問(wèn)題。(重點(diǎn))
1.2.5 vector 在OJ中的使用
2.vector深度剖析及模擬實(shí)現(xiàn)
使用memcpy拷貝問(wèn)題
動(dòng)態(tài)二維數(shù)組理解
模擬實(shí)現(xiàn)vector:
1. vector 是表示可變大小數(shù)組的序列容器。 2. 就像數(shù)組一樣, vector 也采用的連續(xù)存儲(chǔ)空間來(lái)存儲(chǔ)元素。也就是意味著可以采用下標(biāo)對(duì) vector 的元素進(jìn)行訪問(wèn),和數(shù)組一樣高效。但是又不像數(shù)組,它的大小是可以動(dòng)態(tài)改變的,而且它的大小會(huì)被容器自動(dòng)處理。 3. 本質(zhì)講, vector 使用動(dòng)態(tài)分配數(shù)組來(lái)存儲(chǔ)它的元素。當(dāng)新元素插入時(shí)候,這個(gè)數(shù)組需要被重新分配大小為了增加存儲(chǔ)空間。其做法是,分配一個(gè)新的數(shù)組,然后將全部元素移到這個(gè)數(shù)組。就時(shí)間而言,這是一個(gè)相對(duì)代價(jià)高的任務(wù),因?yàn)槊慨?dāng)一個(gè)新的元素加入到容器的時(shí)候,vector 并不會(huì)每次都重新分配大小。 4. vector 分配空間策略: vector 會(huì)分配一些額外的空間以適應(yīng)可能的增長(zhǎng),因?yàn)榇鎯?chǔ)空間比實(shí)際需要的存儲(chǔ)空間更大。不同的庫(kù)采用不同的策略權(quán)衡空間的使用和重新分配。但是無(wú)論如何,重新分配都應(yīng)該是對(duì)數(shù)增長(zhǎng)的間隔大小,以至于在末尾插入一個(gè)元素的時(shí)候是在常數(shù)時(shí)間的復(fù)雜度完成的。 5. 因此, vector 占用了更多的存儲(chǔ)空間,為了獲得管理存儲(chǔ)空間的能力,并且以一種有效的方式動(dòng)態(tài)增長(zhǎng)。 6. 與其它動(dòng)態(tài)序列容器相比( deque, list and forward_list ), vector 在訪問(wèn)元素的時(shí)候更加高效,在末尾添加和刪除元素相對(duì)高效。對(duì)于其它不在末尾的刪除和插入操作,效率更低。比起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 的使用1.2.3 vector 空間增長(zhǎng)問(wèn)題我們可以看到這里的iterator行為上就像指針一樣,但又不一定是指針?,而對(duì)于vector這里來(lái)說(shuō),這里的iterator就是一個(gè)原生指針,后面會(huì)講到迭代器失效的問(wèn)題。
這里的resize和reserve和之前的string的含義一樣,這里就看看函數(shù)的使用方式即可:
capacity 的代碼在 vs 和 g++ 下分別運(yùn)行會(huì)發(fā)現(xiàn), vs下capacity是按1.5倍增長(zhǎng)的,g++是按2倍增長(zhǎng)的。 這個(gè)問(wèn)題經(jīng)常會(huì)考察,不要固化的認(rèn)為, vector 增容都是 2 倍,具體增長(zhǎng)多少是根據(jù)具體的需求定義的。 vs是PJ版本STL,g++是SGI版本STL 。( 也就是不同編譯器的實(shí)現(xiàn)方式不同,所以可能會(huì)導(dǎo)致有不同的結(jié)果) reserve 只負(fù)責(zé)開(kāi)辟空間,如果確定知道需要用多少空間, reserve 可以緩解 vector 增容的代價(jià)缺陷問(wèn)題。 resize 在開(kāi)空間的同時(shí)還會(huì)進(jìn)行初始化,影響 size 。
這是vs下的擴(kuò)容:
reserve的優(yōu)勢(shì)就在于如果我們知道要開(kāi)多少空間,我們就可以一次性開(kāi)好,就可以避免頻繁的擴(kuò)容,因?yàn)槲覀冎李l繁擴(kuò)容是要付出代價(jià)的,所以C++在這方面做的很好。
1.2.3 vector 增刪查改為什么不推薦使用insert以及erase呢?因?yàn)槲覀冎罃?shù)組刪除數(shù)據(jù)是要挪動(dòng)數(shù)據(jù)的,這樣就導(dǎo)致花費(fèi)更多時(shí)間,所以一般情況下不推薦使用。
上述內(nèi)容很簡(jiǎn)單,查網(wǎng)站就會(huì)使用,不過(guò)多講解,下面主要講解迭代器失效的問(wèn)題;
1.2.4 vector 迭代器失效問(wèn)題。(重點(diǎn))迭代器的主要作用就是讓算法能夠不用關(guān)心底層數(shù)據(jù)結(jié)構(gòu),其底層實(shí)際就是一個(gè)指針,或者是對(duì)指針進(jìn)行了封裝,比如:vector的迭代器就是原生態(tài)指針T* 。因此迭代器失效,實(shí)際就是迭代器底層對(duì)應(yīng)指針?biāo)赶虻目臻g被銷毀了,而使用一塊已經(jīng)被釋放的空間,造成的后果是程序崩潰(即如果繼續(xù)使用已經(jīng)失效的迭代器,程序可能會(huì)崩潰)。 為什么會(huì)這樣呢? 下面我們看幾個(gè)例子:1. 會(huì)引起其底層空間改變的操作,都有可能是迭代器失效 ,比如: resize 、 reserve 、 insert 、 assign 、push_back等。 拿擴(kuò)容來(lái)說(shuō),reserve的底層實(shí)現(xiàn)是講原來(lái)的空間釋放掉,然后開(kāi)辟新的空間,這樣迭代器所在的位置就發(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ò)容過(guò),所以迭代器肯定失效
while (it != v.end())
{
cout<< *it<< " ";
++it;
}
cout<< endl;
return 0;
}
結(jié)果正如我們所料:
解決這個(gè)辦法就是更新一下迭代器即可正常使用。
看看其他例子:
2. 指定位置元素的刪除操作--eraseint 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; // 此處會(huì)導(dǎo)致非法訪問(wèn)
return 0;
}
erase
刪除
pos
位置元素后,
pos
位置之后的元素會(huì)往前搬移,
沒(méi)有導(dǎo)致底層空間的改變,理論上講迭代器不應(yīng)該會(huì)失效
,但是:
如果pos剛好是最后一個(gè)元素,刪完之后pos剛好是end的位置,而end位置是沒(méi)有元素的,那么pos就失效了。因此刪除vector中任意位置上元素時(shí),vs就認(rèn)為該位置迭代器失效了。
我們可以看到
vs實(shí)現(xiàn)的方式是比較嚴(yán)格的
,如果不更新迭代器這就無(wú)法使用了。后面我們會(huì)模擬實(shí)現(xiàn)vector,后面我們模擬實(shí)現(xiàn)的就可以使用。
如果要
刪除vector中所有的偶數(shù),我們應(yīng)該怎么做呢?
下面這樣就是有問(wèn)題的:
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)這里肯定是有問(wèn)題的,因?yàn)閯h除完4之后it又++就已經(jīng)越界訪問(wèn)了。
我們可以在不是偶數(shù)的時(shí)候再++,同時(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++編譯器就沒(méi)有檢查的那么嚴(yán)格:
看看擴(kuò)容這段代碼:
// 1. 擴(kuò)容之后,迭代器已經(jīng)失效了,程序雖然可以運(yùn)行,但是運(yùn)行結(jié)果已經(jīng)不對(duì)了
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;
// 通過(guò)reserve將底層空間設(shè)置為100,目的是為了讓vector的迭代器失效
v.reserve(100);
cout<< "擴(kuò)容之后,vector的容量為: "<< v.capacity()<< endl;
// 經(jīng)過(guò)上述reserve之后,it迭代器肯定會(huì)失效,在vs下程序就直接崩潰了,但是linux下不會(huì)
// 雖然可能運(yùn)行,但是輸出的結(jié)果是不對(duì)的
while (it != v.end())
{
cout<< *it<< " ";
++it;
}
cout<< endl;
return 0;
}
可以看到Linux底下是沒(méi)有報(bào)錯(cuò)的,因?yàn)榭臻g還是原來(lái)的空間,后序元素往前搬移了,it的位置還是有效的,但是對(duì)于剛剛那個(gè)偶數(shù)那題Linux下也會(huì)報(bào)錯(cuò):
4. 與vector類似,string在插入+擴(kuò)容操作+erase之后,迭代器也會(huì)失效
最后說(shuō)說(shuō)如何解決這類問(wèn)題:
迭代器失效解決辦法:在使用前,對(duì)迭代器重新賦值即可 1.2.5 vector 在OJ中的使用1. 力扣因?yàn)閿?shù)組在實(shí)際的應(yīng)用非常廣泛,所以C++的vector的運(yùn)用也是非常多,而且嵌套vector遠(yuǎn)遠(yuǎn)比C語(yǔ)言中的二維數(shù)組好用,下面我們就來(lái)看看vector在oj中的應(yīng)用:
這題楊輝三角實(shí)現(xiàn)起來(lái)其實(shí)并不是很難,但是如果使用C語(yǔ)言來(lái)做就很難受了,因?yàn)殚_(kāi)辟空間那里就會(huì)讓你非常頭疼,但是對(duì)于C++來(lái)說(shuō)這又不是一件難事了。這里就體現(xiàn)了嵌套vector的優(yōu)點(diǎn)了。 思路: 先開(kāi)辟好一個(gè)vector實(shí)現(xiàn)方式:>,這樣相當(dāng)于C語(yǔ)言中的二維數(shù)組了。然后調(diào)整好空間,在第一行以及對(duì)角線的那一行初始化為1,其他的初始化為0,然后我們就可以遍歷這個(gè)嵌套vector,判斷是否0的元素,是就讓其加上上一行的前一個(gè)以及上一行的那個(gè)。
class Solution {
public:
vector>generate(int numRows) {
//先開(kāi)辟空間
vector>vv;
vv.resize(numRows);
for(size_t i= 0 ;i
2.力扣
這道題如果使用哈希表的話就超出了這個(gè)空間復(fù)雜度了,用暴力查找的方式又不符合題意,這里有一個(gè)思路非常巧妙:
我們可以利用位運(yùn)算來(lái)解決,因?yàn)檫@個(gè)除了這個(gè)數(shù)字其他的數(shù)字都出現(xiàn)過(guò)3次,我們可以把數(shù)組中的每一個(gè)數(shù)字的二進(jìn)制位加起來(lái),然后讓結(jié)果%3就可以得到我們所想要的二進(jìn)制位了,(不論是0還是1,%3的結(jié)果都是我們想要的那個(gè)數(shù)的二進(jìn)制位),最后我們用ret每次接受一下要的到二進(jìn)制位,就可以得到答案。
代碼實(shí)現(xiàn):
class Solution {
public:
int singleNumber(vector& nums) {
//我們可以把所有的二進(jìn)制位全部加起來(lái),然后%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)制位找出來(lái)
if(sum%3)
{
ret |= (1<
3.數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)字_??皖}霸_牛客網(wǎng)
思路:因?yàn)樗霈F(xiàn)的元素的個(gè)數(shù)超過(guò)了一般半,我們就可以通過(guò)計(jì)數(shù)的方式記錄它,如果是這個(gè)元素就++,不是就--,最后得到的那個(gè)數(shù)一定是我們想要的數(shù),另外,我們還可以拓展一下:如果這個(gè)數(shù)不一定存在那要怎么處理?
我們可以對(duì)這個(gè)記錄一下這個(gè)數(shù),然后再遍歷一次數(shù)組,通過(guò)計(jì)數(shù)的方式去確認(rèn)是否存在。
代碼實(shí)現(xiàn):
class Solution {
public:
int MoreThanHalfNum_Solution(vectornumbers) {
//因?yàn)樗霈F(xiàn)的元素的個(gè)數(shù)超過(guò)了一般半,我們就可以通過(guò)計(jì)數(shù)的方式記錄它,如果是這個(gè)元素就++,不是就--
//這樣的話就可以在最后的時(shí)候找到這個(gè)元素
int tmp = numbers[0];//記錄我們要求的數(shù)據(jù)
int times = 1;
for(int i = 1;i
4.力扣
這一題的難度比較大,運(yùn)用到了回溯算法
思路:
我們可以通過(guò)一個(gè)數(shù)組來(lái)記錄數(shù)字與字母之間的映射關(guān)系,然后利用回溯算法(遞歸)就解決像這種組合問(wèn)題,下面通過(guò)這題來(lái)大概講解一下回溯:
這個(gè)很像二叉樹(shù)的遍歷,但又復(fù)雜一點(diǎn),這個(gè)可以看成多叉樹(shù)的遍歷方式。我們可以通過(guò)每一層的遞歸來(lái)達(dá)到一個(gè)組合的效果。
代碼實(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;
}
//找到對(duì)應(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;//用來(lái)每次加,然后最后加到vcombine中
//遞歸
combine(digits,i,vcombine,retstr);
return vcombine;
}
};
下面通過(guò)畫遞歸展開(kāi)圖再來(lái)看看其中的細(xì)節(jié):
1. memcpy是內(nèi)存的二進(jìn)制格式拷貝,將一段內(nèi)存空間中內(nèi)容原封不動(dòng)的拷貝到另外一段內(nèi)存空間中 2. 如果拷貝的是自定義類型的元素, memcpy 既高效又不會(huì)出錯(cuò),但 如果拷貝的是自定義類型元素,并且自定義類型元素中涉及到資源管理時(shí),就會(huì)出錯(cuò),因?yàn)閙emcpy的拷貝實(shí)際是淺拷貝。
這個(gè)和之前講拷貝構(gòu)造的時(shí)候很像,都是淺拷貝導(dǎo)致的問(wèn)題。?可能會(huì)引起內(nèi)存泄漏甚至程序崩潰。
動(dòng)態(tài)二維數(shù)組理解模擬實(shí)現(xiàn)vector:在前面就已經(jīng)看過(guò)了二維數(shù)組的題了,這里不過(guò)多介紹,還是介紹一下memcpy也會(huì)使內(nèi)存崩潰的結(jié)果:
要解決這個(gè)問(wèn)題,我們還是要進(jìn)行深拷貝,這是下面的reserve的模擬實(shí)現(xiàn)代碼來(lái)解決這個(gè)問(wèn)題:
我們可以通過(guò)這個(gè)一個(gè)對(duì)象賦值的方式來(lái)進(jìn)行深拷貝
templateclass vector
{
public:
// Vector的迭代器是一個(gè)原生指針
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)
{
//找個(gè)工具人
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)
{
//堅(jiān)持不縮容
if (n >capacity())
{
//開(kāi)辟新的空間,然后賦值過(guò)去
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ò)容不處理會(huì)導(dǎo)致迭代器失效
pos = _start + distance;
}
//挪動(dòng)數(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);
//挪動(dòng)數(shù)據(jù)
iterator ret = pos + 1;
while (ret< _end)
{
*(ret - 1) = *ret;
++ret;
}
--_end;
return pos;
}
private:
iterator _start; // 指向數(shù)據(jù)塊的開(kāi)始
iterator _end; // 指向有效數(shù)據(jù)的尾
iterator _endOfStorage; // 指向存儲(chǔ)容量的尾
};
其中實(shí)現(xiàn)過(guò)程中最容易錯(cuò)誤的就是insert以及erase擴(kuò)容問(wèn)題,這是最容易出錯(cuò)的。
擴(kuò)容是防止淺拷貝,所有把利用賦值來(lái)實(shí)現(xiàn)深拷貝。insert以及erase要注意更新迭代器,防止迭代器失效。
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商?創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源,準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性,企業(yè)級(jí)服務(wù)器適合批量采購(gòu),新人活動(dòng)首月15元起,快前往官網(wǎng)查看詳情吧
網(wǎng)頁(yè)題目:C++vector-創(chuàng)新互聯(lián)
網(wǎng)站路徑:http://aaarwkj.com/article6/dddpog.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供建站公司、網(wǎng)站排名、營(yíng)銷型網(wǎng)站建設(shè)、Google、云服務(wù)器、網(wǎng)站制作
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來(lái)源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容