Repository: TheAlgorithms/C-Plus-Plus
File: others/lfu_cache.cpp (C++)

Code before:
 */
namespace others {
namespace Cache {

template <typename T>
class D_Node {
 public:
    T data;
    D_Node<T> *prev;
    D_Node<T> *next;

    explicit D_Node(T data) : data(data), prev(nullptr), next(nullptr) {}
};

template <typename K, typename V>
using CacheNode = D_Node<std::pair<K, V>>;

template <typename K, typename V>
class LFUCache {
    std::unordered_map<K, std::pair<CacheNode<K, V> *, int>>
        node_map;  // maps the key to the node address and frequency
    std::unordered_map<int, std::pair<CacheNode<K, V> *, CacheNode<K, V> *>>
        freq_map;  // maps the frequency to doubly linked list

    int minFreq;    // minimum frequency in the cache
    int _capacity;  // maximum capacity of the cache

 public:
    /**
     * @brief Constructor, Initialize with minFreq and _capacity.
     * @param _capacity Total capacity of the cache.
     */
    explicit LFUCache(int _capacity) : minFreq(0), _capacity(_capacity) {}

 private:
    /**
     * @brief push the node at first position in the linked list of given
     * frequency
     * @param freq the frequency mapping to the linked list where node should be
     * pushed.
     * @param node node to be pushed to the linked list.
     */
    void push(int freq, CacheNode<K, V> *node) {
        // if freq is not present, then make a new list with node as the head as
        // well as tail.
        if (!freq_map.count(freq)) {
            freq_map[freq] = {node, node};
            return;
        }

        std::pair<CacheNode<K, V> *, CacheNode<K, V> *> &p = freq_map[freq];

Review comment (performance):
```suggestion
    std::unordered_map<K, std::pair<CacheNode<K, V> *, int>>
        node_map;  ///< maps the key to the node address and frequency
    std::unordered_map<int, std::pair<CacheNode<K, V> *, CacheNode<K, V> *>>
        freq_map;  ///< maps the frequency to doubly linked list

    int minFreq;    ///< minimum frequency in the cache
    int _capacity;  ///< maximum capacity of the cache
```


Code after:
 * @brief Other algorithms
 */
namespace others {

/**
 * @namespace
 * @brief Cache algorithm
 */
namespace Cache {

/**
 * @class
 * @brief Node for a doubly linked list with data, prev and next pointers
 * @tparam T type of the data of the node
 */
template <typename T>
class D_Node {
 public:
    T data;           ///< data of the node
    D_Node<T> *prev;  ///< previous node in the doubly linked list
    D_Node<T> *next;  ///< next node in the doubly linked list

    explicit D_Node(T data) : data(data), prev(nullptr), next(nullptr) {}
};

template <typename K, typename V>
using CacheNode = D_Node<std::pair<K, V>>;

/**
 * @class
 * @brief LFUCache
 * @tparam K type of key in the LFU
 * @tparam V type of value in the LFU
 */
template <typename K, typename V>
class LFUCache {
    std::unordered_map<K, std::pair<CacheNode<K, V> *, int>>
        node_map;  ///< maps the key to the node address and frequency
    std::unordered_map<int, std::pair<CacheNode<K, V> *, CacheNode<K, V> *>>
        freq_map;  ///< maps the frequency to doubly linked list

    int minFreq;    ///< minimum frequency in the cache
    int _capacity;  ///< maximum capacity of the cache

 public:
    /**
     * @brief Constructor, Initialize with minFreq and _capacity.
     * @param _capacity Total capacity of the cache.
     */
    explicit LFUCache(int _capacity) : minFreq(0), _capacity(_capacity) {}