карта с ошибкой сегментации класса

Question

Разработка и внедрение структуры данных для кэша наименее используемого (LRU). Он должен поддерживать следующие операции: get и set.

get (key) - Получить значение (всегда будет положительным) ключа, если ключ существует в кеше, в противном случае возвращает -1. set (ключ, значение) - установите или вставьте значение, если ключ еще не присутствует. Когда кеш достигнет своей емкости, он должен аннулировать последний использованный элемент перед вставкой нового элемента.

#include <iostream> 
#include <map> 
using namespace std; 
struct node{ 
    int val; 
    struct node* next; 
    struct node* prev; 
}; 
class dlist{ 
    public: 
     dlist(){} 
     dlist(int capacity){ 
      cap=capacity; 
     } 
     void add(int value){ 
      node* n=new node; 
      n->val=value; 
      if (size==0){ 
       size++; 
       tail=n; 
       head=tail; 
      } 
      else { 
       if (size==cap){ 
        node* buf=head; 
        head=head->next; 
        head->prev=NULL; 
        delete buf; 
        size--; 
       } 
       tail->next=n; 
       n->prev=tail; 
       tail=n; 
       size++; 
      } 
     } 
     int getVal(){ 
      if (tail==NULL) 
       return -1; 
      return tail->val; 
     } 
    private: 
     int cap; 
     int size; 
     node* tail; 
     node* head; 
}; 

class LRUCache{ 
    public: 
     LRUCache(int capacity) { 
      cap=capacity; 
     } 
     int get(int key) { 
      if(cap!=0&&cache.find(key)!=cache.end()) 
       return cache[key].getVal(); 
      return -1; 
     } 
     void set(int key, int value) { 
      if (cap==0) 
       return; 
      if(cache.find(key)==cache.end()){ 
       dlist d=dlist(cap); 
       cache.insert(make_pair(key,d)); 
      } 
      cache[key].add(value); 
     } 
    private: 
     int cap; 
     map<int,dlist> cache; 
}; 

int main() 
{ 
    LRUCache lru(3); 
        cout<<"asd"; 
    lru.set(1,9); 
    lru.set(1,8); 
    lru.set(1,1); 
    lru.set(1,7); 
    lru.set(2,9); 
    cout<<lru.get(1)<<endl; 
    cout<<lru.get(2)<<endl; 
    cout<<lru.get(3)<<endl; 
    return 0; 
} 

поэтому я использовал карту и пользовательские двойной связанный список, это, кажется, работает нормально, если я с добавить COUT строку сразу после инициализации LRU, но она будет иметь сегментный вина, если у меня нет, я и не очень уверен, что мне следует делать, чтобы управлять использованием памяти LRU (если это проблема)

Также, если есть какая-либо строка, которая может быть лучше написана (кроме пространства имен std), пожалуйста, скажите мне, я был бы очень признателен за то, что ,

Answer 1

Ваша программа имеет неопределенное поведение со времени переменных членов size, tail и head из dlist не инициализируется перед использованием.

Использование

dlist() : dlist(0) {} 
dlist(int capacity) : cap(capacity), size(0), tail(nullptr), head(nullptr) {} 

Это устраняет проблему нарушения сегментации в ходе тестирования.

Я рекомендую добавить конструктор node также:

struct node{ 

    node(int v) : val(v), next(nullptr), prev(nullptr) {} 

    int val; 
    struct node* next; 
    struct node* prev; 
}; 

и использовать

node* n=new node(value); 

вместо

node* n=new node; 
n->val=value;