A.3 (C++)

在课堂上讲的哈希表的基础上，写一个以整数为键的只有一个类型参数的哈希表类, HT<E>。
另外，请添加一个函数 getKeys，该函数返回所有二元组(tuple)中的键(key)。

HINT：尝试通过添加额外代码(<10行)完成该题。

EXAMPLE INPUT

2000

EXAMPLE OUTPUT

2000
text51
text151
text251
text351
text451
text551
text651
text751
text851
text951
text1051
text1151
text1251
text1351
text1451
text1551
text1651
text1751
text1851
text1951
0

主程序 (不能修改)

#include "source.cpp"

#include <iostream>
#include <sstream>
using namespace std;

int main() {
    int test_count;
    cin >> test_count;
    HT<string> map;
    for (int i = 0; i < test_count; ++ i) {
        stringstream ss;
        ss << "text" << (1 + i);
        map.put(i * 10, ss.str());
    }
    cout << map.size() << endl;
    for (int i = 0; i < test_count; ++ i) {
        if (! map.containsKey(i * 10)) {
            cout << "bad" << endl;
        }
        else if (i % 100 == 50) {
            cout << map[i * 10] << endl;
        }
    }
    vector<int> keys = map.getKeys();
    for (int i = 0; i < keys.size(); ++ i) {
        map.remove(keys[i]);
    }
    cout << map.size() << endl;
}

来自Mitte的参考答案
Mitte

#include<vector>
using namespace std;

vector<int> Keylist;
template <typename V>
class Tuple{
public:
    V val;
    int key;
    
};

template <typename V>
class HT
{
    vector<Tuple<V>> tuples;
    size_t index0fKey(const int & key) const{
        for(int i=0;i<tuples.size();i++)
            if(tuples[i].key==key) return i;
        return -1;
    }
public:
    bool containsKey(const int & key) const{
        return index0fKey(key) != -1;
    }
    const V & operator [](const int & key) const{
        size_t index = index0fKey(key);
        return tuples[index].val;
    }
    void put(const int & key,const V & val){
        size_t index = index0fKey(key);
        if(index == -1){
            Tuple<V> tuple;
            tuple.key=key;
            tuple.val=val;
            tuples.push_back(tuple);
        }
        else{
            tuples[index].val = val;
        }
        Keylist.push_back(key);
    }
    void remove(const int & key){
        size_t index = index0fKey(key);
        tuples[index]= tuples[tuples.size()-1];
        tuples.pop_back();
    }
    size_t size() const{return tuples.size();}
    vector<int> getKeys(){
        return Keylist;
    }
};

课件中的相关代码（供参考）

#include <vector>
#define I(i,n) for (int i = 0; i < n; ++ i)
template <typename K,typename V>
class NoSuchKeyException{};
class Tuple
{
    public:
    K key;
    V val;
    bool in_use;

    Tuple() : in_use(false){}
};

template <typename K,typename V>
class Dictionary
{
    vector<Tuple<K,V>> tuples;
    size_t _size;
public:
    Dictionary() : _size(0){
        tuples.resize(1000);
    }

    size_t circular_shift(size_t bits,int shift_bits){
        const int num_bits = 8 * sizeof(size_t);
        shift_bits = shift_bits % num_bits;
        return bits << shift_bits | bits >> (num_bits - shift_bits);
    }

    size_t hash_function(const string & key){
        size_t code=0;
        I(i,key.size())
        code ^=circular_shift(key[i],i*5);
        return code;
    }

    size_t canonical_index(const K &key) const{
        size_t hash_code = hash_function(key);
        return hash_code % tuples.size();
    }

    size_t indexOfKey(const K & key) const{
        size_t index = canonical_index(key);
        while(true){
            if(!tuples[index].in_use) return index;
            if(tuples[index].key == key) return index;
            index = (index+1)% tuples.size();
        }
    }

    void _inspect() const{
        I(i,tuples.size())
             if(tuples[i].in_use)
               cout <<"#"<<i<<" C"<< canonical_index(tuples[i].key)<<" "<<tuples[i].key<<" "<<tuples[i].val<<endl;
    }

static bool _between(size_t hole,size_t canonical,size_t tuple_index){
    if(hole<tuple_index)
    return canonical > hole && canonical <=tuple_index;
    else
    return canonical > hole || canonical <=tuple_index;
}

void remove(const K & key){
    size_t index = indexOfKey(key);
    if(!tuples[index].in_use)
        throw NoSuchKeyException();
    tuples[index].in_use = false;
    -- _size;
    size_t hole = index;
    size_t tuple_index = hole;
    while(ture){
        tuple_index = (tuple_index + 1) % tuples.size();
        if(!tuples[tuple_index].in_use) return;
        size_t canonical canonical_index(tuples[tuple_index].key);
        if(_between(hole,canonical,tuple_index)) continue;
        tuples[hole] = tuples[tuple_index];
        hole = tuple_index;
        tuples[hole].in_use = false;
    }
}

void put(const K & key,const V &val){
    size_t index = indexOfKey(key);
    tuples[index].key = key;
    tuples[index].val = val;
    if(tuples[index].in_use) return;
    tuple_index[index].in_use = true;
    ++ _size;
    if(2 * _size > tuple.size())
    _double_tuples();
}

void _double_tuples(){
    vector<Tuple> non_empty_tuples;
    I(i,tuples.size())
    if(tuples[i].in_use)
    non_empty_tuples.push_back(tuples[i]);
    clear();
    tuple.resize(tuple.size() * 2);
    I(i,non_empty_tuples.size())
    put(non_empty_tuples[i].key,non_empty_tuples[i].val);
}
};