文章目錄

• 順序容器
• • vector(向量容器)
  • deque(雙端隊列)
  • list
• 關(guān)聯(lián)容器
• • set（集合）
  • multiset
  • map（key,value）
  • multimap

順序容器

vector(向量容器)

• 特點
• 內(nèi)存可2倍增長的動態(tài)數(shù)組
• 數(shù)據(jù)結(jié)構(gòu)：線性連續(xù)空間
• 維護(hù)三個迭代器：start、finish、end_of_storage
  

注意：動態(tài)增加大小，并不是在原空間之后接續(xù)新空間（因為無法保證之后尚有可供分配的空間），而是每次再分配原大小兩倍的內(nèi)存空間。因此，對vector的任何操作，一旦引起空間重新配置，指向原vector的所有迭代器就都失效了。

• 成員函數(shù)

函數(shù)作用

assign(first,last)	用迭代器first,last所指定的元素取代容器中的元素
assign(num,val)	用val的num份副本取代2元素
at(n)	等價于[]運算符，返回容器中位置n的元素
front()	返回容器中第一個元素的引用
back()	返回容器中最后一個元素的引用
begin()	返回容器中第一個元素的迭代器
end()	返回容器中最后一個元素的下一個迭代器(不可解引用)
max_size()	返回容器類型的最大容量（2^30-1=0x3FFFFFFF）
capacity()	返回容器當(dāng)前開辟的空間大小
size()	返回容器中現(xiàn)有元素的個數(shù)（<=capacity）
clear()	清空容器中所有元素
empty()	如果容器為空，返回真
erase(start,end)	刪除迭代器[start ,end)所指定范圍內(nèi)的元素
erase(i)	刪除迭代器i所指向的元素,返回指向刪除元素下一位置的迭代器
insert(i,x)	把x插入到迭代器i所指定的位置之前
insert(i,n,x)	把x的n份副本插入到迭代器i所指定的位置之前
insert(i,start,end)	在i位置插入在[start,end)區(qū)間的數(shù)據(jù),無返回值。
push_back(x)	尾插
op_back()	刪除容器最后一個元素
rbegin()	返回一個反向迭代器，該迭代器指向的元素越過了容器中的最后一個元素
rend()	返回一個反向迭代器，該迭代器指向容器中第一個元素
reverse()	反轉(zhuǎn)元素順序
resize(n,x)	把容器的大小改為n,新元素的初值賦為x
swap(vector1)	交換2個容器的內(nèi)容

deque(雙端隊列)

• 特點

• 數(shù)據(jù)結(jié)構(gòu)：一種雙向開口的存儲空間分段連續(xù)的數(shù)據(jù)結(jié)構(gòu)，每段數(shù)據(jù)空間內(nèi)部是連續(xù)的，而每段數(shù)據(jù)空間之間則不一定連續(xù)

• deque與vector的最大差異 :
  1.允許常數(shù)時間內(nèi)對起首端進(jìn)行元素的插入和刪除
  2.deque沒有所謂的容量概念，因為它是以分段連續(xù)空間組合而成，隨時可以增加一段新的空間并連接起來
  
  上圖deque有四部分?jǐn)?shù)據(jù)空間，這些空間都是程序運行過程中在堆上動態(tài)分配的。
  中控器（map）保存著一組指針，每個指針指向一段數(shù)據(jù)空間的起始位置，通過中控器可以找到所有的數(shù)據(jù)空間。如果中控器的數(shù)據(jù)空間滿了，會重新申請一塊更大的空間，并將中控器的所有指針拷貝到新空間中。

• deque采用一塊所謂的map（注意，不是STL的map容器）作為主控。這里所謂map是一小塊連續(xù)空間，其中每個元素（此處稱為一個節(jié)點，node）都是指針，指向另一段（較大的）連續(xù)線性空間，稱為緩沖區(qū)。緩沖區(qū)才是deque的儲存空間主體
  

• deque 的迭代器

deque的迭代器由四個屬性組成，這四個屬性是我們隨機(jī)訪問一個容器內(nèi)元素的必要成分。

1.node用于指向的“第一維”的某個位置，該位置對應(yīng)要訪問元素的入口地址
2.剩下的三個屬性則用于“第二維”，[first,last)規(guī)定了訪問本區(qū)間元素的邊界條件，而curr則指向?qū)嶋H我們要訪問的元素。

1.start迭代器:綁定到第一個有效的map結(jié)點和該結(jié)點對應(yīng)的緩沖區(qū)。

2.finish迭代器:綁定到最后一個有效的map結(jié)點和該結(jié)點對應(yīng)的緩沖區(qū)。

舉例：
假設(shè)deque中存儲20個元素，每個緩沖區(qū)大小為8，則需要20/8=3個緩沖區(qū)，所以map中會運用3個節(jié)點。deque的begin()和end()始終會返回map中節(jié)點的頭和尾，名為start和finish，其中，start的cur指向第一個緩沖區(qū)中的首元素，finish的cur指向最后一個緩沖區(qū)的最后一個元素的下一位置。

• deque緩沖區(qū)擴(kuò)充

注意：從上圖來看，如果無窮盡的向deque中存儲數(shù)據(jù)，map所含有的緩沖區(qū)也會填滿的。也就是說，當(dāng)map的前端節(jié)點或后端節(jié)點備用空間不足時，map也需要重新配置，依然是經(jīng)過三個步驟：配置更大的、拷貝原來的、釋放原空間。

• 成員函數(shù)

函數(shù)作用

c.assign(beg,end)	將[beg; end)區(qū)間中的數(shù)據(jù)賦值給c。
c.assign(n,elem)	將n個elem的拷貝賦值給c。
c.at(idx)	傳回索引idx所指的數(shù)據(jù)，如果idx越界，拋出out_of_range。
c.back()	返回最后一個數(shù)據(jù)，不檢查這個數(shù)據(jù)是否存在。
c.begin()	返回迭代器的第一個數(shù)據(jù)。
c.clear()	移除容器中所有數(shù)據(jù)。
deque	創(chuàng)建一個空的deque。
deque c1(c2)	c復(fù)制一個deque。
deque c(n)	創(chuàng)建一個deque，含有n個數(shù)據(jù)，數(shù)據(jù)均已缺省構(gòu)造產(chǎn)生。
deque c(n, elem)	創(chuàng)建一個含有n個elem拷貝的deque。
deque c(beg,end)	創(chuàng)建一個以[beg;end)區(qū)間的deque。
c.~deque()	銷毀所有數(shù)據(jù)，釋放內(nèi)存。
c.empty()	判斷容器是否為空。
c.end()	指向迭代器中的最后一個數(shù)據(jù)地址。
c.erase(pos)	刪除pos位置的數(shù)據(jù)，返回下一個數(shù)據(jù)的位置。
c.erase(beg,end)	刪除[beg,end)區(qū)間的數(shù)據(jù)，返回下一個數(shù)據(jù)的位置。
c.front()	返回容器的第一個元素。
get_allocator	使用構(gòu)造函數(shù)返回一個拷貝。
c.insert(pos,elem)	在pos位置插入一個elem拷貝，傳回新數(shù)據(jù)位置。
c.insert(pos,n,elem)	在pos位置插入>n個elem數(shù)據(jù)。無返回值。
c.insert(pos,beg,end)	在pos位置插入在[beg,end)區(qū)間的數(shù)據(jù)。無返回值。
c.max_size()	返回容器中最大數(shù)據(jù)的數(shù)量。
c.pop_back()	刪除最后一個數(shù)據(jù)。
c.pop_front()	刪除頭部數(shù)據(jù)。
c.push_back(elem)	在尾部加入一個數(shù)據(jù)。
c.push_front(elem)	在頭部插入一個數(shù)據(jù)。
c.rbegin()	傳回一個反向隊列的第一個數(shù)據(jù)。
c.rend()	傳回一個反向隊列的最后一個數(shù)據(jù)的下一個位置。
c.resize(num)	重新指定隊列的長度。
c.size()	返回容器中實際數(shù)據(jù)的個數(shù)。
c1.swap(c2)	將c1和c2元素互換
swap(c1,c2)	將c1和c2元素互換。

list

• 特點

• 有效利用空間

• 數(shù)據(jù)結(jié)構(gòu)：環(huán)狀雙向鏈表

• 插入(insert)和接合(splice)操作都不會造成原來list的迭代器失效

• 刪除（erase）操作僅僅使“指向被刪除元素”的迭代器失效，其它迭代器不受影響

• 隨機(jī)訪問比較慢

插入一個結(jié)點

• 成員函數(shù)

函數(shù)作用

assign()	給list賦值
back()	返回最后一個元素
begin()	返回指向第一個元素的迭代器
clear()	刪除所有元素
empty()	如果list是空的則返回true
end()	返回末尾的迭代器
erase()	刪除一個元素
front()	返回第一個元素
get_allocator()	返回list的配置器
insert()	插入一個元素到list中
max_size(）	返回list能容納的最大元素數(shù)量
merge()	合并兩個list
pop_back()	刪除最后一個元素
pop_front()	刪除第一個元素
push_back()	在list的末尾添加一個元素
push_front()	在list的頭部添加一個元素
rbegin()	返回指向第一個元素的逆向迭代器
remove()	從list刪除元素
remove_if()	按指定條件刪除元素
rend()	指向list末尾的逆向迭代器
resize()	改變list的大小
reverse()	把list的元素逆序
size()	返回list中的元素個數(shù)
sort()	給list排序
splice()	合并兩個list
swap()	交換兩個list
unique()	刪除list中重復(fù)的元素

關(guān)聯(lián)容器

set（集合）

• 特點
• 數(shù)據(jù)結(jié)構(gòu)：底層使用平衡的搜索樹——紅黑樹實現(xiàn)
  
• 插入刪除操作時僅僅需要指針操作節(jié)點即可完成，不涉及到內(nèi)存移動和拷貝
• set中元素都是唯一的，而且默認(rèn)情況下會對元素自動進(jìn)行升序排列
• 支持集合的交(set_intersection),差(set_difference) 并(set_union)，對稱差 (set_symmetric_difference) 等一些集合上的操作

• 成員函數(shù)

函數(shù)作用

begin()	返回容器的第一個迭代器
end()	返回容器的最后元素的下一個迭代器
clear()	刪除容器中的所有元素
empty()	判斷容器是否為空
insert()	插入一個元素
erase()	刪除一個元素
size()	返回當(dāng)前容器的元素個數(shù)
rbegin()	返回尾元素的逆向迭代器指針
reverse_iterator rend()	返回首元素前一個位置的迭代器指針
find()	查找一個元素，不存在返回s.end()
lower_bound()	返回第一個大于或等于給定關(guān)鍵值的元素
upper_bound()	返回第一個大于給定關(guān)鍵值的元素
swap()	交換兩個集合元素

注意：

• set內(nèi)部元素也是以鍵值對的方式存儲的，只不過它的鍵值與實值相同
• set中不允許存放兩個實值相同的元素
• 迭代器是被定義成const iterator的，說明set的鍵值是不允許更改的，并且不允許通過迭代器進(jìn)行修改set里面的值

multiset

• 特點
• 數(shù)據(jù)結(jié)構(gòu)：底層實現(xiàn)與set一樣，也采用了紅黑樹
• 允許插入重復(fù)的鍵值，使用insert_equal機(jī)制
• 插入、刪除操作的時間復(fù)雜度為O(log2n)
  
• 成員函數(shù)用法同set

map（key,value）

• 特點

• map中key的值是唯一的

• 數(shù)據(jù)結(jié)構(gòu)：紅黑樹變體的平衡二叉樹數(shù)據(jù)結(jié)構(gòu)

• 提供基于key的快速檢索能力

• 元素插入是按照排序規(guī)則插入的，不能指定位置插入

• 對于迭代器來說，可以修改實值，而不能修改key。

• 根據(jù)key值快速查找,查找的復(fù)雜度基本是log2n

• 成員函數(shù)

函數(shù)作用

begin()	返回指向map頭部的迭代器
clear()	刪除所有的元素
count()	返回指定元素出現(xiàn)的次數(shù)
empty()	判斷容器是否為空
end()	返回指向map末尾的迭代器
get_allocator()	返回map的配置器
insert()	添加元素
lower_bound()	返回鍵值>=給定元素的第一個位置
upper_bound()	返回>給定元素的第一個元素
max_size()	返回可以容納的最大元素個數(shù)
rbegin()	返回一個指向map尾部的逆向迭代器
rend()	返回一個指向map頭部的逆向迭代器
find(k)	返回指向第一個與鍵 k 匹配的 pair 的迭代指針，沒找到返回指向map尾部的迭代器
erase()	刪除迭代器所指向的元素
swap()	兩個容器交換
size()	返回map中元素的個數(shù)

注意：
map在進(jìn)行插入的時候是不允許有重復(fù)的鍵值的，如果新插入的鍵值與原有的鍵值重復(fù)則插入無效，可以通過insert的返回的pair中第二個bool型變量來判斷是否插入成功來判斷是否成功插入.

pair<iterator, bool> insert(const value_type& x)

• 1

舉例：

#include<iostream> #include<map> using namespace std; int main() {map<int, int> m;m.insert(pair<int, int>(1, 10));pair<map<int, int>::iterator, bool> ret;ret = m.insert(pair<int, int>(1, 20));if (ret.second){cout << "成功" << endl;}else{cout << "失敗" << endl;}

multimap

• 特點
• 與 map 不同，multimap 可以包含重復(fù)鍵

比如：

1.在電話簿中相同的人可以有兩個以上電話號碼 2.文件系統(tǒng)中可以將多個符號鏈接映射到相同的物理文件 3.DNS服務(wù)器可以將幾個URL映射到相同的IP地址

• 成員函數(shù)

函數(shù)作用

begin()	返回指向第一個元素的迭代器
clear()	刪除所有元素
count()	返回一個元素出現(xiàn)的次數(shù)
empty()	如果multimap為空則返回真
end()	返回一個指向multimap末尾的迭代器
equal_range(k)	該函數(shù)查找所有與 k 關(guān)聯(lián)的值。返回迭代指針的 pair，它標(biāo)記開始和結(jié)束范圍
erase()	刪除元素
find()	查找元素
get_allocator()	返回multimap的配置器
insert()	插入元素
key_comp()	返回比較key的函數(shù)
lower_bound()	返回鍵值>=給定元素的第一個位置
max_size()	返回可以容納的最大元素個數(shù)
rbegin()	返回一個指向mulitmap尾部的逆向迭代器
rend()	返回一個指向multimap頭部的逆向迭代器
size()	返回multimap中元素的個數(shù)
swap()	交換兩個multimaps
upper_bound()	返回鍵值>給定元素的第一個位置
value_comp()	返回比較元素value的函數(shù)

equal_range()函數(shù)應(yīng)用舉例：

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

int main()
{
multimap<int, int> m;
m.insert(pair<int,int>(1, 10));
m.insert(pair<int, int>(1, 20));
m.insert(pair<int, int>(1, 30));
m.insert(pair<int, int>(2, 21));
m.insert(pair<int, int>(2, 22));
m.insert(pair<int, int>(3, 31));
m.insert(pair<int, int>(3, 32));

注意:

multimap::insert() 和 map::insert() 的返回值不同。

multimap::insert():返回指向新插入元素的迭代器（multimap::insert()總是能執(zhí)行成功）

map::insert() :返回 pair<iterator, bool>，此處 bool 值表示插入操作是否成功。

總結(jié)

以上是生活随笔為你收集整理的【c++】22. STL容器的底层实现详解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。