C++ STL Unordered Container無序容器

頭檔案：

<unordered_set>

、

<unordered_map>

Unordered容器的能力

所有标準化無序容器類都以哈希表為基礎.

關于再散列,有兩種實作政策：

1.傳統做法:在單一insert或erase動作出現時，有時候會發生一次内部資料重新組織

2.遞進式做法是:漸進改變bucket或slot數量

對于每個将被存放的元素，哈希函數會把key映射至哈希表内的某個bucket中.每個bucket管理一個單向linked list.

建立和控制Unordered容器

構造函數和析構函數

布局操作

提供你自己的Hash函數

template <typename T>
class Hash
{
};
template <>
class Hash<std::string>//string的顯式具體化
{
public:
	size_t operator()(const std::string & key)
	{
		size_t hashval = 0;
		for (char ch : key)
			hashval = 37 * hashval + ch;
		return hashval;
	}
};
template<>
class Hash<int>//int的顯式具體化
{
public:
	size_t operator()(int item)//除留餘數法
	{
		size_t i = item;
		return i;
	}

};
unordered_set<int,Hash<int>>custset;
           

如果不願意傳遞一個function obejct成為容器類型的一部分，也可以傳遞一個hash函數作為構造函數實參:

size_t customer_hash_func(const Customer& c)
{
	return...
}
unordered_set<Customer, size_t(*)(const Customer&)>custset(20,customer_hash_func);
           

如果沒有給予特殊的哈希函數，預設的哈希函數是

hash<>

,可以應付整數類型、浮點數類型、指針、string、若幹特殊類型,這些之外的其他類型，你就必須提供你自己的哈希函數

比較好的做法是，使用由boost提供的hash函數和一個便利接口

提供你自己的等價準則

作為無序容器類型的第三或第四模闆參數，你可以傳遞等價準則，預設使用的是

equal_to<>

,以

operator ==

進行比較，你可以為你自己的類型提供

operator==

比如:

Unordered容器的其他操作

非更易型操作

查找操作

Unordered容器對快速查找元素有着優化，在一個擁有1000個元素的集合中查找，平均隻需要一次動作，是以你應該用容器自帶的find算法.

指派操作

疊代器相關函數和元素通路

無序容器提供的疊代器隻保證是前些疊代器，不支援bidirectional 或random- access.

在

unordered set/multiset

内移除元素，你唯一可以使用的是容器提供的成員函數

插入和移除操作

set傳回的是pair結構，second成員表示安插是否成功 first成員表示新插元素的位置或既有元素的位置.

有三種不同的方法可以将value傳入unordered map或unordered multimap内:

1.value_type:

unordered_map<string,float>coll;
coll.insert(unordered_map<string,float>::value_type("otto",22.3));
coll.insert(decltype(coll)::value_type("otto",22.3));
           

2.pair<>:

unordered_map<string,float>coll;
coll.insert(pair<string,float>("otto",22.3));
           

3.make_pair():

unordered_map<string,float>coll;
coll.insert(make_pair("otto",22.3));
           

使用emplace()安插新元素，可以這樣做:

unordered_map<string,complex<float>>m;
m.emplace(std::piecewise_construct, make_tuple("hello"),make_tuple("3.4,7.8"));
           

想要移除某個值為value的元素，可以這樣做:

unordered_map<string,float>coll;
coll.erase(key);
           

如果multimap内含重複元素，你無法使用erase删除重複元素中的第一個，但是可以這樣做:

unordered_multimap<string,float>coll;
auto pos = coll.find(key);
if(pos!= coll.end())
{
coll.erase(pos);
}
           

Bucket接口

使用例子：

template<typename T>
inline void PRINT_ELEMENTS(const T & coll, const std::string & optstr = "")
{
	std::cout << optstr;
	for (const auto & elem : coll)
	{
		std::cout << elem << ' ';
	}
	std::cout << std::endl;
}


template<typename T1, typename T2>
ostream& operator << (std::ostream& strm, const pair<T1, T2>& p)
{
	return strm << "[" << p.first << "," << p.second << "]";
}
template<typename T>
void printHashTableState(const T& cont)
{
	cout << "size:			  " << cont.size() << "\n";
	cout << "buckets:		  " << cont.bucket_count() << "\n";
	cout << "load factor:	  " << cont.load_factor() << "\n";
	cout << "max load factor: " << cont.max_load_factor() << "\n";
	if (typeid(typename iterator_traits<typename T::iterator>::iterator_category) == typeid(bidirectional_iterator_tag))
	{
		cout << "chaining style: doubly-likned" << "\n";
	}
	else
	{
		cout << "chaining style: singly-linked" << "\n";
	}
	cout << "data: " << "\n";
	for (auto idx = 0; idx != cont.bucket_count(); ++idx)
	{
		cout << "b[" << setw(2) << idx << "]: ";
		for (auto pos = cont.begin(idx); pos != cont.end(idx); ++pos)
		{
			cout << *pos << " ";
		}
		cout << endl;
	}
	cout << endl;
}
int main()
{
	unordered_set<int>intset = { 1,2,3,5,7,11,13,17,19 };
	printHashTableState(intset);
	intset.insert({ -7,17,33,4 });
	printHashTableState(intset);

}
           

這是另一個例子：

unordered_multimap<string, string>dict = { {"day","Tag"},{"strange","fremd"}, {"car","Auto"}, {"Smart","elegant"},
											   {"trait","Merkmal"}, {"strange","seltsam"} };
	printHashTableState(dict);
	dict.insert({ {"smart","raffiniert"},{"smart","klug"},
		{"clever","raffiniert"} });
	printHashTableState(dict);
	dict.max_load_factor(0.7);
	printHashTableState(dict);
           

使用Unordered Map作為Associative Array

Unordered容器的運用執行個體：

int main()
{

	unordered_set<int>coll = { 1,2,3,5,7,11,13,17,19,77 };
	PRINT_ELEMENTS(coll);
	coll.insert({ -7,17,33,-11,17,19,1,13 });
	PRINT_ELEMENTS(coll);
	coll.erase(33);
	if (coll.find(19) != coll.end())
	{
		cout << "19 is available" << endl;
	}
	unordered_set<int>::iterator pos;
	for (pos = coll.begin(); pos != coll.end();)
	{
		if (*pos < 0)
		{
			pos = coll.erase(pos);
		}
		else
		{
			++pos;
		}
	}
	PRINT_ELEMENTS(coll);

}