C++容器底層數據結構介紹

這篇文章主要介紹“C++容器底層數據結構介紹”，在日常操作中，相信很多人在C++容器底層數據結構介紹問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”C++容器底層數據結構介紹”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

內置數組：

int arr[10][10];
memset(arr,0,10*10*sizeof(int)); //初始化
int tmp[10][10];
memcpy(arr, tmp, 10 * 10 * sizeof(int));//拷貝

void *memcpy(void *destin, void *source, unsigned n); //源*目的內存覆蓋問題

memcpy 函數用于 把資源內存（src所指向的內存區域） 拷貝到目標內存（dest所指向的內存區域）；拷貝多少個？有一個size變量控制拷貝的字節數；

序列容器：array、vector 、deque、 list 、 forward_list

array<T,N> (數組容器) ：基于數組，長度固定的序列，有 N 個 T 類型的對象。

vector<T> (向量容器)  ：基于數組，長度可變的序列，用來存放T類型的對象，預留分配大一些的一段連續空間，當超出時會二次分配更大的拷貝過去。

deque<T> (雙端隊列容器) ：長度可變序列，用來存放T類型的對象，在序列的兩端都能高效地增加或刪除元素，由一段一段的定量連續空間構成，下標訪問必須進行二次指針解引用，與之相比 vector 的下標訪問只進行一次，只保有一個元素的 deque 必須分配其整個內部數組（例如 64 位 libstdc++ 上為對象大小 8 倍； 64 位 libc++ 上為對象大小 16 倍或 4096 字節的較大者）。

list<T> (鏈表容器) ：長度可變的、由 T 類型對象組成的序列，它以雙向鏈表的形式組織元素，在這個序列的任何地方都可以高效地增加或刪除元素。訪問容器中任意元素的速度要比前三種容器慢，這是因為 list<T> 必須從第一個元素或最后一個元素開始訪問，需要沿著鏈表移動，直到到達想要的元素。

forward list<T> (正向鏈表容器) ：長度可變的、由 T 類型對象組成的序列，它以單鏈表的形式組織元素，是一類比鏈表容器快、更節省內存的容器，但是它內部的元素只能從第一個元素開始訪問。

string：與vector相似的容器，但專門用于保存字符。隨機訪問快。在尾部插入/刪除速度快。

所有序列容器的函數成員 max_size() 都會返回它能存儲的元素個數的最大值。這通常是一個很大的值，一般是 2^32 -1。

Stack

The standard container classes vector, deque and list fulfill these requirements. By default, if no container class is specified for a particular stack class instantiation, the standard container deque is used. 

默認使用deque而不是vector作為底層容器

set、map、multimap、unordered_set、unordered_map、unordered_multimap的底層數據結構，以及幾種map容器如何選擇？

• set、map、multimap基于紅黑樹，是非嚴格平衡二叉搜索樹，元素有序，且插入、刪除效率高但空間占用率高

• unordered_set、unordered_map、unordered_multimap基于哈希表，元素無序，查找效率高。

• 內存占有率的問題就轉化成紅黑樹 VS hash表 , 還是unorder_map占用的內存要高，哈希表的建立比較耗費時間。

map<string,vector<int> > empty_map1; map1.swap(empty_map1); map1.clear(); 或 StrategyMap().swap(_stg_flows);

map.clear()只是把map清空了，但是內存沒有釋放，如果要釋放內存不止是要clear()掉，還要和一個空的map來進行swap，將內存釋放。

注意map中如果元素不是基本類型，也要進行內存釋放，如指針，vector要尤其注意，否則map占的內存太大，會造成程序崩潰。

vector

array： 固定長度的數組,使用棧（靜態內存分配），因此效率與數組相同。

1. 使用fill方法實現了數據填充。

2. 使用size方法取得數組的大小。

3. 雖然at(i)方法實現帶有越界檢查的讀寫。

寫入速度的比較結果：內置數組的速度最快，vector容器次之，array容器最慢???

拷貝速度：https://blog.csdn.net/qq_35976351/article/details/82940121

拷貝：/* 未開優化： array=466ms vector=7923ms memcpy=198ms */ /* -O3優化，最高速度： array=0ms vector=453ms memcpy=0ms */

迭代器iterator

在STL中，使用迭代器（內置類型 iterator）給出數據在表中的位置

• 正向迭代器：containerType::iterator itr;

• 常量正向迭代器（不可更改）：containerType::const_iterator itr;

• 反向迭代器：containerType::reverse_iterator itr;

• 常量反向迭代器：containerType::const_reverse_iterator itr;

常用的需要使用迭代器的容器方法：

• iterator insert(iterator pos, const Object & x)：添加x到表中迭代器pos所指向的位置之前的位置。對1ist是常量時間操作，對vector則不是。返回值是一個指向插入項位置的迭代器

• iterator erase(iterator pos)：刪除迭代器所給出位置的對象。對1ist是常量時間操作，對vector不是。返回值是調用之前pos所指向元素的下一個元素的位置。這個操作使pos失效。pos不再有用，因為它所指向的容器變量已經被刪除了

• iterator erase(iterator start, iterator end)：刪除所有的從位置start開始直到位置end(但是不包括end)的所有元素

到此，關于“C++容器底層數據結構介紹”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！