linked_map

• 下载演示项目 - 52 Kb
• 下载源码 - 5.63 Kb

引言

linked_map 是一个 C++ 模板包装器，用于包装 std::map 关联容器，它

• 当条目插入到 map 中时，它们会以有序的双向链表连接起来。
• 每次您调用 get 或 insert 时，map 对的链表节点都会从其当前位置移除并放置在末尾。

这对于为缓存实现“最近最少使用”规则非常有用。例如，您可能希望将经常访问的客户保留在内存中，并丢弃不经常访问的客户。例如

class customer
{
};

typedef linked_map <std::string,customer,10> customer_cache;

或者甚至让 linked_map 通过覆盖一些虚函数来管理内存的释放

class customer_ptr_cache: public linked_map <std::string,customer *,10>
{
    public:
    ~customer_ptr_cache()
    {
        clear();
    }
    void delete_value( const iterator & i)
    {
        std::pair <bool,customer*> least_used_customer = at ( i );

        delete least_used_customer.second;
    }
}

现在，您可以自由地从缓存中添加和获取客户，并确保内存中不会超过 10 个客户，并且如果缓存必须丢弃客户，它将是“最少使用的”那个。

背景

linked_map 是一个非常简单的模板。它有一个内部的 std::map 来保存您的值，以及一个指向双向链表节点的指针。大致如下

这样，我们可以重新链接链表的节点以跟踪插入/获取/删除顺序，同时保持树的顺序以有效地查找键。以下是在对树的左子节点调用 get() 方法之前和之后的结构示例（为了清晰起见，隐藏了之前的节点）

使用代码

该类的接口是

template <typename K,typename V,typename Pr = std::less<K>,int Cap = -1 >
class linked_map;

boolean insert(const K & k,const V & v);

插入对 <k,v> 并将其对应的链接节点放置在列表的末尾，并返回 true。如果该键已存在于 linked_map 中，则返回 false。

void erase(const iterator & iter);

删除与迭代器 iter 对应的条目。

void erase(const K & k);

删除键为 k 的条目。

void clear();

清除 map 和 linked_list 元素。为每个元素调用 delete_value()。

boolean empty();

如果 linked_map 没有元素，则返回 true，否则返回 false。

std::pair<boolean,V> get(const K & k);

如果存在键为 k 的 <k,v> 条目，则返回 <true,val>，并将其对应的 linked_list 节点移动到末尾。否则返回 <false,val()>。

std::pair<boolean,V> at( const iterator & iter)

如果迭代器 iter 存在 <k,v> 条目，则返回 <true,val>，否则返回 <false,val()>。不更改 linked_list 顺序。

size_t size()

返回 linked_map 中的项目数。

iterator begin()

返回指向 linked_map 的第一个元素（最近最少使用）的迭代器。

iterator end()

返回一个指向 linked_map 的最后一个元素之后的迭代器。

virtual void delete_value(const iterator & i)

将为每个删除操作调用此函数。您可以覆盖它以使用 free 或 delete 释放您的值。请不要从这里更改任何内容，除了值！！ 不要忘记也覆盖析构函数。

关注点

虽然我尽了最大努力测试此代码，但我知道这不是最终作品。我欢迎任何建议、更正、改进等。另外，我想说，在我看来，这种容器非常有用，并且应该成为标准的一部分。也许，linked_set 和 linked_hash (实际上是第一个 hash) 是下一步。

在源代码中，您将找到 linked_map.h 文件和一个 VC++ 6.0 测试项目，我在其中随机调用 insert/get/erase 函数，检查内存泄漏和数据的一致性。