2
我想明白我应该如何实现关联数组赋予一定的时间用于搜索操作，现在我的实现看起来是这样的：如何实现一个轻量级的快速关联数组？
#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 ::矢量我自己的自定义实现）
约束
- 没有使用在所有的STL的原因是不是因为执行不好（快速，通用，全特色）足够，但更多的是因为我的尺寸限制项目（final exe <=65536bytes）相当沉重。即使这个小的实现STL实际上是相当大的使用，因为它是
- 我不需要一个关联数组的完整实现，但只是提供了我已经实现上面的接口（主要问题是线性 - 时间搜索）
- 我不在乎插入/删除方法缓慢，但绝对我希望搜索/查找接近恒定时间
- 我想我需要将上述实现转换为关联数组使用散列表，但我不确定相关的实现细节（每个对象的散列函数，表大小，...）
std :: unordered_map有什么问题？你是否将此视为编程挑战？也许可以解释为什么你需要这个新容器。 –
您应该开始为变量和类型使用有意义的名称。 – moooeeeep
@RichardCritten std :: unordered_map没有错，但我根本不想使用stl。是的，有点...主要原因是学习如何自己实现（学习目的）。 – BPL