Реализация LRU Cache на C ++

Я изучаю C ++, решая небольшие дизайнерские задачи. Я попытался реализовать кеш LRU, и реализация, которую я здесь приложил, работает нормально.

Однако я не уверен, соответствует ли мой код передовым практикам C ++. Например, Ненужное использование ref, указателей и константы или отсутствие встроенных функций, пространств имен или макросов.

Пожалуйста, подскажите, как сделать этот код производственным.

PS: Это мой первый вопрос. Все предложения по детализации вопроса приветствуются.

Main.cpp

/******************************************************************************

Implement LRU Cache

*******************************************************************************/
#include "unordered_map"
#include "string"

#include "Page.h"
#include "Disk.h"
#include "Cache.h"

int main()
{
    Disk disk(10);
    Cache cache(disk, 2);
    
    cache.getPage(1);
    cache.getPage(2);
    disk.writePage(2, "Hello");
    cache.getPage(2);
    cache.getPage(1);
    cache.getPage(3);

    return 0;
}

Page.h

struct Page {
    int id;
    std::string content;
    
    Page* prev;
    Page* next;
    
    Page(int id): 
        id(id), 
        content("---"),
        prev(nullptr),
        next(nullptr)
    {
        
    }
    
    int getId()
    {
        return id;
    }
    
    std::string& getContent()
    {
        return content;
    }
    
    void setContent(const std::string& newContent)
    {
        content = newContent;
    }
};

Disk.h

class Disk {
    Page** pageAr = nullptr;
    size_t pageCount = 0;
    
    public:
    
    Disk(size_t pageCount): pageCount(pageCount)
    {
        pageAr = new Page*[pageCount];
        for(int i=0; i<pageCount; ++i)
        {
            pageAr[i] = new Page(i);
        }
    }
    
    Page* readPage(int pageIndex) {
        printf("Reading page %d from DISKn", pageIndex);
        return pageAr[pageIndex];
    }
    
    void writePage(int pageIndex, const std::string& newContent)
    {
        printf("Updating page %d on DISK to %sn", pageIndex, newContent.c_str());
        Page* pg = pageAr[pageIndex];
        pg->setContent(newContent);
    }
    
    ~Disk()
    {
        for(int i=0; i<pageCount; i++)
        {
            delete pageAr[i];
        }
        delete [] pageAr;
        pageAr = nullptr;
        pageCount = 0;
    }
};

Cache.h

class Cache {
    Disk& disk;
    size_t cacheSize;
    Page* pageQueueStart;
    Page* pageQueueEnd;
    std::unordered_map<int, Page*> pageTable;
    
    
    void addPage(Page* p)
    {
        p->prev = nullptr;
        p->next = pageQueueStart;
        if(pageQueueStart != nullptr)
            pageQueueStart->prev = p;
        pageQueueStart = p;
        
        if(pageQueueEnd == nullptr)
            pageQueueEnd = p;
            
        pageTable[p->getId()] = p;
    }
    
    void removePage(Page* p)
    {
        if(p->prev != nullptr)
        {
            p->prev->next = p->next;
        }
        else
        {
            pageQueueStart = p->next;    
        }
        
        if(p->next != nullptr)
        {
            p->next->prev = p->prev;
        }
        else
        {
            pageQueueEnd = p->prev;
        }
        
        p->prev = nullptr;
        p->next = nullptr;
        
        pageTable.erase(p->getId());
    }
    
    void removeLeastRecentlyUsedPage()
    {
        printf("Remove Page %d from CACHEn", pageQueueEnd->getId());
        if(pageQueueEnd->prev)
            pageQueueEnd->prev->next = nullptr;
        pageQueueEnd->prev = nullptr;
        pageQueueEnd->next = nullptr;
        
        pageTable.erase(pageQueueEnd->getId());
    }
    
    public:
    Cache(Disk& disk, size_t cacheSize): 
        disk(disk),
        cacheSize(cacheSize),
        pageQueueStart(nullptr), 
        pageQueueEnd(nullptr)
    {
        
    }
    
    Page* getPage(int pageIndex)
    {
        printf("Reading page %d from CACHEn", pageIndex);
        if(pageTable.find(pageIndex) == pageTable.end())
        {
            printf("tMISSn");
            Page* pageFromDisk = disk.readPage(pageIndex);
            if(pageTable.size() >= cacheSize)
                removeLeastRecentlyUsedPage();
            
            addPage(pageFromDisk);
        }
        else
        {
            printf("tHITn");
            Page* pageFromCache = pageTable[pageIndex];
            
            removePage(pageFromCache);
            addPage(pageFromCache);
        }
        
        printf("Page content : %sn", pageTable[pageIndex]->getContent().c_str());
        return pageTable[pageIndex];
    }
    
    ~Cache()
    {
        pageQueueStart = nullptr;
        pageQueueEnd = nullptr;
    }
};
```

2 ответа
2

Некоторые предварительные наблюдения для начала:

Размещение

поскольку Disk и Cache не являются классами управления памятью, не пишите свой собственный код управления памятью, поскольку управление памятью C ++ подвержено ошибкам. Вместо этого используйте стандартные средства библиотеки, например
std::vector как только возможно.

Семантика перемещения

Это всегда копирует аргумент:

void setContent(const std::string& newContent)
{
    content = newContent;
}

Взять std::string и использовать std::move вместо.

Инкапсуляция

Когда класс является общедоступным, вам не нужны геттеры и сеттеры. Следовательно, Page либо должно быть просто

struct Page {
    int id;
    std::string content{"---"};
    Page* prev;
    Page* next;
};

или иметь частные данные и правильную инкапсуляцию.

Разное

Заголовки из стандартной библиотеки обычно разделяются <>
вместо того "". Более того, файлы заголовков должны быть самодостаточными и включать необходимые файлы заголовков, а не полагаться на исходный файл для их предварительного включения. (Несколько включений одного и того же заголовка будут исключены компилятором.) Вам также не хватает некоторых
#includes, например <cstddef> и <cstdio>.

Имена из стандартной библиотеки C должны по-прежнему квалифицироваться как std::
в C ++.

    Я заметил несколько вещей

    Постоянная правильность

    Хорошая практика – делать методы как геттеры const

    Установка значений в деструкторе

    Нет причин, по которым я знаю, что делать pageAr = nullptr; pageCount = 0; во время разрушения.

    Цикл for на основе диапазона

    Они менее подвержены ошибкам (вы не можете испортить индексы), поэтому я бы посоветовал использовать их, если это возможно.

    Разное

    std::string& getContent()
    {
        return content;
    }
    

    Лучше вернуться const std::string& потому что кажется, что это не предназначено для того, чтобы дать возможность изменить content используя этот геттер

      Добавить комментарий

      Ваш адрес email не будет опубликован. Обязательные поля помечены *