c++ - 如何实现一个轻量级的快速关联数组？

Question

我试图理解我应该如何实现一个关联数组，它为搜索操作提供恒定的时间，现在我的实现如下所示:

#include <iostream>
#include <vector>
#include <string>
using namespace std;

template <class Key, class Value> class Dict {
  private:
    typedef struct Item {
        Value value;
        Key key;
    } Item;
    vector<Item> _data;

  public:
    void clear() {
        _data.clear();
    }

    long size() {
        return _data.size();
    }

    bool is_item(Key key) {
        for (int i = 0; i < size(); i++) {
            if (_data[i].key == key) return true;
        }
        return false;
    }

    bool add_item(Key key, Value value) {
        if (is_item(key)) return false;
        Item new_item;
        new_item.key = key;
        new_item.value = value;
        _data.push_back(new_item);
        return true;
    }

    Value &operator[](Key key) {
        for (int i = 0; i < size(); i++) {
            if (_data[i].key == key) return _data[i].value;
        }
        long idx = size();
        Item new_item;
        new_item.key = key;
        _data.push_back(new_item);
        return _data[idx].value;
    }

    Key get_key(long index) {
        if (index < 0) index = 0;
        for (int i = 0; i < size(); i++)
            if (i == index) return _data[i].key;
        return NULL;
    }

    Value &operator[](long index) {
        if (index < 0) index = 0;
        for (int i = 0; i < size(); i++) {
            if (i == index) return _data[i].value;
        }
        return _data[0].value;
    }
};

一个简单的测试:

class Foo {
  public:
    Foo(int value) {
        _value = value;
    }

    int get_value() {
        return _value;
    }

    void set_value(int value) {
        _value = value;
    }

  private:
    int _value;
};

template <class Key, class Value> void print_dict(Dict<Key, Value> &dct) {
    if (!dct.size()) {
        printf("Empty Dict");
    }
    for (int i = 0; i < dct.size(); i++) {
        printf("%d%s", dct[dct.get_key(i)], i == dct.size() - 1 ? "" : ", ");
    }
    printf("\n");
}

int main(int argc, char *argv[]) {
    printf("\nDict tests\n------------\n");
    Dict<string, int> dct;

    string key1("key1");
    string key2("key2");
    string key3("key3");
    dct["key1"] = 100;
    dct["key2"] = 200;
    dct["key3"] = 300;
    printf("%d %d %d\n", dct["key1"], dct["key2"], dct["key3"]);
    printf("%d %d %d\n", dct[key1], dct[key2], dct[key3]);
    print_dict(dct);
    dct.clear();
    print_dict(dct);

    Dict<Foo *, int> dct2;
    Foo *f1 = new Foo(100);
    Foo *f2 = new Foo(200);
    dct2[f1] = 101;
    dct2[f2] = 202;
    print_dict(dct2);
}

事情是这样的，现在搜索操作是线性时间，我希望它成为常数时间，我想知道一种简单/轻量级的方法来实现这一点。

我看过 hashtables是一个可能的选择，但我宁愿不必为每个对象实现哈希函数。也许类似于 unordered_map ... 不知道。

任何人都可以提供一些想法或者提供一个简单的轻量级实现来实现我在这里想要实现的目标吗？

在这个虚构的例子中，我使用 std::vector 来避免使问题变得比实际问题更大更复杂，但我的真实用例根本不会使用 STL(即:我会编写我自己的 std::vector 自定义实现)

约束

• 根本不使用 STL 的原因不是因为该实现不够好(快速、通用、功能齐全)，而是因为对于我的大小受限项目(final exe <=65536bytes)来说它非常繁重。即使是 STL 的这个小实现实际上很大，无法按原样使用
• 我不需要关联数组的完整实现，只需提供我已经在上面实现的接口(interface)(主要问题是线性时间搜索)
• 我不关心插入/删除方法是否缓慢，但我绝对希望搜索/查找接近恒定时间
• 我想我需要使用哈希表将上述实现转换为关联数组，但我不确定相关的实现细节(每个对象的哈希函数、表的大小……)

Answer 1

让我解决您在问题中提出的一些问题。

Here's the thing, right now the search operation is linear time and I'd like it to become constant time and I'm wondering about a simple/lightweight way to achieve this.

实现此目的的一种简单的轻量级方法，即拥有关联数组(又名键值存储)，是使用标准库提供的方法。

您正在使用最新版本的 C++ 进行编码，您处于幸运的位置，标准库实际上提供了一个满足您的恒定时间要求的库:

• http://en.cppreference.com/w/cpp/container/unordered_map

如今，作为任何像样的编译器的标准库的一部分提供的数据结构的实现可能比您能想到的任何东西都要好。 (或者你为什么要给我代码？)。

I've seen hashtables are a possible option but I'd prefer not having to implement a hash function per object. Maybe something similar to an unordered_map... dunno.

std::unordered_map 实际上 是一个哈希表，正如您在文档中看到的那样，它采用哈希函数。正如您在文档中看到的那样，有许多类型的特化已经可用，可以帮助您为自定义对象类型派生自定义哈希函数:

• http://en.cppreference.com/w/cpp/utility/hash

Could anyone give some ideas or maybe providing a simple lightweight implementation of what I'm trying to achieve here?

只需查看 std::unordered_map 的示例代码，了解它是如何使用的。如果您担心性能，请不要忘记测量。如果你真的想在哈希表的实现上消耗一些输入，我喜欢这些关于 Python 字典的演讲:

• https://www.youtube.com/watch?v=C4Kc8xzcA68
• https://www.youtube.com/watch?v=p33CVV29OG8

另请查看维基百科页面(如果您还没有):

• https://en.wikipedia.org/wiki/Associative_array

In this fictional example I'm using std::vector to avoid making the question bigger and more complex than what it is but my the real use-case won't be using the STL at all (ie: i'll be coding my own custom implementation of std::vector)

除非您出于教育/娱乐目的这样做，否则不要这样做。不要以你的努力为耻on the shoulders of giants .即标准库wasn't invented in your project不是问题。