第六节:容器之分类和各种测试(四)
-
stack
不提供iterator
操作,破坏了容器的独特性,先进先出。
使用容器multiset(允许元素重复)
- 内部是红黑树,
insert
操作就保证了排好了序。 - 标准库有个
::find()
函数,大家都可以用。容器本身也有一个c.find()
,通过键值对查找非常快! - 测试
#include <set>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio> //snprintf()
#include <iostream>
#include <ctime>
namespace jj06
{
void test_multiset(long& value)
{
cout << "\ntest_multiset().......... \n";
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));
}
catch(exception& p) {
cout << "i=" << i << " " << p.what() << endl;
abort();
}
}
cout << "milli-seconds : " << (clock()-timeStart) << endl;
cout << "multiset.size()= " << c.size() << endl;
cout << "multiset.max_size()= " << c.max_size() << endl; //214748364
string target = get_a_target_string();
{
timeStart = clock();
auto pItem = find(c.begin(), c.end(), target); //比 c.find(...) 慢很多
cout << "std::find(), milli-seconds : " << (clock()-timeStart) << endl;
if (pItem != c.end())
cout << "found, " << *pItem << endl;
else
cout << "not found! " << endl;
}
{
timeStart = clock();
auto pItem = c.find(target); //比 std::find(...) 快很多
cout << "c.find(), milli-seconds : " << (clock()-timeStart) << endl;
if (pItem != c.end())
cout << "found, " << *pItem << endl;
else
cout << "not found! " << endl;
}
c.clear();
test_moveable(multiset<MyString>(),multiset<MyStrNoMove>(), value);
}
}
使用容器multimap(允许元素重复)
- 内部是红黑树,key-value键值对。
-
multiset
不可用[]做insertion c.insert(pair<long,string>(i,buff))
(*pItem).second
- 测试
#include <map>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio> //snprintf()
#include <iostream>
#include <ctime>
namespace jj07
{
void test_multimap(long& value)
{
cout << "\ntest_multimap().......... \n";
multimap<long, string> c;
char buf[10];
clock_t timeStart = clock();
for(long i=0; i< value; ++i)
{
try {
snprintf(buf, 10, "%d", rand());
//multimap 不可使用 [] 做 insertion
c.insert(pair<long,string>(i,buf));
}
catch(exception& p) {
cout << "i=" << i << " " << p.what() << endl;
abort();
}
}
cout << "milli-seconds : " << (clock()-timeStart) << endl;
cout << "multimap.size()= " << c.size() << endl;
cout << "multimap.max_size()= " << c.max_size() << endl; //178956970
long target = get_a_target_long();
timeStart = clock();
auto pItem = c.find(target);
cout << "c.find(), milli-seconds : " << (clock()-timeStart) << endl;
if (pItem != c.end())
cout << "found, value=" << (*pItem).second << endl;
else
cout << "not found! " << endl;
c.clear();
}
}
使用unordered_multiset容器
- 使用
hashtable
使用分离链地址方法实现 -
gnu C
之前的名称hash_multiset
-
unorder_multiset.bucket_count
篮子的个数 -
load_factor
,max_load_factor
,max_bucket_count
方法 - 篮子后面的链表不能太长,元素的个数大于等于篮子的个数,就需要重新分配篮子的大小,重新进行插入元素
-
c.find()
容器自身的find操作快很多 - 测试
#include <unordered_set>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio> //snprintf()
#include <iostream>
#include <ctime>
namespace jj08
{
void test_unordered_multiset(long& value)
{
cout << "\ntest_unordered_multiset().......... \n";
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));
}
catch(exception& p) {
cout << "i=" << i << " " << p.what() << endl;
abort();
}
}
cout << "milli-seconds : " << (clock()-timeStart) << endl;
cout << "unordered_multiset.size()= " << c.size() << endl;
cout << "unordered_multiset.max_size()= " << c.max_size() << endl; //357913941
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 (unsigned i=0; i< 20; ++i) {
cout << "bucket #" << i << " has " << c.bucket_size(i) << " elements.\n";
}
string target = get_a_target_string();
{
timeStart = clock();
auto pItem = find(c.begin(), c.end(), target); //比 c.find(...) 慢很多
cout << "std::find(), milli-seconds : " << (clock()-timeStart) << endl;
if (pItem != c.end())
cout << "found, " << *pItem << endl;
else
cout << "not found! " << endl;
}
{
timeStart = clock();
auto pItem = c.find(target); //比 std::find(...) 快很多
cout << "c.find(), milli-seconds : " << (clock()-timeStart) << endl;
if (pItem != c.end())
cout << "found, " << *pItem << endl;
else
cout << "not found! " << endl;
}
c.clear();
test_moveable(unordered_multiset<MyString>(),unordered_multiset<MyStrNoMove>(), value);
}
}
使用unordered_multimap容器
- 测试
#include <unordered_map>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio> //snprintf()
#include <iostream>
#include <ctime>
namespace jj09
{
void test_unordered_multimap(long& value)
{
cout << "\ntest_unordered_multimap().......... \n";
unordered_multimap<long, string> c;
char buf[10];
clock_t timeStart = clock();
for(long i=0; i< value; ++i)
{
try {
snprintf(buf, 10, "%d", rand());
//multimap 不可使用 [] 進行 insertion
c.insert(pair<long,string>(i,buf));
}
catch(exception& p) {
cout << "i=" << i << " " << p.what() << endl;
abort();
}
}
cout << "milli-seconds : " << (clock()-timeStart) << endl;
cout << "unordered_multimap.size()= " << c.size() << endl;
cout << "unordered_multimap.max_size()= " << c.max_size() << endl; //357913941
long target = get_a_target_long();
timeStart = clock();
auto pItem = c.find(target);
cout << "c.find(), milli-seconds : " << (clock()-timeStart) << endl;
if (pItem != c.end())
cout << "found, value=" << (*pItem).second << endl;
else
cout << "not found! " << endl;
}
}
使用set容器
- 不允许元素重复
#include <set>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio> //snprintf()
#include <iostream>
#include <ctime>
namespace jj13
{
void test_set(long& value)
{
cout << "\ntest_set().......... \n";
set<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));
}
catch(exception& p) {
cout << "i=" << i << " " << p.what() << endl;
abort();
}
}
cout << "milli-seconds : " << (clock()-timeStart) << endl;
cout << "set.size()= " << c.size() << endl;
cout << "set.max_size()= " << c.max_size() << endl; //214748364
string target = get_a_target_string();
{
timeStart = clock();
auto pItem = find(c.begin(), c.end(), target); //比 c.find(...) 慢很多
cout << "std::find(), milli-seconds : " << (clock()-timeStart) << endl;
if (pItem != c.end())
cout << "found, " << *pItem << endl;
else
cout << "not found! " << endl;
}
{
timeStart = clock();
auto pItem = c.find(target); //比 std::find(...) 快很多
cout << "c.find(), milli-seconds : " << (clock()-timeStart) << endl;
if (pItem != c.end())
cout << "found, " << *pItem << endl;
else
cout << "not found! " << endl;
}
}
}
使用map容器
- 不允许元素键重复
-
c[i]=string(buf)
组成pair,允许这样进行插入操作
#include <map>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio> //snprintf()
#include <iostream>
#include <ctime>
namespace jj14
{
void test_map(long& value)
{
cout << "\ntest_map().......... \n";
map<long, string> c;
char buf[10];
clock_t timeStart = clock();
for(long i=0; i< value; ++i)
{
try {
snprintf(buf, 10, "%d", rand());
c[i] = string(buf);
}
catch(exception& p) {
cout << "i=" << i << " " << p.what() << endl;
abort();
}
}
cout << "milli-seconds : " << (clock()-timeStart) << endl;
cout << "map.size()= " << c.size() << endl;
cout << "map.max_size()= " << c.max_size() << endl; //178956970
long target = get_a_target_long();
timeStart = clock();
auto pItem = c.find(target);
cout << "c.find(), milli-seconds : " << (clock()-timeStart) << endl;
if (pItem != c.end())
cout << "found, value=" << (*pItem).second << endl;
else
cout << "not found! " << endl;
c.clear();
}
}
使用unorder_set容器
#include <unordered_set>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio> //snprintf()
#include <iostream>
#include <ctime>
namespace jj15
{
void test_unordered_set(long& value)
{
cout << "\ntest_unordered_set().......... \n";
unordered_set<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));
}
catch(exception& p) {
cout << "i=" << i << " " << p.what() << endl;
abort();
}
}
cout << "milli-seconds : " << (clock()-timeStart) << endl;
cout << "unordered_set.size()= " << c.size() << endl;
cout << "unordered_set.max_size()= " << c.max_size() << endl; //357913941
cout << "unordered_set.bucket_count()= " << c.bucket_count() << endl;
cout << "unordered_set.load_factor()= " << c.load_factor() << endl;
cout << "unordered_set.max_load_factor()= " << c.max_load_factor() << endl;
cout << "unordered_set.max_bucket_count()= " << c.max_bucket_count() << endl;
for (unsigned i=0; i< 20; ++i) {
cout << "bucket #" << i << " has " << c.bucket_size(i) << " elements.\n";
}
string target = get_a_target_string();
{
timeStart = clock();
auto pItem = find(c.begin(), c.end(), target); //比 c.find(...) 慢很多
cout << "std::find(), milli-seconds : " << (clock()-timeStart) << endl;
if (pItem != c.end())
cout << "found, " << *pItem << endl;
else
cout << "not found! " << endl;
}
{
timeStart = clock();
auto pItem = c.find(target); //比 std::find(...) 快很多
cout << "c.find(), milli-seconds : " << (clock()-timeStart) << endl;
if (pItem != c.end())
cout << "found, " << *pItem << endl;
else
cout << "not found! " << endl;
}
}
}
使用unorder_map容器
#include <unordered_map>
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio> //snprintf()
#include <iostream>
#include <ctime>
namespace jj16
{
void test_unordered_map(long& value)
{
cout << "\ntest_unordered_map().......... \n";
unordered_map<long, string> c;
char buf[10];
clock_t timeStart = clock();
for(long i=0; i< value; ++i)
{
try {
snprintf(buf, 10, "%d", rand());
c[i] = string(buf);
}
catch(exception& p) {
cout << "i=" << i << " " << p.what() << endl;
abort();
}
}
cout << "milli-seconds : " << (clock()-timeStart) << endl;
cout << "unordered_map.size()= " << c.size() << endl; //357913941
cout << "unordered_map.max_size()= " << c.max_size() << endl;
long target = get_a_target_long();
timeStart = clock();
//! auto pItem = find(c.begin(), c.end(), target); //map 不適用 std::find()
auto pItem = c.find(target);
cout << "c.find(), milli-seconds : " << (clock()-timeStart) << endl;
if (pItem != c.end())
cout << "found, value=" << (*pItem).second << endl;
else
cout << "not found! " << endl;
}
}
hash_set/hash_map/hash_multiset/hash_multimap
包含
gnu C
的编译器就可以包含的头文件可能需要修改
#include<...>
非标准容器,由于时间的原因,没有放在一起,在C++11大会之前就出现了!测试
/*
以下測試 hash_multiset, hash_multimap 過程中遇到阻礙:
headers <hash_set> 和 <hash_map> 各有兩個,
分別在 ...\4.9.2\include\c++\backward 和 ...\4.9.2\include\c++\ext,
不知要用哪一組!
用 <ext\...> 那一組會有問題
...\4.9.2\include\c++\backward\hashtable.h
[Error] no match for call to '(const hasher {aka const __gnu_cxx::hash<std::basic_string<char> >}) (const key_type&)'
用 <backward\...> 那一組有相同的問題.
so, 放棄測試 (no insertion or push_back or ...).
*/
#include <ext\hash_set>
//...\4.9.2\include\c++\backward\backward_warning.h
//[Warning] #warning This file includes at least one deprecated or antiquated header
//which may be removed without further notice at a future date.
//Please use a non-deprecated interface with equivalent functionality instead.
//For a listing of replacement headers and interfaces, consult the file backward_warning.h.
//To disable this warning use -Wno-deprecated. [-Wcpp]
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio> //snprintf()
#include <iostream>
#include <ctime>
namespace jj11
{
void test_hash_multiset(long& value)
{
cout << "\ntest_hash_multiset().......... \n";
__gnu_cxx::hash_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));
}
catch(exception& p) {
cout << "i=" << i << " " << p.what() << endl;
abort();
}
}
cout << "milli-seconds : " << (clock()-timeStart) << endl;
}
}
//---------------------------------------------------
#include <ext\hash_map>
//...\4.9.2\include\c++\backward\backward_warning.h
//[Warning] #warning This file ... (如上個函數所言)
#include <stdexcept>
#include <string>
#include <cstdlib> //abort()
#include <cstdio> //snprintf()
#include <iostream>
#include <ctime>
namespace jj12
{
void test_hash_multimap(long& value)
{
cout << "\ntest_hash_multimap().......... \n";
__gnu_cxx::hash_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(...
}
catch(exception& p) {
cout << "i=" << i << " " << p.what() << endl;
abort();
}
}
cout << "milli-seconds : " << (clock()-timeStart) << endl;
timeStart = clock();
//! auto ite = c.find(...
cout << "milli-seconds : " << (clock()-timeStart) << endl;
}
}