LRU.cpp

//C++ implementation of above algorithm 
#include<bits/stdc++.h> 
using namespace std; 

// Function to find page faults using indexes 
int pageFaults(int pages[], int n, int capacity) 
{ 
	// To represent set of current pages. We use 
	// an unordered_set so that we quickly check 
	// if a page is present in set or not 
	unordered_set<int> s; 

	// To store least recently used indexes 
	// of pages. 
	unordered_map<int, int> indexes; 

	// Start from initial page 
	int page_faults = 0; 
	for (int i=0; i<n; i++) 
	{ 
		// Check if the set can hold more pages 
		if (s.size() < capacity) 
		{ 
			// Insert it into set if not present 
			// already which represents page fault 
			if (s.find(pages[i])==s.end()) 
			{ 
				s.insert(pages[i]); 

				// increment page fault 
				page_faults++; 
			} 

			// Store the recently used index of 
			// each page 
			indexes[pages[i]] = i; 
		} 

		// If the set is full then need to perform lru 
		// i.e. remove the least recently used page 
		// and insert the current page 
		else
		{ 
			// Check if current page is not already 
			// present in the set 
			if (s.find(pages[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; 
                        // cout<<indexes[*it]<<" index";
					} 
				} 

				// Remove the indexes page 
				s.erase(val); 

				// insert the current page 
				s.insert(pages[i]); 

				// Increment page faults 
				page_faults++; 
			} 

			// Update the current page index 
			indexes[pages[i]] = i; 
		} 
	} 

	return page_faults; 
} 

// Driver code 
int main() 
{ 
	int pages[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2}; 
	int n = sizeof(pages)/sizeof(pages[0]); 
	int capacity = 4; 
	cout << pageFaults(pages, n, capacity); 
	return 0; 
}