deque概述

deque屬于順序容器，稱為雙端隊(duì)列容器

底層數(shù)據(jù)結(jié)構(gòu)是動(dòng)態(tài)二維數(shù)組，從整體上看，deque的內(nèi)存不連續(xù)

初始數(shù)組第一維數(shù)量為2，必要時(shí)進(jìn)行2倍擴(kuò)容

每次第一維擴(kuò)容后，原來(lái)數(shù)組第二維元素從新數(shù)組下標(biāo)為OldSize/2的第一維開始存儲(chǔ)

這樣的存儲(chǔ)方式使得前后都預(yù)留相同空間，方便支持deque首尾元素添加

數(shù)組第二維長(zhǎng)度固定

deque相關(guān)操作

// deque相較于vector增加的相關(guān)操作有：push_front()和pop_front()

deque<int> deq;

// 1、添加
deq.push_back(10);
// （1）向末尾添加元素10，時(shí)間復(fù)雜度為O(1)
deq.push_front(20);
// （2）向首部添加元素20，時(shí)間復(fù)雜度為O(1)
deq.insert(it, 30);
// （3）向迭代器it處添加元素30，需要挪動(dòng)元素和更新迭代器，時(shí)間復(fù)雜度為O(n)

// 2、刪除
deq.pop_back();
// （1）刪除末尾元素，時(shí)間復(fù)雜度為O(1)
deq.pop_front();
// （2）刪除首部元素，時(shí)間復(fù)雜度為O(1)
deq.erase(it);
// （3）刪除迭代器it處元素，需要挪動(dòng)元素和更新迭代器，時(shí)間復(fù)雜度為O(n)

// 3、查詢
// （1）使用迭代器遍歷

辨析vector和deque

1、底層數(shù)據(jù)結(jié)構(gòu)不同

vector底層是動(dòng)態(tài)一維數(shù)組；

deque底層是動(dòng)態(tài)二維數(shù)組

2、添加刪除元素的時(shí)間復(fù)雜度不同

首部添加刪除操作頻繁，選擇deque

3、內(nèi)存使用效率不同

vector需要連續(xù)內(nèi)存空間，內(nèi)存使用效率低；

deque分塊存儲(chǔ)數(shù)據(jù)，不要求內(nèi)存空間連續(xù)，內(nèi)存使用效率高

4、在中間位置添加刪除的效率不同

vector效率更高，deque效率更低

因?yàn)関ector使用連續(xù)內(nèi)存空間，方便挪動(dòng)元素

而deque的內(nèi)存空間不連續(xù)，不便挪動(dòng)元素

list概述

list屬于順序容器，稱為鏈表容器

底層數(shù)據(jù)結(jié)構(gòu)是雙向循環(huán)鏈表

list相關(guān)操作

// list相較于vector增加的相關(guān)操作有：push_front()和pop_front()

list<int> mylist;

// 1、添加
mylist.push_back(10);
// （1）向末尾添加元素10，時(shí)間復(fù)雜度為O(1)
mylist.push_front(20);
// （2）向首部添加元素20，時(shí)間復(fù)雜度為O(1)
mylist.insert(it, 30);
// （3）向迭代器it處添加元素30，需要更新迭代器，時(shí)間復(fù)雜度為O(1)
// 鏈表進(jìn)行insert前，需要進(jìn)行query查詢
// 對(duì)于鏈表來(lái)說(shuō)，query查詢效率低

// 2、刪除
mylist.pop_back();
// （1）刪除末尾元素，時(shí)間復(fù)雜度為O(1)
mylist.pop_front();
// （2）刪除首部元素，時(shí)間復(fù)雜度為O(1)
mylist.erase(it);
// （3）刪除迭代器it處元素，需要更新迭代器，時(shí)間復(fù)雜度為O(1)

// 3、查詢
// （1）使用迭代器遍歷

辨析vector和list

1、底層數(shù)據(jù)結(jié)構(gòu)不同

vector底層是動(dòng)態(tài)一維數(shù)組；

list底層是雙向循環(huán)鏈表

2、時(shí)間復(fù)雜度不同

vector：增加刪除O(n)、查詢O(n)、隨機(jī)訪問(wèn)O(1)

list：增加刪除O(1)、查詢O(n)

增加刪除操作頻繁，選擇list；

隨機(jī)訪問(wèn)操作頻繁，選擇vector文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-656740.html

到了這里，關(guān)于標(biāo)準(zhǔn)模板庫(kù)STL——deque和list的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！