STL — hash_map/hash_setソースコードプロファイリング

hash_map/hash_setソースコードプロファイリング
STLは複雑度とインタフェースのみを規範化し、実現方法は規範化されていないが、STL setの多くはRB_Tree. SGIは、STL規格に加えて、いわゆるhash_を提供するset
で、
hashTable
の下地メカニズムhash_のためsetが供給する操作インタフェースは、hashTableが提供するので、ほとんどのhash_set操作動作は、いずれも呼び出しのみです
hashTableの
操作
行為にすぎない.
setを用いたのは,要素をすばやく検索できることであり,その下層がRB_であってもTreeまたはhashtableはいずれもタスクを達成できますが、RB_に注意してください.treeには自動ソート機能があります
を選択し、
hashtable
いいえ、反応した結果、setの要素は自動的にソートする機能があり、hash_setいいえ.コードを直接見てみましょう.

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
// 4         :
//vlalue :        hashFcn : hash function       ExtracKey :            
//Alloc ：           .
template ,
class EqualKey = equal_to,
class Alloc = alloc>
#else
template 
#endif
class hash_set
{
private:
	//   set          ， set      .
	//     identiy<>     
	typedef hashtable,
		EqualKey, Alloc> ht;
	ht rep;

public:
	//      .
	typedef typename ht::key_type key_type;
	typedef typename ht::value_type value_type;
	typedef typename ht::hasher hasher;
	typedef typename ht::key_equal key_equal;

	typedef typename ht::size_type size_type;
	typedef typename ht::difference_type difference_type;
	typedef typename ht::const_pointer pointer;
	typedef typename ht::const_pointer const_pointer;
	typedef typename ht::const_reference reference;
	typedef typename ht::const_reference const_reference;

	typedef typename ht::const_iterator iterator;
	typedef typename ht::const_iterator const_iterator;

	hasher hash_funct() const { return rep.hash_funct(); }
	key_equal key_eq() const { return rep.key_eq(); }

public:
	//       100   ，  hash table            .
	hash_set() : rep(100, hasher(), key_equal()) {}
	explicit hash_set(size_type n) : rep(n, hasher(), key_equal()) {}
	hash_set(size_type n, const hasher& hf) : rep(n, hf, key_equal()) {}
	hash_set(size_type n, const hasher& hf, const key_equal& eql)
		: rep(n, hf, eql) {}

	//     ，    insert_unique()，       .
	hash_set(const value_type* f, const value_type* l)
		: rep(100, hasher(), key_equal()) {
		rep.insert_unique(f, l);
	}
	hash_set(const value_type* f, const value_type* l, size_type n)
		: rep(n, hasher(), key_equal()) {
		rep.insert_unique(f, l);
	}
	hash_set(const value_type* f, const value_type* l, size_type n,
		const hasher& hf)
		: rep(n, hf, key_equal()) {
		rep.insert_unique(f, l);
	}
	hash_set(const value_type* f, const value_type* l, size_type n,
		const hasher& hf, const key_equal& eql)
		: rep(n, hf, eql) {
		rep.insert_unique(f, l);
	}

	hash_set(const_iterator f, const_iterator l)
		: rep(100, hasher(), key_equal()) {
		rep.insert_unique(f, l);
	}
	hash_set(const_iterator f, const_iterator l, size_type n)
		: rep(n, hasher(), key_equal()) {
		rep.insert_unique(f, l);
	}
	hash_set(const_iterator f, const_iterator l, size_type n,
		const hasher& hf)
		: rep(n, hf, key_equal()) {
		rep.insert_unique(f, l);
	}
	hash_set(const_iterator f, const_iterator l, size_type n,
		const hasher& hf, const key_equal& eql)
		: rep(n, hf, eql) {
		rep.insert_unique(f, l);
	}

public:
	//      ，  hash table   ，      .
	size_type size() const { return rep.size(); }
	size_type max_size() const { return rep.max_size(); }
	bool empty() const { return rep.empty(); }
	void swap(hash_set& hs) { rep.swap(hs.rep); }
	friend bool operator== __STL_NULL_TMPL_ARGS(const hash_set&,
		const hash_set&);

	iterator begin() const { return rep.begin(); }
	iterator end() const { return rep.end(); }

public:
	pair insert(const value_type& obj)
	{
		pair p = rep.insert_unique(obj);
		return pair(p.first, p.second);
	}
#ifdef __STL_MEMBER_TEMPLATES
	template 
	void insert(InputIterator f, InputIterator l) { rep.insert_unique(f, l); }
#else
	void insert(const value_type* f, const value_type* l) {
		rep.insert_unique(f, l);
	}
	void insert(const_iterator f, const_iterator l) { rep.insert_unique(f, l); }
#endif /*__STL_MEMBER_TEMPLATES */
	pair insert_noresize(const value_type& obj)
	{
		pair p = rep.insert_unique_noresize(obj);
		return pair(p.first, p.second);
	}

	iterator find(const key_type& key) const { return rep.find(key); }

	size_type count(const key_type& key) const { return rep.count(key); }

	pair equal_range(const key_type& key) const
	{
		return rep.equal_range(key);
	}

	size_type erase(const key_type& key) { return rep.erase(key); }
	void erase(iterator it) { rep.erase(it); }
	void erase(iterator f, iterator l) { rep.erase(f, l); }
	void clear() { rep.clear(); }

public:
	void resize(size_type hint) { rep.resize(hint); }
	size_type bucket_count() const { return rep.bucket_count(); }
	size_type max_bucket_count() const { return rep.max_bucket_count(); }
	size_type elems_in_bucket(size_type n) const
	{
		return rep.elems_in_bucket(n);
	}
};

template 
inline bool operator==(const hash_set& hs1,
	const hash_set& hs2)
{
	return hs1.rep == hs2.rep;
}

hash_mapのソースコード実装:

//   hash<>  function object     
template ,
class EqualKey = equal_to,
class Alloc = alloc>
#else
template 
#endif
class hash_map
{
private:
	//     select1st<>    .
	typedef hashtable, Key, HashFcn,
		select1st >, EqualKey, Alloc> ht;
	ht rep; //     hash table  .

public:
	//       100   ，  hash table            .
	typedef typename ht::key_type key_type;
	typedef T data_type;
	typedef T mapped_type;
	typedef typename ht::value_type value_type;
	typedef typename ht::hasher hasher;
	typedef typename ht::key_equal key_equal;

	typedef typename ht::size_type size_type;
	typedef typename ht::difference_type difference_type;
	typedef typename ht::pointer pointer;
	typedef typename ht::const_pointer const_pointer;
	typedef typename ht::reference reference;
	typedef typename ht::const_reference const_reference;

	typedef typename ht::iterator iterator;
	typedef typename ht::const_iterator const_iterator;

	hasher hash_funct() const { return rep.hash_funct(); }
	key_equal key_eq() const { return rep.key_eq(); }

public:
	hash_map() : rep(100, hasher(), key_equal()) {}
	explicit hash_map(size_type n) : rep(n, hasher(), key_equal()) {}
	hash_map(size_type n, const hasher& hf) : rep(n, hf, key_equal()) {}
	hash_map(size_type n, const hasher& hf, const key_equal& eql)
		: rep(n, hf, eql) {}
	//           insert_unique()，       .
	hash_map(const value_type* f, const value_type* l)
		: rep(100, hasher(), key_equal()) {
		rep.insert_unique(f, l);
	}
	hash_map(const value_type* f, const value_type* l, size_type n)
		: rep(n, hasher(), key_equal()) {
		rep.insert_unique(f, l);
	}
	hash_map(const value_type* f, const value_type* l, size_type n,
		const hasher& hf)
		: rep(n, hf, key_equal()) {
		rep.insert_unique(f, l);
	}
	hash_map(const value_type* f, const value_type* l, size_type n,
		const hasher& hf, const key_equal& eql)
		: rep(n, hf, eql) {
		rep.insert_unique(f, l);
	}

	hash_map(const_iterator f, const_iterator l)
		: rep(100, hasher(), key_equal()) {
		rep.insert_unique(f, l);
	}
	hash_map(const_iterator f, const_iterator l, size_type n)
		: rep(n, hasher(), key_equal()) {
		rep.insert_unique(f, l);
	}
	hash_map(const_iterator f, const_iterator l, size_type n,
		const hasher& hf)
		: rep(n, hf, key_equal()) {
		rep.insert_unique(f, l);
	}
	hash_map(const_iterator f, const_iterator l, size_type n,
		const hasher& hf, const key_equal& eql)
		: rep(n, hf, eql) {
		rep.insert_unique(f, l);
	}
#endif /*__STL_MEMBER_TEMPLATES */

public:
	//        hash table    ，      .
	size_type size() const { return rep.size(); }
	size_type max_size() const { return rep.max_size(); }
	bool empty() const { return rep.empty(); }
	void swap(hash_map& hs) { rep.swap(hs.rep); }
	friend bool
		operator== __STL_NULL_TMPL_ARGS(const hash_map&, const hash_map&);

	iterator begin() { return rep.begin(); }
	iterator end() { return rep.end(); }
	const_iterator begin() const { return rep.begin(); }
	const_iterator end() const { return rep.end(); }

public:
	pair insert(const value_type& obj)
	{
		return rep.insert_unique(obj);
	}
#ifdef __STL_MEMBER_TEMPLATES
	template 
	void insert(InputIterator f, InputIterator l) { rep.insert_unique(f, l); }
#else
	void insert(const value_type* f, const value_type* l) {
		rep.insert_unique(f, l);
	}
	void insert(const_iterator f, const_iterator l) { rep.insert_unique(f, l); }
#endif /*__STL_MEMBER_TEMPLATES */
	pair insert_noresize(const value_type& obj)
	{
		return rep.insert_unique_noresize(obj);
	}

	iterator find(const key_type& key) { return rep.find(key); }
	const_iterator find(const key_type& key) const { return rep.find(key); }

	T& operator[](const key_type& key) {
		return rep.find_or_insert(value_type(key, T())).second;
	}

	size_type count(const key_type& key) const { return rep.count(key); }

	pair equal_range(const key_type& key)
	{
		return rep.equal_range(key);
	}
	pair equal_range(const key_type& key) const
	{
		return rep.equal_range(key);
	}

	size_type erase(const key_type& key) { return rep.erase(key); }
	void erase(iterator it) { rep.erase(it); }
	void erase(iterator f, iterator l) { rep.erase(f, l); }
	void clear() { rep.clear(); }

public:
	void resize(size_type hint) { rep.resize(hint); }
	size_type bucket_count() const { return rep.bucket_count(); }
	size_type max_bucket_count() const { return rep.max_bucket_count(); }
	size_type elems_in_bucket(size_type n) const
	{
		return rep.elems_in_bucket(n);
	}
};

template 
inline bool operator==(const hash_map& hm1,
	const hash_map& hm2)
{
	return hm1.rep == hm2.rep;
}