MRU without linked lists

mru.cpp

#include <cstdio>
#include <cassert>
#include <vector>
#include <string>
#include <unordered_set>

class Mru
{
public:
    Mru(size_t size): _size(size), _limit(size * 2)
    {
        assert(size > 0);
    }

    void touch(const std::string& str)
    {
        _storage.push_back(str);
        if (_storage.size() >= _limit) normalize();
    }

    std::vector<std::string> contents()
    {
        normalize();
        return std::vector<std::string>(_storage.rbegin(), _storage.rend());
    }

private:
    size_t _size, _limit;
    std::vector<std::string> _storage;

    void normalize()
    {
        std::vector<std::string> data(std::move(_storage));

        std::unordered_set<std::string> s;

        for (std::vector<std::string>::reverse_iterator it = data.rbegin(); it != data.rend(); ++it)
            if (_storage.size() < _size && s.insert(*it).second)
                _storage.push_back(*it);

        std::reverse(_storage.begin(), _storage.end());
    }
};

void DumpMru(Mru& mru, const char* comment)
{
    printf("Mru:");
    for (auto& s: mru.contents()) printf(" %s", s.c_str());
    printf(" -- %s\n", comment);
}

int main()
{
    Mru mru(3);

    mru.touch("a");
    mru.touch("b");
    mru.touch("c");
    DumpMru(mru, "touch abc");

    mru.touch("b");
    DumpMru(mru, "touch b");

    mru.touch("b");
    DumpMru(mru, "retouch b");

    mru.touch("d");
    DumpMru(mru, "introduce d");

    mru.touch("a");
    DumpMru(mru, "reintroduce a");
}