C++STL与泛型编程（3）容器之分类与测试
2020-04-06 16:53:48
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
版权
文章目录
容器的分类
序列式容器（sequence containers）代码示例
stack 容器
queue 容器
list 容器的测试代码
测试代码中部分函数解析
vector 容器的测试代码
测试代码中部分函数解析
array容器的测试代码
测试代码中部分函数解析
辅助函数
array 容器
vector 容器
list 容器
forward_list 容器
deque 容器
关联式容器（Associative Containers）代码示例
unordered_multiset 容器测试代码
multimap 容器测试代码
multiset 容器测试代码
multiset 容器
multimap 容器
unordered_multiset 容器
unordered_multimap 容器
set容器，map容器
unordered_set 容器
unordered_map 容器
容器的分类
序列式容器（sequence containers）
单向链表
双向链表，每一个元素带有两个指针，其占用内存比单向链表要多
连续空间，前后都可以扩充，
连续空间，前面不可以扩充，后面可以扩充，
连续空间，大小不能扩充
Array
Vector
Deque
List
Forward-List
关联式容器（Associative Containers）（有key和value，适合做快速查找操作）
Map的每一个结点都有一个key和value，Map元素的key不能重复，Multimap元素的key可以重复
set的key就是value，value就是key，set元素不能重复，Multiset元素可以重复
set/Multiset
Map/Multimap
不定序容器（Unordered Containers）（是关联式容器中的一种，底部结构是hashtable）
序列式容器（sequence containers）代码示例
辅助函数
//得到目标longlong get_a_target_long() {long target = 0;cout << "target (0~" << RAND_MAX << "):";cin >> target;return target;}//得到目标stringstring get_a_target_string() {long target = 0;char buf[10];cout << "target (0~" << RAND_MAX << "):";cin >> target;//snprintf 将数值target转换成字符串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数组，第一个参数是容器中的类型，第二个参数是数组的大小。array.size();array的大小array.front();array的第一个元素array.back();array的最后一个元素array.data();array数组的首地址
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数组中插入50000个元素所用时间:" << clock()- timeStart <<endl;cout << "array大小是：" << c.size() << endl;cout << "array中第一个元素是：" << c.front() << endl;cout << "array中最后一个元素是：" << c.back() << endl;cout << "array首地址是：" << c.data() << endl;//设定目标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 << "在数组中，已找到！" << endl;elsecout << *pItem << "不在数组中！" << endl;}//调用test_array()int main() {test_array();system("pause");return 0;}
输出结果：
test_array() starting......array数组中插入50000个元素所用时间:8array大小是：50000array中第一个元素是：41array中最后一个元素是：14499array首地址是：001CF028target (0~32767):2000qsort和bsearch所用时间:432000在数组中，已找到！
测试代码中部分函数解析
qsort和bsearch在cstdlib文件中
qsort(容器首地址，容器中元素数量，每一个元素的字节大小，排序方式)
bsearch(查询内容的地址，容器首地址，容器中元素数量，每一个元素的字节大小，排序方式)
vector 容器
vector容器的空间大小是两倍两倍的增长。其中两倍增长的意思是，当空间大小不够时，在另一块空间找到两倍大小的空间，将数据进行搬移到另一空间，而不是在原有空间的基础上进行增长。主要原因是因为vector空间连续。
vector<string> c;声明一个vector，第一参数是元素类型，第二参数是分配器，不写的话即是默认分配器vector.size() 是真正元素的个数vector.capacity()是当前空间的大小vector.push_back()是往vector里放数据以下功能同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;//设定目标值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;}//调用test_vector函数int main() {long targets = 50000;test_vector(targets);system("pause");return 0;}
输出结果：
test_vector() starting......vector中插入50000个元素所用时间:2047vector大小是：50000vector容量是：61447vector中第一个元素是：41vector中最后一个元素是：14499vector首地址是：00970060target (0~32767):1357find所用时间:181357在vector中，已找到！sort+bsearch所用时间：40941357在vector中，已找到！
测试代码中部分函数解析
首尾迭代器是前闭后开区间的形式
find(首迭代器，尾迭代器，搜寻的目标值)
sort(首迭代器，尾迭代器)
sort(首迭代器，尾迭代器，Compare comp) 其中，comp接受两个参数，返回bool值，comp是给出比较两个数的大小关系的方式
list 容器
list是每增加一个元素就增加一个对应大小的空间，其存储空间是不连续的。空间利用率高，但搜索数据慢。
list<string>c;声明一个list，第一参数是元素类型，第二参数是分配器 list.size() 是真正元素的个数 list.capacity()是当前空间的大小 list.push_back()是往vector里放数据以下功能同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;//设定目标值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;}//调用test_list函数int main() {long targets = 50000;test_list(targets);system("pause");return 0;}
输出结果
test_list() starting......list中插入50000个元素所用时间:840list大小是：50000list max_size大小是：119304647list中第一个元素是：41list中最后一个元素是：14499target (0~32767):1234find所用时间:121234在list中，已找到！
测试代码中部分函数解析
list和 forward_list都有自己的sort函数
c.sort();是容器中的sort函数，不是标准库中的sort函数，当容器中有sort函数时，优先选择容器中的sort函数
forward_list 容器
forward_list<string>c;声明一个forward_listforward_list.push_front()只有push_front()没有push_back()，即从beginning开始插入数据，比较快，从后面插入数据太慢，forward_list.front()首元素，没有forward_list.back()，没有forward_list.size()找forward_list里的元素，可用auto pItem=::find(c.begin(),c.end(),target),::表示全局，即标准库中的find函数，返回的pItem是一个迭代器
deque 容器
双向开口，可进可出的连续性存储空间，但它是分段连续，即在每一段中是连续的，段与段之间不连续，但在使用过程中，我们会觉得deque是整个连续的当deque的空间不够用时，调用push_back时，会再分配一段空间使用deque<string>c; deque的声明size(),front(),back(),max_size()函数意义同上找deque里的元素，可用auto pItem=::find(c.begin(),c.end(),target),deque自身没有sort函数，排序要用全局的sort，即 ::sort(c.begin(),c.end());
stack和queue容器没有新的技术，是使用deque得到的，一般不称为容器，而是称为容器适配器（container adapters）。stack和queue不提供迭代器相关操作，因为如果有迭代器相关操作的话，则stack和queue就可以改变其内部的数据，不再符合先进后出和先进先出的特性。
stack 容器
先进后出stack<string>c; stack的声明size()top()返回最顶部数据，不弹出pop()最顶部元素弹出来push()元素放进去
queue 容器
先进先出queue<string>c; queue的声明size()front()back()pop()元素弹出来push()元素放进去
关联式容器（Associative Containers）代码示例
multiset 容器
没有push_back,没有push_frontmultiset<string>c;multiset.insert()插入元素multiset.size()multiset.max_size()搜寻某数据，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;//设定目标值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;}//调用test_multiset函数int main() {long targets = 50000;test_multiset(targets);system("pause");return 0;}
输出结果，可以看出，容器自带的find函数快
test_multiset() starting......multiset中插入50000个元素所用时间:2966multiset大小是：50000multiset max_size大小是：97612893target (0~32767):88find所用时间:6288在multiset中，已找到！multiset容器中sort所用时间:0
multimap 容器
multimap<long,string>c;声明multimapmultimap.insert(pair<long,string>(i,buf));插入key，valuemultimap不可用[]做插入操作
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;//设定目标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;}//调用test_multimap函数int main() {long targets = 50000;test_multimap(targets);system("pause");return 0;}
输出结果
test_multimap() starting......multimap中插入50000个元素所用时间:2760multimap大小是：50000multimap max_size大小是：89478485target (0~32767):30000multimap容器中find所用时间:0key为：30000 在multimap中已找到，其value为：8970
unordered_multiset 容器
unordered_multiset 容器底层结构是hashtable，multiset和multimap底层结构是红黑树
#include<unordered_set>unordered_multiset<string> c;c.size()c.max_size()c.bucket_count();bucket的个数c.load_factor();载重因子c.max_load_factor();最大载重因子为1c.max_bucket_count();最大bucket个数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;}//设定目标值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;}
输出结果
test_unordered_multiset() starting......unordered_multiset中插入50000个元素所用时间:3668unordered_multiset size是：50000unordered_multiset max_size大小是：119304647unordered_multiset bucket_count()是：65536unordered_multiset load_factor()是：0.762939unordered_multiset max_load_factor()是：1unordered_multiset max_bucket_count()是：536870911bucket # 0 has 0 elementsbucket # 1 has 0 elementsbucket # 2 has 2 elementsbucket # 3 has 0 elementsbucket # 4 has 8 elementsbucket # 5 has 2 elementsbucket # 6 has 0 elementsbucket # 7 has 0 elementsbucket # 8 has 0 elementsbucket # 9 has 0 elementsbucket # 10 has 0 elementsbucket # 11 has 0 elementsbucket # 12 has 0 elementsbucket # 13 has 0 elementsbucket # 14 has 0 elementsbucket # 15 has 0 elementsbucket # 16 has 0 elementsbucket # 17 has 0 elementsbucket # 18 has 0 elementsbucket # 19 has 0 elementstarget (0~32767):1357find所用时间:361357在unordered_multiset中，已找到！unordered_multiset容器中find所用时间:0
unordered_multimap 容器
使用方法同multimap
set容器，map容器
使用方法同multiset，multimap，但是插入数据不重复map可以用[]插入数据，例 map[key]=value;
unordered_set 容器
unordered_map 容器
底层结构是hashtable，用法同set和map
赞 (0)