當前位置：首頁 > 编程语言 > c/c++ >内容正文

c/c++

C++STL与泛型编程（3）容器之分类与测试

發(fā)布時間：2023/12/13 c/c++ 23 豆豆

生活随笔收集整理的這篇文章主要介紹了 C++STL与泛型编程（3）容器之分类与测试小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

文章目錄

容器的分類
序列式容器（sequence containers）代碼示例
- 輔助函數(shù)
- array 容器
- - array容器的測試代碼
  - 測試代碼中部分函數(shù)解析
- vector 容器
- - vector 容器的測試代碼
  - 測試代碼中部分函數(shù)解析
- list 容器
- - list 容器的測試代碼
  - 測試代碼中部分函數(shù)解析
- forward_list 容器
- deque 容器
- - stack 容器
  - queue 容器
關(guān)聯(lián)式容器（Associative Containers）代碼示例
- multiset 容器
- - multiset 容器測試代碼
- multimap 容器
- - multimap 容器測試代碼
- unordered_multiset 容器
- - unordered_multiset 容器測試代碼
- unordered_multimap 容器
- set容器，map容器
- unordered_set 容器
- unordered_map 容器

容器的分類

序列式容器（sequence containers）
- Array
  - 連續(xù)空間，大小不能擴充
- Vector
  - 連續(xù)空間，前面不可以擴充，后面可以擴充，
- Deque
  - 連續(xù)空間，前后都可以擴充，
- List
  - 雙向鏈表，每一個元素帶有兩個指針，其占用內(nèi)存比單向鏈表要多
- Forward-List
  - 單向鏈表
關(guān)聯(lián)式容器（Associative Containers）（有key和value，適合做快速查找操作）
- set/Multiset
  - set的key就是value，value就是key，set元素不能重復(fù)，Multiset元素可以重復(fù)
- Map/Multimap
  - Map的每一個結(jié)點都有一個key和value，Map元素的key不能重復(fù)，Multimap元素的key可以重復(fù)
不定序容器（Unordered Containers）（是關(guān)聯(lián)式容器中的一種，底部結(jié)構(gòu)是hashtable）

序列式容器（sequence containers）代碼示例

輔助函數(shù)

//得到目標long long get_a_target_long() {long target = 0;cout << "target (0~" << RAND_MAX << "):";cin >> target;return target; } //得到目標string string get_a_target_string() {long target = 0;char buf[10];cout << "target (0~" << RAND_MAX << "):";cin >> target;//snprintf 將數(shù)值target轉(zhuǎn)換成字符串snprintf(buf,10,"%d",target);return string(buf); } //比較兩個long是否相等 int compareLongs(const void *a, const void *b) {return (*(long*)a- *(long*)b); } //比較兩個string是否相等 int compareStrings(const void *a, const void *b) {if (*(string*)a > *(string*)b)return 1;else if (*(string*)a < *(string*)b)return -1;elsereturn 0; }

array 容器

array<long,ASIZE> c; array數(shù)組，第一個參數(shù)是容器中的類型，第二個參數(shù)是數(shù)組的大小。 array.size(); array的大小 array.front(); array的第一個元素 array.back(); array的最后一個元素 array.data(); array數(shù)組的首地址

array容器的測試代碼

#include<iostream> #include<array> #include<ctime> #include<cstdlib>//using namespace std;const int ASIZE = 50000;void test_array() {cout << "test_array() starting......" << endl;array<long, ASIZE> c ;clock_t timeStart = clock();for (long i = 0; i < ASIZE;++i) {c[i] = rand();}cout << "array數(shù)組中插入50000個元素所用時間:" << clock()- timeStart <<endl;cout << "array大小是：" << c.size() << endl;cout << "array中第一個元素是：" << c.front() << endl;cout << "array中最后一個元素是：" << c.back() << endl;cout << "array首地址是：" << c.data() << endl;//設(shè)定目標long值long target = get_a_target_long();timeStart = clock();qsort(c.data(),ASIZE,sizeof(long),compareLongs);long* pItem=(long*)bsearch(&target,c.data(), ASIZE, sizeof(long), compareLongs);cout << "qsort和bsearch所用時間:" << clock() - timeStart << endl;if (pItem != NULL)cout << *pItem << "在數(shù)組中，已找到！" << endl;elsecout << *pItem << "不在數(shù)組中！" << endl; } //調(diào)用test_array() int main() {test_array();system("pause");return 0; }

輸出結(jié)果：

test_array() starting...... array數(shù)組中插入50000個元素所用時間:8 array大小是：50000 array中第一個元素是：41 array中最后一個元素是：14499 array首地址是：001CF028 target (0~32767):2000 qsort和bsearch所用時間:43 2000在數(shù)組中，已找到！

測試代碼中部分函數(shù)解析

qsort和bsearch在cstdlib文件中
qsort(容器首地址，容器中元素數(shù)量，每一個元素的字節(jié)大小，排序方式)
bsearch(查詢內(nèi)容的地址，容器首地址，容器中元素數(shù)量，每一個元素的字節(jié)大小，排序方式)

vector 容器

vector容器的空間大小是兩倍兩倍的增長。其中兩倍增長的意思是，當空間大小不夠時，在另一塊空間找到兩倍大小的空間，將數(shù)據(jù)進行搬移到另一空間，而不是在原有空間的基礎(chǔ)上進行增長。主要原因是因為vector空間連續(xù)。

vector<string> c;聲明一個vector，第一參數(shù)是元素類型，第二參數(shù)是分配器，不寫的話即是默認分配器vector.size() 是真正元素的個數(shù) vector.capacity()是當前空間的大小 vector.push_back()是往vector里放數(shù)據(jù)以下功能同array： vector.front() vector.back() vector.data()

vector 容器的測試代碼

#include<vector> #include<algorithm> #include<iostream> #include<ctime> #include<cstdlib> #include<string>using namespace std;void test_vector(long& targets) {cout << "test_vector() starting......" << endl;vector<string> c;char buf[10];clock_t timeStart = clock();for (long i = 0; i < targets; ++i) {snprintf(buf, 10, "%d", rand());c.push_back(string(buf));}cout << "vector中插入50000個元素所用時間:" << clock() - timeStart << endl;cout << "vector大小是：" << c.size() << endl;cout << "vector容量是：" << c.capacity() << endl;cout << "vector中第一個元素是：" << c.front() << endl;cout << "vector中最后一個元素是：" << c.back() << endl;cout << "vector首地址是：" << c.data() << endl;//設(shè)定目標值string target = get_a_target_string();timeStart = clock();auto ite=find(c.begin(),c.end(),target);cout << "find所用時間:" << clock() - timeStart << endl;if (ite != c.end())cout << *ite << "在vector中，已找到！" << endl;elsecout << *ite << "不在vector中！" << endl;timeStart = clock();sort(c.begin(), c.end());string* pItem = (string*)bsearch(&target,c.data(),c.size(),sizeof(string),compareStrings);cout << "sort+bsearch所用時間：" << clock()-timeStart<<endl;if (pItem != NULL)cout << *pItem << "在vector中，已找到！" << endl;elsecout << *pItem << "不在vector中！" << endl; } //調(diào)用test_vector函數(shù) int main() {long targets = 50000;test_vector(targets);system("pause");return 0; }

輸出結(jié)果：

test_vector() starting...... vector中插入50000個元素所用時間:2047 vector大小是：50000 vector容量是：61447 vector中第一個元素是：41 vector中最后一個元素是：14499 vector首地址是：00970060 target (0~32767):1357 find所用時間:18 1357在vector中，已找到！ sort+bsearch所用時間：4094 1357在vector中，已找到！

測試代碼中部分函數(shù)解析

首尾迭代器是前閉后開區(qū)間的形式

find(首迭代器，尾迭代器，搜尋的目標值)
sort(首迭代器，尾迭代器)
sort(首迭代器，尾迭代器，Compare comp) 其中，comp接受兩個參數(shù)，返回bool值，comp是給出比較兩個數(shù)的大小關(guān)系的方式

list 容器

list是每增加一個元素就增加一個對應(yīng)大小的空間，其存儲空間是不連續(xù)的。空間利用率高，但搜索數(shù)據(jù)慢。

list<string>c; 聲明一個list，第一參數(shù)是元素類型，第二參數(shù)是分配器list.size() 是真正元素的個數(shù)list.capacity()是當前空間的大小list.push_back()是往vector里放數(shù)據(jù)以下功能同array：list.front()list.back()list.data()

list 容器的測試代碼

#include<list> #include<algorithm> #include<functional> #include<iostream> #include<ctime> #include<cstdlib> #include<string> using namespace std;void test_list(long& targets) {cout << "test_list() starting......" << endl;list<string> c;char buf[10];clock_t timeStart = clock();for (long i = 0; i < targets; ++i) {snprintf(buf, 10, "%d", rand());c.push_back(string(buf));}cout << "list中插入50000個元素所用時間:" << clock() - timeStart << endl;cout << "list大小是：" << c.size() << endl;cout << "list max_size大小是：" << c.max_size() << endl;cout << "list中第一個元素是：" << c.front() << endl;cout << "list中最后一個元素是：" << c.back() << endl;//設(shè)定目標值string target = get_a_target_string();timeStart = clock();auto ite = find(c.begin(), c.end(), target);cout << "find所用時間:" << clock() - timeStart << endl;if (ite != c.end())cout << *ite << "在list中，已找到！" << endl;elsecout << *ite << "不在list中！" << endl;timeStart = clock();c.sort();cout << "sort所用時間:" << clock() - timeStart << endl;} //調(diào)用test_list函數(shù) int main() {long targets = 50000;test_list(targets);system("pause");return 0; }

輸出結(jié)果

test_list() starting...... list中插入50000個元素所用時間:840 list大小是：50000 list max_size大小是：119304647 list中第一個元素是：41 list中最后一個元素是：14499 target (0~32767):1234 find所用時間:12 1234在list中，已找到！

測試代碼中部分函數(shù)解析

list和 forward_list都有自己的sort函數(shù)
c.sort();是容器中的sort函數(shù)，不是標準庫中的sort函數(shù)，當容器中有sort函數(shù)時，優(yōu)先選擇容器中的sort函數(shù)

forward_list 容器

forward_list<string>c; 聲明一個forward_list forward_list.push_front() 只有push_front()沒有push_back()，即從beginning開始插入數(shù)據(jù)，比較快，從后面插入數(shù)據(jù)太慢， forward_list.front() 首元素，沒有forward_list.back()，沒有forward_list.size()找forward_list里的元素，可用auto pItem=::find(c.begin(),c.end(),target), ::表示全局，即標準庫中的find函數(shù)，返回的pItem是一個迭代器

deque 容器

雙向開口，可進可出的連續(xù)性存儲空間，但它是分段連續(xù)，即在每一段中是連續(xù)的，段與段之間不連續(xù)，但在使用過程中，我們會覺得deque是整個連續(xù)的當deque的空間不夠用時，調(diào)用push_back時，會再分配一段空間使用deque<string>c; deque的聲明 size(),front(),back(),max_size()函數(shù)意義同上找deque里的元素，可用auto pItem=::find(c.begin(),c.end(),target),deque自身沒有sort函數(shù)，排序要用全局的sort，即 ::sort(c.begin(),c.end());

stack和queue容器沒有新的技術(shù)，是使用deque得到的，一般不稱為容器，而是稱為容器適配器（container adapters）。stack和queue不提供迭代器相關(guān)操作，因為如果有迭代器相關(guān)操作的話，則stack和queue就可以改變其內(nèi)部的數(shù)據(jù)，不再符合先進后出和先進先出的特性。

stack 容器

先進后出stack<string>c; stack的聲明 size() top() 返回最頂部數(shù)據(jù)，不彈出 pop() 最頂部元素彈出來 push() 元素放進去

queue 容器

先進先出queue<string>c; queue的聲明 size() front() back() pop() 元素彈出來 push() 元素放進去

關(guān)聯(lián)式容器（Associative Containers）代碼示例

multiset 容器

沒有push_back,沒有push_front multiset<string>c; multiset.insert() 插入元素 multiset.size() multiset.max_size()搜尋某數(shù)據(jù)，multiset.find()比::find()快

multiset 容器測試代碼

#include<set> #include<algorithm> #include<functional> #include<iostream> #include<ctime> #include<cstdlib> #include<string>using namespace std;void test_multiset(long& targets) {cout << "test_multiset() starting......" << endl;multiset<string> c;char buf[10];clock_t timeStart = clock();for (long i = 0; i < targets; ++i) {snprintf(buf, 10, "%d", rand());c.insert(string(buf));}cout << "multiset中插入50000個元素所用時間:" << clock() - timeStart << endl;cout << "multiset大小是：" << c.size() << endl;cout << "multiset max_size大小是：" << c.max_size() << endl;//設(shè)定目標值string target = get_a_target_string();timeStart = clock();auto ite = find(c.begin(), c.end(), target);cout << "find所用時間:" << clock() - timeStart << endl;if (ite != c.end())cout << *ite << "在multiset中，已找到！" << endl;elsecout << *ite << "不在multiset中！" << endl;timeStart = clock();c.find(target);cout << "multiset容器中find所用時間:" << clock() - timeStart << endl;} //調(diào)用test_multiset函數(shù)int main() {long targets = 50000;test_multiset(targets);system("pause");return 0; }

輸出結(jié)果，可以看出，容器自帶的find函數(shù)快

test_multiset() starting...... multiset中插入50000個元素所用時間:2966 multiset大小是：50000 multiset max_size大小是：97612893 target (0~32767):88 find所用時間:62 88在multiset中，已找到！ multiset容器中sort所用時間:0

multimap 容器

multimap<long,string>c; 聲明multimap multimap.insert(pair<long,string>(i,buf)); 插入key，value multimap不可用[]做插入操作

multimap 容器測試代碼

#include<map> #include<algorithm> #include<functional> #include<iostream> #include<ctime> #include<cstdlib> #include<string>using namespace std;void test_multimap(long& targets) {cout << "test_multimap() starting......" << endl;multimap<long,string> c;char buf[10];clock_t timeStart = clock();for (long i = 0; i < targets; ++i) {snprintf(buf, 10, "%d", rand());c.insert(pair<long, string>(i,string(buf)));}cout << "multimap中插入50000個元素所用時間:" << clock() - timeStart << endl;cout << "multimap大小是：" << c.size() << endl;cout << "multimap max_size大小是：" << c.max_size() << endl;//設(shè)定目標long值long target = get_a_target_long();timeStart = clock();auto pItem=c.find(target);cout << "multimap容器中find所用時間:" << clock() - timeStart << endl;if (pItem != c.end())cout << "key為：" << pItem->first << " 在multimap中已找到，其value為：" << pItem->second << endl;elsecout << "key為：" << pItem->first << " 在multimap中不存在" << endl;}//調(diào)用test_multimap函數(shù) int main() {long targets = 50000;test_multimap(targets);system("pause");return 0; }

輸出結(jié)果

test_multimap() starting...... multimap中插入50000個元素所用時間:2760 multimap大小是：50000 multimap max_size大小是：89478485 target (0~32767):30000 multimap容器中find所用時間:0 key為：30000 在multimap中已找到，其value為：8970

unordered_multiset 容器

unordered_multiset 容器底層結(jié)構(gòu)是hashtable，multiset和multimap底層結(jié)構(gòu)是紅黑樹

#include<unordered_set> unordered_multiset<string> c;c.size() c.max_size() c.bucket_count(); bucket的個數(shù) c.load_factor(); 載重因子 c.max_load_factor(); 最大載重因子為1 c.max_bucket_count(); 最大bucket個數(shù) c.bucket_size(i);

unordered_multiset 容器測試代碼

#include<unordered_set> #include<algorithm> #include<functional> #include<iostream> #include<ctime> #include<cstdlib> #include<string>using namespace std;void test_unordered_multiset(long& targets) {cout << "test_unordered_multiset() starting......" << endl;unordered_multiset<string> c;char buf[10];clock_t timeStart = clock();for (long i = 0; i < targets; ++i) {snprintf(buf, 10, "%d", rand());c.insert(string(buf));}cout << "unordered_multiset中插入50000個元素所用時間:" << clock() - timeStart << endl;cout << "unordered_multiset size是：" << c.size() << endl;cout << "unordered_multiset max_size大小是：" << c.max_size() << endl;cout << "unordered_multiset bucket_count()是：" << c.bucket_count() << endl;cout << "unordered_multiset load_factor()是：" << c.load_factor() << endl;cout << "unordered_multiset max_load_factor()是：" << c.max_load_factor() << endl;cout << "unordered_multiset max_bucket_count()是：" << c.max_bucket_count() << endl;for (int i = 0; i < 20;++i) {cout << "bucket # " << i << " has " << c.bucket_size(i) << " elements" << endl;}//設(shè)定目標值string target = get_a_target_string();timeStart = clock();auto ite = find(c.begin(), c.end(), target);cout << "find所用時間:" << clock() - timeStart << endl;if (ite != c.end())cout << *ite << "在unordered_multiset中，已找到！" << endl;elsecout << *ite << "不在unordered_multiset中！" << endl;timeStart = clock();c.find(target);cout << "unordered_multiset容器中find所用時間:" << clock() - timeStart << endl;}

輸出結(jié)果

test_unordered_multiset() starting...... unordered_multiset中插入50000個元素所用時間:3668 unordered_multiset size是：50000 unordered_multiset max_size大小是：119304647 unordered_multiset bucket_count()是：65536 unordered_multiset load_factor()是：0.762939 unordered_multiset max_load_factor()是：1 unordered_multiset max_bucket_count()是：536870911 bucket # 0 has 0 elements bucket # 1 has 0 elements bucket # 2 has 2 elements bucket # 3 has 0 elements bucket # 4 has 8 elements bucket # 5 has 2 elements bucket # 6 has 0 elements bucket # 7 has 0 elements bucket # 8 has 0 elements bucket # 9 has 0 elements bucket # 10 has 0 elements bucket # 11 has 0 elements bucket # 12 has 0 elements bucket # 13 has 0 elements bucket # 14 has 0 elements bucket # 15 has 0 elements bucket # 16 has 0 elements bucket # 17 has 0 elements bucket # 18 has 0 elements bucket # 19 has 0 elements target (0~32767):1357 find所用時間:36 1357在unordered_multiset中，已找到！ unordered_multiset容器中find所用時間:0

unordered_multimap 容器

使用方法同multimap

set容器，map容器

使用方法同multiset，multimap，但是插入數(shù)據(jù)不重復(fù) map可以用[]插入數(shù)據(jù)，例 map[key]=value;

unordered_set 容器

unordered_map 容器

底層結(jié)構(gòu)是hashtable，用法同set和map

總結(jié)

以上是生活随笔為你收集整理的C++STL与泛型编程（3）容器之分类与测试的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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