G++ ok, but got runtime error


  • 0
    L

    #include <iostream>
    using std::cout;
    using std::endl;

    struct KV{
    int key;
    int val;
    struct KV* next;
    struct KV* pre;
    struct KV* pri_next;
    struct KV* pri_pre;
    KV(int k, int v) : key(k), val(v), next(NULL), pre(NULL), pri_next(NULL), pri_pre(NULL) {}
    };

    #define BUCKETS 1000

    int hash_f(int k) {
    return k % BUCKETS;
    }

    class LRUCache{
    public:
    LRUCache(int capacity) {
    this->cap = capacity;
    pri_head = NULL;
    pri_tail = NULL;
    cur_cap = 0;
    }

    void visit(KV *kv) {
        // delete from pri list
        if (kv == pri_head) {
            return ;
        }else if (kv == pri_tail) {
            pri_tail = kv->pri_pre;
            kv->pri_pre->pri_next = NULL;
        }else {
            kv->pri_pre->pri_next = kv->pri_next;
            kv->pri_next->pri_pre = kv->pri_pre;
        }
        kv->pri_next = pri_head;
        pri_head->pri_pre = kv;
        
        pri_head = kv;
    }
    
    
    int get(int key) {
        int hash_val = hash_f(key);
        KV * kv_list = hash_table[hash_val];
        KV *tmp = kv_list;
        while (tmp != NULL) {
            if (tmp->key == key) {
                visit(tmp);
                return tmp->val;
            }
            tmp = tmp->next;
        }
        return -1;
    }
    
    KV *get_kv(int key) {
        int hash_val = hash_f(key);
        KV * kv_list = hash_table[hash_val];
        KV *tmp = kv_list;
        while (tmp != NULL) {
            if (tmp->key == key) {
                visit(tmp);
                return tmp;
            }
            tmp = tmp->next;
        }
       return NULL; 
    }
    
    void set(int key, int value) {
        KV *hashed_kv = get_kv(key);
        int key_hash = hash_f(key);
        if (cur_cap == cap) {
            if (hashed_kv == NULL) {
                KV * node_to_remove = pri_tail;
                if(node_to_remove->pre == NULL) {
                    hash_table[hash_f(node_to_remove->key)]->next = node_to_remove->next;
                }else if (node_to_remove->next == NULL) {
                    node_to_remove->pre->next = NULL;
                }else {
                    node_to_remove->pre->next = node_to_remove->next;
                    node_to_remove->next->pre = node_to_remove->pre;
                }
                KV *node_to_add = new KV(key, value);
                if (hash_table[key_hash] == NULL) {
                    hash_table[key_hash] = node_to_add;
                    hash_table_tail[key_hash] = node_to_add;
                }else {
                    hash_table_tail[key_hash]->next = node_to_add;
                    node_to_add->pre = hash_table_tail[key_hash];
                    hash_table_tail[key_hash] = node_to_add;
                }
    
                // add to pri head
                node_to_add->pri_next = pri_head;
                pri_head->pri_pre = node_to_add;
                pri_head = node_to_add;
    
                pri_tail = pri_tail->pri_pre;
                free(pri_tail->pri_next);
                pri_tail->pri_next = NULL;
            }else {
                hashed_kv->val = value;
            }
        } else {
            if (hashed_kv == NULL) {
                KV *node_to_add = new KV(key, value);
                key_hash = hash_f(node_to_add->key);
                if (hash_table[key_hash] == NULL) {
                    hash_table[key_hash] = node_to_add;
                    hash_table_tail[key_hash] = node_to_add;
                }else {
                    hash_table_tail[key_hash]->next = node_to_add;
                    node_to_add->pre = hash_table_tail[key_hash];
                    hash_table_tail[key_hash] = node_to_add;
                }
    
                // add to pri head
                if (pri_head == NULL) {
                    pri_head = node_to_add;
                    pri_tail = node_to_add;
                }else {
                    node_to_add->pri_next = pri_head;
                    pri_head->pri_pre = node_to_add;
                    pri_head = node_to_add;
                }
                cur_cap ++;
            }else {
                hashed_kv->val = value;
            }
        }
    }
    KV * hash_table[BUCKETS];
    KV * hash_table_tail[BUCKETS];
    KV * pri_head;
    KV * pri_tail;
    int cur_cap;
    int cap;
    

    };

    int main() {
    LRUCache *cache = new LRUCache(1);
    cache->set(2,1);
    cout << cache->get(2) << endl;
    cache->set(3,4);
    cout << cache->get(2) << endl;
    cache->set(4,5);
    cache->set(5,6);
    cout << cache->get(2) << endl;
    cout << cache->get(3) << endl;
    return 0;
    }

    I did not use STL containers. it is ok when using g++ 3.4.5; But I got a runtime error when submitting the code.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.