LRU Pagefaults.cpp

#include <iostream>
#include <vector>
#include <set>
#include <list>

int count_pagefaults(std::vector<int> access, int max_size) {
    std::set<int> working_set;
    std::list<int> lru_queue;

    int page_faults = 0;
    for (auto page : access) {
        if (working_set.find(page) == working_set.end()) {
            page_faults++;
            working_set.insert(page);
        }

        if (working_set.size() > max_size) {
            auto front = lru_queue.front();
            lru_queue.remove(front);
            working_set.erase(front);
        }

        lru_queue.remove(page);
        lru_queue.push_back(page);
    }

    return page_faults;
}

int main(void) {
    std::vector<int> input = { 2, 3, 6, 7, 1, 5, 6, 2, 1, 1, 6, 5, 1, 6, 6, 4, 5, 6, 2, 2, 3, 4, 4, 2 };
    for (int i = 1; i <= 10; i++) {
        std::cout << i << ": " << count_pagefaults(input, i) << '\n';
    }
    getchar();
}