LRU Strategy in C++

 //C++ implementation of above algorithm

#include<bits/stdc++.h>

using namespace std;

// Function to find Buffers using indexes

int LRUBufferPool(int Buffer[], int n, int capacity)

{

// To represent set of current Buffer. We use

// an unordered_set so that we quickly check

// if a Buffer is present in set or not

unordered_set<int> s;

// To store least recently used indexes

// of Buffer.

unordered_map<int, int> indexes;

// Start from initial Buffer

int Buffer_faults = 0;

for (int i=0; i<n; i++)

{

// Check if the set can hold more Buffers

if (s.size() < capacity)

{

// Insert it into set if not present

// already which represents Buffers

if (s.find(Buffer[i])==s.end())

{

s.insert(Buffer[i]);

// increment Buffer

Buffer_faults++;

}

// Store the recently used index of

// each Buffer

indexes[Buffer[i]] = i;

}

// If the set is full then need to perform lru

// i.e. remove the least recently used Buffer

// and insert the current Buffer

else

{

// Check if current Buffer is not already

// present in the set

if (s.find(Buffer[i]) == s.end())

{

// Find the least recently used pages

// that is present in the set

int lru = INT_MAX, val;

for (auto it=s.begin(); it!=s.end(); it++)

{

if (indexes[*it] < lru)

{

lru = indexes[*it];

val = *it;

}

}

// Remove the indexes page

s.erase(val);

// insert the current page

s.insert(Buffer[i]);

// Increment page faults

BufferPool++;

}

// Update the current page index

indexes[Buffer[i]] = i;

}

}

return BufferPool;

}

// Driver code

int main()

{

int Buffer[] = {3, 0, 1, 4, 2};

int n = sizeof(Buffer)/sizeof(Buffer[0]);

int capacity = 4;

cout << LRUBufferPool(Buffer, n, capacity);

return 0;

}