欢迎您访问 最编程 本站为您分享编程语言代码，编程技术文章！

热门搜索/Hot Search

您现在的位置是： 首页

用 unordered_set 封装 unordered_map

最编程 2024-10-06 21:52:38
...

目录

前言

unordered_set的封装

代码解读

类模板参数

私有嵌套结构 SetKeyOfT

类型别名

公共成员函数

私有成员

insert 函数的详细解读

unordered_map的封装

代码解读

类模板参数

私有嵌套结构 MapKeyOfT

类型别名

公共成员函数

私有成员

operator[] 函数的详细解读

const 版本的 operator[]

前言

unordered_map 和 unordered_set 在 C++ 标准库中是对哈希表的封装。它们是基于哈希桶（开散列）实现的容器，提供了平均常数时间复杂度的插入、查找和删除操作。

  • unordered_map 是一种关联容器，它存储键值对，其中键是唯一的。它使用哈希表来实现，允许快速检索键对应的值。

  • unordered_set 是一种集合容器，它存储唯一的元素。同样基于哈希表实现，用于快速检查元素是否存在于集合中。

以下是 unordered_map 和 unordered_set 的一些关键特性：

  • 哈希表实现：内部使用哈希表来存储元素，这意味着元素是无序的，且通常不保证元素的顺序。

  • 哈希函数：它们使用哈希函数来确定元素在哈希表中的位置。C++ 标准库为常见数据类型提供了默认的哈希函数，也可以为自定义类型提供专门的哈希函数。

  • 处理冲突：当多个元素散列到同一个位置时，unordered_map 和 unordered_set 使用开散列的方法（如分离链接法）来处理冲突。每个哈希桶位置存储一个链表或另一个数据结构，所有散列到该位置的元素都存储在这个结构中。

  • 性能：理想情况下，unordered_map 和 unordered_set 提供了平均常数时间复杂度的操作（O(1)），但最坏情况下可能会退化到线性时间复杂度（O(n)），这通常发生在哈希表的负载因子过高，需要进行重新哈希时。

因此，可以说 unordered_map 和 unordered_set 是对哈希桶的高层抽象，提供了方便的接口来管理基于哈希的元素集合。

unordered_set的封装


namespace My_unordered_set {
	template <class K, class HashFunc = HashFunc<K>>
	class unordered_set
	{
	private:
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return t;
			}
		};

	public:
		typedef typename HashTable<K, K, SetKeyOfT, HashFunc>::iterator iterator;	//iterator是一个类型，不是实例化的对象
		typedef typename HashTable<K, K, SetKeyOfT, HashFunc>::const_iterator const_iterator;

		iterator begin()
		{
			return _table.begin();
		}

		const_iterator begin() const
		{
			return _table.begin();
		}

		iterator end()
		{
			return _table.end();
		}

		const_iterator end() const
		{
			return _table.end();
		}

		bool erase(const K& key)
		{
			return _table.Erase(key);
		}

		iterator find(const K& key)
		{
			return _table.Find(key);
		}

		pair<const_iterator, bool> insert(const K& key)
		{
			//return _table.Insert(key);	//这里返回这个函数，因为它返回pair<iterator, bool>，而我们需要返回pair<const_iterator, bool>
			auto ret = _table.Insert(key);
										//用返回的迭代器的成员构造一个const迭代器													//ret.second控制返回是否成功
			return make_pair(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);	//构造的这个const_iterator构造完成之后，只能调用const函数（通过Ref与Ptr进行控制）
		}

	private:
		HashTable<K, K, SetKeyOfT, HashFunc> _table;
	};
}

代码解读

这段代码定义了一个名为 My_unordered_set 的命名空间，其中包含一个模板类 unordered_set。这个类模仿了 C++ 标准库中的 unordered_set，用于存储唯一元素，基于哈希表实现。下面是对这个类的详细解读：

类模板参数

  • K：表示集合中存储的元素类型。
  • HashFunc：表示用于计算哈希值的哈希函数类型，默认为 HashFunc<K>。

私有嵌套结构 SetKeyOfT

这个结构体定义了一个函数对象，它返回其参数的引用。在这个上下文中，它似乎没有被使用，因为它总是返回传入的 key。这可能是一个设计上的失误，因为通常在哈希表中，我们需要一个函数来提取键值。

struct SetKeyOfT
{
    const K& operator()(const K& key)
    {
        return key;
    }
};

类型别名

  • iterator 和 const_iterator：这两个类型别名分别用于定义普通迭代器和常量迭代器。它们是基于 HashTable 类的迭代器类型。

typedef typename HashTable<K, K, SetKeyOfT, HashFunc>::iterator iterator;
typedef typename HashTable<K, K, SetKeyOfT, HashFunc>::const_iterator const_iterator;

公共成员函数

  • begin() 和 begin() const：返回一个指向集合中第一个元素的迭代器。
  • end() 和 end() const：返回一个指向集合中最后一个元素之后位置的迭代器。
  • erase(const K& key)：从集合中删除指定的元素，如果元素存在则返回 true，否则返回 false。
  • find(const K& key)：在集合中查找指定的元素，并返回一个迭代器指向该元素，如果未找到则返回 end()。
  • insert(const K& key)：将元素插入集合中，如果元素已存在则不插入，并返回一个 pair，包含一个迭代器指向已存在的或新插入的元素，以及一个布尔值表示插入是否成功。

私有成员

  • _table：这是一个 HashTable 类的实例，用于实际存储集合中的元素。

insert 函数的详细解读

在 insert 函数中，我们尝试将一个元素插入到哈希表中。这里有一个需要注意的地方：

auto ret = _table.Insert(key);
return make_pair(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);

这里，_table.Insert(key) 返回一个 pair<iterator, bool>，其中 iterator 是 HashTable 的迭代器。为了返回 pair<const_iterator, bool>，我们需要将普通的迭代器转换为常量迭代器。这是通过构造一个 const_iterator 来完成的，它接收与普通迭代器相同的参数：节点指针 _node，指向哈希表的指针 _pht，以及哈希值 _hashi。

总的来说，这个 unordered_set 类是一个简化版的哈希集合实现，它基于一个未在此代码段中定义的 HashTable 类。这个类提供了基本的集合操作，如插入、查找和删除元素。

unordered_map的封装


namespace My_unordered_map
{
	template<typename K, typename V, class HashFunc = HashFunc<K>>		//map是K/V结构
	class unordered_map
	{
	private:
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv) 
			{
				return kv.first;
			}
		}

	public:
		typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, HashFunc>::iterator iterator;
		typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, HashFunc>::const_iterator const_iterator;

		iterator begin()
		{
			return _ht.begin();
		}

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

		const_iterator end() const
		{
			return _ht.end();
		}

		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}

		iterator find(const K& key)
		{
			return _ht.Find(key);
		}

		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _ht.Insert(kv);
		}

		V& operator[](const K& key)
		{
			pair<iterator, bool>  ret = _table.Insert(pair<K, V>(key, V()));	//总是先执行一次插入
			return ret.first->second;	//使用迭代器重载的操作符（迭代器行为类似节点指针）
		}

		const V& operator[](const K& key) const
		{
			pair<iterator, bool>  ret = _table.Insert(pair<K, V>(key, V()));	//总是先执行一次插入
			return ret.first->second;	//使用迭代器重载的操作符（迭代器行为类似节点指针）
		}

	private:
		HashTable<K, pair<const K, V>, MapKeyOfT, HashFunc> _table;	//借助MapKeyOfT类，获取到的键值K是const修饰过的

	};

}

代码解读

这段代码定义了一个名为 My_unordered_map 的命名空间，其中包含一个模板类 unordered_map。这个类模仿了 C++ 标准库中的 unordered_map，用于存储键值对，其中键是唯一的，基于哈希表实现。下面是对这个类的详细解读：

类模板参数

  • K：表示键的类型。
  • V：表示值的类型。
  • HashFunc：表示用于计算键的哈希值的哈希函数类型，默认为 HashFunc<K>。

私有嵌套结构 MapKeyOfT

这个结构体定义了一个函数对象，它用于从一个键值对 pair<K, V> 中提取键 K。

struct MapKeyOfT
{
    const K& operator()(const pair<K, V>& kv)
    {
        return kv.first;
    }
}

类型别名

  • iterator 和 const_iterator：这两个类型别名分别用于定义普通迭代器和常量迭代器。它们是基于 HashTable 类的迭代器类型。

typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, HashFunc>::iterator iterator;
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, HashFunc>::const_iterator const_iterator;

公共成员函数

  • begin() 和 end()：返回一个指向映射中第一个键值对的迭代器。
  • begin() const 和 end() const：返回一个指向映射中第一个键值对的常量迭代器。
  • erase(const K& key)：从映射中删除指定键的键值对，如果键存在则返回 true，否则返回 false。
  • find(const K& key)：在映射中查找指定键的键值对，并返回一个迭代器指向该键值对，如果未找到则返回 end()。
  • insert(const pair<K, V>& kv)：将键值对插入映射中，如果键已存在则不插入，并返回一个 pair，包含一个迭代器指向已存在的或新插入的键值对，以及一个布尔值表示插入是否成功。
  • operator[](const K& key)：允许通过键直接访问或插入值。如果键不存在，则插入一个默认构造的值。

私有成员

  • _table：这是一个 HashTable 类的实例，用于实际存储映射中的键值对。

operator[] 函数的详细解读

operator[] 函数允许通过键直接访问或修改映射中的值。如果键不存在，它会插入一个默认构造的值。

V& operator[](const K& key)
{
    pair<iterator, bool> ret = _table.Insert(pair<K, V>(key, V())); // 总是先执行一次插入
    return ret.first->second; // 使用迭代器重载的操作符（迭代器行为类似节点指针）
}

在这个函数中，如果键 key 不存在于映射中，它会创建一个默认构造的值 V() 并与键一起插入到哈希表中。Insert 函数返回一个 pair<iterator, bool>，其中 iterator 指向新插入的键值对或已存在的键值对，bool 表示是否成功插入了新的键值对。然后，我们通过 ret.first->second 返回值的引用。

注意，这里有一个潜在的问题：如果 V 类型没有默认构造函数，或者默认构造函数的行为不是期望的，那么这段代码将无法正常工作。

const 版本的 operator[] 

const V& operator[](const K& key) const

这个函数与非常量版本相同，但是它返回一个常量引用，这意味着不能通过这个函数修改值。然而，这段代码似乎有一个错误，因为在一个常量成员函数中调用 Insert 是不允许的，因为 Insert 可能会修改映射。正确的做法是在非常量版本中插入元素，然后在常量版本中仅返回已存在元素的引用。

总结来说，这个 unordered_map 类是一个简化版的哈希映射实现，它基于一个未在此代码段中定义的 HashTable 类。这个类提供了基本的映射操作，如插入、查找、删除键值对，以及通过键直接访问值。

上一篇： python 的可迭代对象包含哪些内容？

下一篇： 长列表加载性能优化

推荐阅读