【c++标准库笔记（三）侯捷老师课程】STL容器分类与各种测试（附代码及测试截图）
由于源代码有点长，所以我放在GitHub上了
目录
1.序列式容器
2.关联式容器（元素有key-value，适合做快速查找）
3.不定序容器
二、对容器的测试代码
辅助函数：
1.对array的测试
2.对vector的测试
3.对list的测试
4.对forward-list的测试
5.对deque的测试
6.对slist，stack，queue的测试
7.对multiset的测试
8.对multimap的测试
9.对unordered_multiset/unordered_multimap的测试
10.对map/set，unordered_set/unordered_map的测试
三、关于源代码
一、容器的结构与分类
1.序列式容器
1.array：连续空间，你要多大就多大
2.vector：自动扩充，分配器在背后作用
3.deque：理解为两端可进可出的队列
4.list：链表，双向链表
5.forward-list：单向链表
2.关联式容器（元素有key-value，适合做快速查找）
1.set/multiset：集合（用红黑树做） key和value是同一个，不分的
前者元素不能重复，后者可以
2.map/multimap：用红黑树做，每个节点有key和value，将来用key来找value
前者key不能重复，后者可以
3.不定序容器
1.unordered set/multiset：
2.unordered map/multimap：
对hash table （separate changing）的补充：分离链地址法实现
二、对容器的测试代码
辅助函数：
1.输入目标数值
2.输入目标数值，转化为字符串
3.对数值的比大小（为了进行快排）
4.对字符串的比大小（为了进行快排）
long get_a_target_long(){long target = 0;cout << "target (0~" << RAND_MAX << "):" ;cin >> target;return target;}string get_a_target_string(){long target = 0;char buf[10];cout << "target (0~" << RAND_MAX << "):" ;cin >> target;snprintf(buf, 10, "%d", target);return string(buf);}int compareLongs(const void* a, const void* b ){return ( *(long*)a - *(long*)b );// 将a转化为long类型的指针，并取其指向地址的值（即target的值）}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;}
1.对array的测试
首先，创建一个大小为50万的array，接着，对每个元素进行赋值（随机数）
然后，对整个array的每个元素进行qsort（快排），最后，对输入的数据进行二分查找（bsearch）
(1) c.data()返回数组首地址(2) 使用bsearch二分查找前需要对数组进行排序，这里使用快排qsort，两者都是c标准库的必须使用头文件<cstdlib>(3) qsort应用：qsort(c.data,size,size(long),comparelongs)(4) bsearch()应用：bsearch(&target,(c.data()),size,size(long),comparelongs)
#include<array>#include<ctime>#include<cstdlib>#include<iostream>namespace jj01{void test_array(){cout << "\ntest array .........." << endl;array<long, ASIZE> c;clock_t timeStart = clock();for (long i = 0; i < ASIZE; i++) {c[i] = rand();}cout << "milli-seconds：" << clock() - timeStart << endl;cout << "c.size() = " << c.size() << endl;cout << "c.front() = " << c.front() << endl;cout << "c.back() = " << c.back() << endl;cout << "c.data() = " << c.data() << endl;long target = get_a_target_long();timeStart = clock();qsort(c.data(), ASIZE, sizeof(long), compareLongs);//数组首地址，数组有多少项，每项大小，比大小函数long* flag = (long*)bsearch(&target, (c.data()), ASIZE, sizeof(long), compareLongs);cout << "qsort()+bsearch(),milli-seconds:" << clock() - timeStart << endl;if (flag != NULL)cout << "found," << *flag << endl;elsecout << "not found!!!" << endl;}}
2.对vector的测试
(1) vecotr增长速度为两倍增长，当capacity不够时，乘以2,例如, 插入第一个数据，vector本身容量为1，够用。插入第二个数据，vector容量*2，变为2。插入第三个数据，vector容量*2，变为4。（此时vector只存了3个数据，即size=3，而capacity=4）(2) vector 是去别的地方找一块本身两倍的内存，然后把现在的所有内容搬过去(3) 关于异常处理，采用try...catch结构(4) ::find()模板函数，加冒号表明是全局函数，当没有冒号时，编译器在当前没有找到，也会到全局去找。
#include<vector>#include<cstdlib>//qsort,bsearch,abort#include<cstdio>//snprintf#include<iostream>#include<string>#include<ctime>#include<algorithm>//算法，sort#include<stdexcept>//抛出异常namespace jj02{void test_vector(long& value)//传引用{cout << "test vector.........." << endl;vector<string> c;char buf[10];clock_t timeStart = clock();for (long i = 0; i < value; i++){try{snprintf(buf, 10, "%d", rand());c.push_back(string(buf));//buf是一个char数组，需要转化为string类型，才能放入vector中}//如果系统无法再分配空间了，就会引发异常catch (exception& p)//捕获了异常，抓住了异常{cout << "i=" << i << " " << p.what() << endl;abort();//退出程序}}cout << "milli-seconds:" << clock() - timeStart << endl;cout << "c.size() = " << c.size() << endl;cout << "c.front() = " << c.front() << endl;cout << "c.back() = " << c.back() << endl;cout << "c.data() = " << c.data() << endl;cout << "c.capicy() = " << c.capacity() << endl;//vector两倍增长，放入1，变成2，放入2，不变，放入3，变成4，放入4，不变//放入5，变成8,放入6,7,8，均不变，所以capacity是容器能存储的元素个数//而size是容器目前存在的元素个数string target = get_a_target_string();{timeStart = clock();auto flag = ::find(c.begin(), c.end(), target);cout << "::find().milli-seconds:" << clock() - timeStart << endl;if (flag != c.end())cout << "found," << *flag << endl;elsecout << "not found" << endl;}{timeStart = clock();sort(c.begin(), c.end());string* flag = (string*)bsearch(&target, c.data(), c.size(), sizeof(string), compareStrings);cout << "qsort()+bsearch(),milli-seconds:" << clock() - timeStart << endl;if (flag != NULL)cout << "found," << *flag << endl;elsecout << "not found!!!" << endl;}}}
3.对list的测试
在STL标准库全局有一个sort函数，但这里调用的是list容器自身内部的sort函数。注意在STL容器中有些自身有sort函数，此时用自身的排序算法更快。
#include<list>#include<cstdlib>//qsort,bsearch,abort#include<cstdio>//snprintf#include<iostream>#include<string>#include<ctime>#include<algorithm>//算法，sort#include<stdexcept>//抛出异常namespace jj03{void test_list(long& value)//传引用{cout << "test list.........." << endl;list<string> c;char buf[10];clock_t timeStart = clock();for (long i = 0; i < value; i++){try{snprintf(buf, 10, "%d", rand());c.push_back(string(buf));//buf是一个char数组，需要转化为string类型，才能放入vector中}//如果系统无法再分配空间了，就会引发异常catch (exception& p)//捕获了异常，抓住了异常{cout << "i=" << i << " " << p.what() << endl;abort();//退出程序}}cout << "milli-seconds:" << clock() - timeStart << endl;cout << "c.size() = " << c.size() << endl;cout << "c.front() = " << c.front() << endl;cout << "c.back() = " << c.back() << endl;cout << "c.max_size() = " << c.max_size() << endl;string target = get_a_target_string();timeStart = clock();auto flag = ::find(c.begin(), c.end(), target);cout << "::find().milli-seconds:" << clock() - timeStart << endl;if (flag != c.end())cout << "found," << *flag << endl;elsecout << "not found" << endl;timeStart = clock();c.sort();cout << "c.sort(),milli-seconds:" << clock() - timeStart << endl;}}
4.对forward-list的测试
#include <forward_list>#include <stdexcept>#include <string>#include <cstdlib> //abort()#include <cstdio> //snprintf()#include <iostream>#include <ctime>namespace jj04{void test_forward_list(long& value){cout << "\ntest_forward_list().......... \n";forward_list<string> c;char buf[10];clock_t timeStart = clock();for (long i = 0; i < value; ++i){try {snprintf(buf, 10, "%d", rand());c.push_front(string(buf));}catch (exception& p) {cout << "i=" << i << " " << p.what() << endl;abort();}}cout << "milli-seconds : " << (clock() - timeStart) << endl;cout << "forward_list.max_size()= " << c.max_size() << endl; //536870911cout << "forward_list.front()= " << c.front() << endl;string target = get_a_target_string();timeStart = clock();auto pItem = find(c.begin(), c.end(), target);cout << "std::find(), milli-seconds : " << (clock() - timeStart) << endl;if (pItem != c.end())cout << "found, " << *pItem << endl;elsecout << "not found! " << endl;timeStart = clock();c.sort();cout << "c.sort(), milli-seconds : " << (clock() - timeStart) << endl;c.clear();}}
5.对deque的测试
(1) 每次扩充一个buffer，buffer由指针指向(2) 本身没有sort函数，所以只能使用全局的sort函数排序
#include<deque>#include<cstdlib>//qsort,bsearch,abort#include<cstdio>//snprintf#include<iostream>#include<string>#include<ctime>#include<algorithm>//算法，sort#include<stdexcept>//抛出异常namespace jj05{void test_deque(long& value)//传引用{cout << endl << "test deque.........." << endl;deque<string> c;char buf[10];clock_t timeStart = clock();for (long i = 0; i < value; i++){try{snprintf(buf, 10, "%d", rand());c.push_back(string(buf));//buf是一个char数组，需要转化为string类型，才能放入vector中}//如果系统无法再分配空间了，就会引发异常catch (exception& p)//捕获了异常，抓住了异常{cout << "i=" << i << " " << p.what() << endl;abort();//退出程序}}cout << "milli-seconds:" << clock() - timeStart << endl;cout << "c.size() = " << c.size() << endl;cout << "c.front() = " << c.front() << endl;cout << "c.back() = " << c.back() << endl;cout << "c.max_size() = " << c.max_size() << endl;string target = get_a_target_string();timeStart = clock();auto flag = ::find(c.begin(), c.end(), target);cout << "::find().milli-seconds:" << clock() - timeStart << endl;if (flag != c.end())cout << "found," << *flag << endl;elsecout << "not found" << endl;timeStart = clock();::sort(c.begin(), c.end());cout << "::sort(c.begin(), c.end()),milli-seconds:" << clock() - timeStart << endl;}}
6.对slist，stack，queue的测试
(1) stack和queue严格来讲是一种容器适配器，其内部都是由deque构成的(2) stack和queue不会有一个函数来返回迭代器（泛化的指针），因为有了迭代器可能你就会去改变stack或queue中的某个数据的值，或者说插入一个数据，然而这与stack和queue自身的先进后出和先进先出的特点相违背。所以以上两种适配器find是无法作用的，因为find函数返回的是迭代器类型
好吧其实我并没有测试这些，代码和上面的都差不多，自己去体会一下各自的特点就行
7.对multiset的测试
(1) 先测试multiset而不是set的原因：前者可以放重复数据，而后者不行(2) 元素放进去为insert，你无需知道它具体放在哪，只需知道它放进去了（放在红黑树中）(3) 把元素放进去就已经给你排序好了，所以时间比较久(4) 测试了全局的find和multiset本身的find函数速度（结果显而易见）(5) 关联式容器查找非常快，给它一个key，很快就能查找到value。
#include<set>#include<cstdlib>//qsort,bsearch,abort#include<cstdio>//snprintf#include<iostream>#include<string>#include<ctime>#include<algorithm>//算法，sort#include<stdexcept>//抛出异常namespace jj06{void test_multiset(long& value)//传引用{cout << endl << "test multiset.........." << endl;multiset<string> c;char buf[10];clock_t timeStart = clock();for (long i = 0; i < value; i++){try{snprintf(buf, 10, "%d", rand());c.insert(string(buf));//buf是一个char数组，需要转化为string类型，才能放入vector中}//如果系统无法再分配空间了，就会引发异常catch (exception& p)//捕获了异常，抓住了异常{cout << "i=" << i << " " << p.what() << endl;abort();//退出程序}}cout << "milli-seconds:" << clock() - timeStart << endl;cout << "c.size() = " << c.size() << endl;cout << "c.max_size() = " << c.max_size() << endl;string target = get_a_target_string();timeStart = clock();auto flag = ::find(c.begin(), c.end(), target);cout << "::find().milli-seconds:" << clock() - timeStart << endl;if (flag != c.end())cout << "found," << *flag << endl;elsecout << "not found" << endl;timeStart = clock();flag = c.find(target);cout << "c.find(target),milli-seconds:" << clock() - timeStart << endl;if (flag != c.end())cout << "found," << *flag << endl;elsecout << "not found" << endl;}}
8.对multimap的测试
(1) multimap内部是红黑树，用key来找value(2) multimap不可以用[]来做insertion（原因见map）(3) c.insert( pair<long,string> (i, buff ) )(4) pair表示multimap中的键值对(5) (*flag).secondflag是一个迭代器，前面加*，表示返回迭代器所指的值（这里是指key值为target的的pair，second表示pair的第二个元素）
#include<map>#include<string>#include<cstdlib>//qsort,bsearch,abort#include<cstdio>//snprintf#include<iostream>#include<ctime>#include<stdexcept>//抛出异常namespace jj07{void test_multimap(long& value)//传引用{cout << endl << "test multimap.........." << endl;multimap <long,string> c;char buf[10];clock_t timeStart = clock();for (long i = 0; i < value; i++){try{snprintf(buf, 10, "%d", rand());c.insert( pair<long, string> (i, buf));}catch (exception& p)//捕获了异常，抓住了异常{cout << "i=" << i << " " << p.what() << endl;abort();//退出程序}}cout << "milli-seconds:" << clock() - timeStart << endl;cout << "c.size() = " << c.size() << endl;cout << "c.max_size() = " << c.max_size() << endl;long target = get_a_target_long();timeStart = clock();auto flag = c.find(target);cout << "c.find(target),milli-seconds:" << clock() - timeStart << endl;if (flag != c.end())cout << "found," << (*flag).second << endl;elsecout << "not found" << endl;}}
9.对unordered_multiset/unordered_multimap的测试
(1) 使用hashtable使用分离链地址方法实现(2) 篮子比存的元素多，合理，原因：若元素个数>=篮子个数，篮子需要扩充，变成大约两倍原来的元素重新打散，挂在篮子上
#include<unordered_set>#include<cstdlib>//qsort,bsearch,abort#include<cstdio>//snprintf#include<iostream>#include<string>#include<ctime>#include<algorithm>//算法，sort#include<stdexcept>//抛出异常namespace jj08{void test_unordered_multiset(long& value)//传引用{cout << endl << "test unordered_multiset.........." << endl;unordered_multiset<string> c;char buf[10];clock_t timeStart = clock();for (long i = 0; i < value; i++){try{snprintf(buf, 10, "%d", rand());c.insert(string(buf));//buf是一个char数组，需要转化为string类型}//如果系统无法再分配空间了，就会引发异常catch (exception& p)//捕获了异常，抓住了异常{cout << "i=" << i << " " << p.what() << endl;abort();//退出程序}}cout << "milli-seconds:" << clock() - timeStart << endl;cout << "c.size() = " << c.size() << endl;cout << "c.max_size() = " << c.max_size() << endl;cout << "c.buket_count() = " << c.bucket_count() << endl;cout << "c.load_factor() = " << c.load_factor() << endl;cout << "c.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 flag = ::find(c.begin(), c.end(), target);cout << "::find().milli-seconds:" << clock() - timeStart << endl;if (flag != c.end())cout << "found," << *flag << endl;elsecout << "not found" << endl;timeStart = clock();flag = c.find(target);cout << "c.find(target),milli-seconds:" << clock() - timeStart << endl;if (flag != c.end())cout << "found," << *flag << endl;elsecout << "not found" << endl;}}
10.对map/set，unordered_set/unordered_map的测试
(1) set中key和value是同一个，所以其中不允许存重复数据存了1000000，但实际上真正的大小只有32768，因为是存了(0~32767)(2) map中key不可重复，value可重复map的insertion可用[]c[i] = string(buf);map会把key和value合成一个pair，放入红黑树
三、关于源代码
由于源代码有点长，所以我放在GitHub上了
赞 (0)