Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

Chapter 24. Boost.Unordered

Daniel James

Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt

Table of Contents 目錄

Introduction 簡介
The Data Structure 數據結構
Equality Predicates and Hash Functions 等同性謂詞和散列函數
Comparison with Associative Containers 與關聯式容器的比較
Implementation Rationale 實現原理
Change Log 變更記錄
Reference 參考手冊
Header <boost/unordered_set.hpp>
Header <boost/unordered_map.hpp>
Bibliography 參考書目

For accessing data based on key lookup, the C++ standard library offers std::set, std::map, std::multiset and std::multimap. These are generally implemented using balanced binary trees so that lookup time has logarithmic complexity. That is generally okay, but in many cases a hash table can perform better, as accessing data has constant complexity, on average. The worst case complexity is linear, but that occurs rarely and with some care, can be avoided.
在基於鍵值查找的數據訪問方面,C++標準庫提供了 std::set, std::map, std::multisetstd::multimap。它們通常都是使用平衡樹來實現的,這樣查找時間具有對數複雜度。通常來說這是OK的,不過在多數情況下 散列表 可以表現得更好,平均而言它對數據的訪問是常量複雜度的。最壞情況下的複雜度則是線性的,不過這種情況極少發生,而且留意一下是可以避免的。

Also, the existing containers require a 'less than' comparison object to order their elements. For some data types this is impossible to implement or isn't practical. In contrast, a hash table only needs an equality function and a hash function for the key.
還有,已有的容器要求一個'小於'比較對像來對元素進行排序。對於某些數據,這是不可能實現或不實際的。相比之下,散列表只需要用於鍵值的一個等同性函數和一個散列函數。

With this in mind, the C++ Standard Library Technical Report introduced the unordered associative containers, which are implemented using hash tables, and they have now been added to the Working Draft of the C++ Standard.
對於這一點,C++ 標準庫技術報告 引入了無序關聯式容器,它們是用散列表來實現的,它們已經被加入到 C++標準的工作草案 之中了。

This library supplies an almost complete implementation of the specification in the Working Draft of the C++ Standard.
本庫提供了一個符合 C++標準的工作草案 規範的基本完整的實現。

unordered_set and unordered_multiset are defined in the header <boost/unordered_set.hpp>
unordered_setunordered_multiset 定義於頭文件 <boost/unordered_set.hpp> 中

namespace boost {
    template <
        class Key,
        class Hash = boost::hash<Key>, 
class Pred = std::equal_to<Key>,
class Alloc = std::allocator<Key> >
class unordered_set; template< class Key, class Hash = boost::hash<Key>,
class Pred = std::equal_to<Key>,
class Alloc = std::allocator<Key> >
class unordered_multiset; }

unordered_map and unordered_multimap are defined in the header <boost/unordered_map.hpp>
unordered_mapunordered_multimap 定義於頭文件 <boost/unordered_map.hpp> 中

namespace boost {
    template <
        class Key, class Mapped,
        class Hash = boost::hash<Key>,
        class Pred = std::equal_to<Key>,
        class Alloc = std::allocator<Key> >
    class unordered_map;

    template<
        class Key, class Mapped,
        class Hash = boost::hash<Key>,
        class Pred = std::equal_to<Key>,
        class Alloc = std::allocator<Key> >
    class unordered_multimap;
}

When using Boost.TR1, these classes are included from <unordered_set> and <unordered_map>, with the classes added to the std::tr1 namespace.
在使用 Boost.TR1 時,這些類包含在 <unordered_set><unordered_map> 中,而且被添加到 std::tr1 名字空間中。

The containers are used in a similar manner to the normal associative containers:
這些容器的使用方式與普通的關聯式容器相似:

typedef boost::unordered_map<std::string, int> map;
map x;
x["one"] = 1;
x["two"] = 2;
x["three"] = 3;

assert(x.at("one") == 1);
assert(x.find("missing") == x.end());


But since the elements aren't ordered, the output of:
不過由於其中的元素是無序的,所以以下語句的輸出:

BOOST_FOREACH(map::value_type i, x) {
    std::cout<<i.first<<","<<i.second<<"\n";
}

can be in any order. For example, it might be:
可以是任意順序。例如,它可能是:

two,2
one,1
three,3

To store an object in an unordered associative container requires both an key equality function and a hash function. The default function objects in the standard containers support a few basic types including integer types, floating point types, pointer types, and the standard strings. Since Boost.Unordered uses boost::hash it also supports some other types, including standard containers. To use any types not supported by these methods you have to extend Boost.Hash to support the type or use your own custom equality predicates and hash functions. See the Equality Predicates and Hash Functions section for more details.
要將一個對像保存在無序關聯式容器中,需要有一個鍵值等同性函數和一個散列函數。在標準容器中的缺省函數對像支持少量基本類型,包括整數類型、浮點數類型、指針類型和標準字符串。由於 Boost.Unordered 使用了 boost::hash,所以它還支持一些其它的類型,包括標準容器。要將這些方法用於尚不支持的類型,你必須 擴展 Boost.Hash 以支持該類型,或者使用你自己定制的等同性謂詞和散列函數。更多細節請見 等同性謂詞和散列函數 一節。

There are other differences, which are listed in the Comparison with Associative Containers section.
其它的差別被列在 與關聯式容器的比較 一節中。

Last revised: November 02, 2008 at 13:07:16 GMT


PrevUpHomeNext