d - 如何删除关联数组中最近最少访问的键？

Question

我有一个限制为 x 个键的关联数组，并且想要删除最近最少访问的键以添加另一个键。我在 mintl 中找到了 HashAA，它可以在 D1 中完成这项工作，但我没有为 D2 找到任何东西。现在有什么支持这一点的，还是我需要维护第二个数组才能完成工作？

Answer 1

我没有真正的答案，但我认为在几分钟内尝试实现它会很有趣（这可能效率很低，而且可能有问题）：

import std.stdio;
import std.traits;

struct MyHash(AA, size_t Limit)
    if (isAssociativeArray!AA)
{
    alias KeyType!AA Key;
    alias ValueType!AA Value;

    void opIndexAssign(Value value, Key key)
    {
        if (hash.length >= Limit)
        {
            Key leastUsed = leastUsedKey;
            hash.remove(leastUsed);
            counts.remove(leastUsed);
        }

        hash[key] = value;
    }

    Value opIndex(Key key)
    {
        counts[key]++;
        return hash[key];
    }

    Value[Key] hash;
    alias hash this;

private:

    @property Key leastUsedKey()
    {
        Key result;
        size_t maxCount = size_t.max;

        foreach (key; hash.byKey)
        {
            if (auto count = key in counts)
            {
                if (*count < maxCount)
                {
                    maxCount = *count;
                    result = key;
                }
            }
            else
            {
                return key;
            }
        }

        return result;
    }

    size_t[Key] counts;
}

// just to avoid declaring variables in main()
@property void consume(int key) { }

void main()
{
    MyHash!(int[int], 3) hash;

    hash[0] = 0;
    hash[1] = 0;
    hash[2] = 0;

    writeln(hash.keys);

    hash[2].consume;
    hash[5] = 0;

    writeln(hash.keys); // 2 stays, 5 added

    hash.clear();
    hash[0] = 0;
    hash[1] = 0;
    hash[2] = 0;

    hash[0].consume;
    hash[1].consume;
    hash[1].consume;
    hash[2].consume;
    hash[2].consume;
    hash[2].consume;

    hash[5] = 0;
    writeln(hash);  // (0 removed)
}

Answer 2

内置的 AA 将在需要时重新散列以适应更多元素，大小不固定，并且不会跟踪您访问或添加元素的方式，并且由于该语言内置了 AA，备用散列表实现将相对较少（大多数人只使用内置的 AA）。

因此，我非常确定您需要自己执行此操作 - 可能是通过围绕内置 AA 类型创建一个包装器并让包装器跟踪对它的所有访问，以便它知道哪个键被访问最少最近。

您可以随时查看dcollections以了解一些备用容器实现（并且 IIRC中确实有一个哈希表，但我怀疑它是否符合您的要求）。就个人而言，我什至从未听说过按照您希望的方式运行的哈希表，所以我希望您正在寻找的内容至少有些不正常。但是创建一个围绕 AA 的包装器应该足够简单，它可以按照您想要的方式运行。