熱線電話:0755-23712116
郵箱:contact@shuangyi-tech.com
地址:深圳市寶安區(qū)沙井街道后亭茅洲山工業(yè)園工業(yè)大廈全至科技創(chuàng)新園科創(chuàng)大廈2層2A
1.vector數(shù)據(jù)結(jié)構(gòu)
vector和數(shù)組類似,擁有一段連續(xù)的內(nèi)存空間,并且起始地址不變。
因此能高效的進(jìn)行隨機(jī)存取,時間復(fù)雜度為o(1);
但因?yàn)閮?nèi)存空間是連續(xù)的,所以在進(jìn)行插入和刪除操作時,會造成內(nèi)存塊的拷貝,時間復(fù)雜度為o(n)。
另外,當(dāng)數(shù)組中內(nèi)存空間不夠時,會重新申請一塊內(nèi)存空間并進(jìn)行內(nèi)存拷貝。
2.list數(shù)據(jù)結(jié)構(gòu)
list是由雙向鏈表實(shí)現(xiàn)的,因此內(nèi)存空間是不連續(xù)的。
只能通過指針訪問數(shù)據(jù),所以list的隨機(jī)存取非常沒有效率,時間復(fù)雜度為o(n);
但由于鏈表的特點(diǎn),能高效地進(jìn)行插入和刪除。
3.vector和list的區(qū)別
我們看一個簡單的vector和list使用示例:
#include<iostream> #include<vector> #include<list> using namespace std; int main() { vector<int> v; list<int> l; for(int i=0;i<8;i++) ////往v和l中分別添加元素 { v.push_back(i); l.push_back(i); } cout<<"v[2]="<<v[2]<<endl; //cout<<"l[2]="<<l[2]<<endl; //編譯錯誤,list沒有重載[] cout<<(v.begin()<v.end())<<endl; //cout<<(l.begin()<l.end())<<endl; /編譯錯誤,list::iterator沒有重載<或> cout<<*(v.begin()+1)<<endl; //cout<<*(l.begin()+1)<<endl; //編譯錯誤,list::iterator沒有重載+ vector<int>::iterator itv=v.begin(); list<int>::iterator itl=l.begin(); itv = itv+2; //itl=itl+2; //編譯錯誤,list::iterator沒有重載+ itl++; //list::iterator中重載了++,只能使用++進(jìn)行迭代訪問。 itl++; cout<<*itv<<endl; cout<<*itl<<endl; getchar(); return 0; }
vector擁有一段連續(xù)的內(nèi)存空間,能很好的支持隨機(jī)存取,
因此vector<int>::iterator支持“+”,“+=”,“<”等操作符。
list的內(nèi)存空間可以是不連續(xù),它不支持隨機(jī)訪問,
因此list<int>::iterator則不支持“+”、“+=”、“<”等
vector<int>::iterator和list<int>::iterator都重載了“++”運(yùn)算符。
總之,如果需要高效的隨機(jī)存取,而不在乎插入和刪除的效率,使用vector;
如果需要大量的插入和刪除,而不關(guān)心隨機(jī)存取,則應(yīng)使用list。
熱線電話:0755-23712116
郵箱:contact@shuangyi-tech.com
地址:深圳市寶安區(qū)沙井街道后亭茅洲山工業(yè)園工業(yè)大廈全至科技創(chuàng)新園科創(chuàng)大廈2層2A