Geek asks and answers

64-bit array operation using C / C ++

I have a critical application where I need such a data structure like an array A. His keys 0, 1, 2,...and his meanings are uint64_t excellent values. I need two operations constant :

1. Given i, return A[i];
2. Given val, return i such that A[i] == val

I prefer not to use a hash table. Since I tried GLib GHashTable , it took about 20 minutes to load 60 million values ​​into the hash table (if I delete the insert statement, it only took about 6 seconds). The time for my application is unacceptable. Or maybe someone would recommend other hash tables? I tried uthash.c, it crashed immediately.

I also tried SDArray , but that seems to be wrong.

Does anyone know any data structure that fits my requirements? Or any efficient hash table implementations? I prefer to use C / C ++.

Thank.

+5
source share
2 answers

In general, for this task you will need two hash tables. As you know, hash tables give you a key at the expected constant time. Value search Iterates through the entire data structure, since the value information is not encoded in the hash lookup table.

: () . , "". , .

-: ++ 11 std::unordererd_map.

(, , , const-correctness, ..):

std::unordered_map<K,T> kvMap; // hash table for forward search
std::unordered_map<T,K> vkMap; // hash table for backward search

void insert(std::pair<K,T> item) {
    kvMap.insert(item);
    vkMap.insert(std::make_pair(item.second, item.first));
}

// expected O(1)
T valueForKey(K key) {
    return kvMap[key];
}

// expected O(1)
K keyForValue(T value) {
    return vkMap[value];
}

++ 11 "" - , "" -. .

: , , "". - , ( ) -, -.

+6

(, ), O (1) , O (log n)

vector<uint64_t> values;
vector<size_t> keys

values.reserve(maxSize); // do memory reservation first, so reallocation doesn't occur during reading of data
keys.reserve(maxSize); // do memory reservation first, so reallocation doesn't occur during reading of data


values[keyRead] = data;
keys[valueRead] = key;


data = values[currentKey];
key = keys[currentData];
0

More articles:


All Articles