CODEWITHSUNDEEP
c++stlcontainers
Arun
Arun

Reputation: 3408

Container with key and sorting criteria separate

I want to have a collection of items which are searchable based on a key (an unsigned value), but I want the elements to be sorted based on a different criteria i.e. the last accessed time (Which is part of the value).

How can I achieve this in C++? I can sort them separately on demand, but can I create the container itself such that sorting happens automatically?

Are there ready made containers (in boost) that can have similar feature built into them?

Upvotes: 3

Views: 104

Answers (1)

Kostas
Kostas

Reputation: 4186

You could probably implement something of this kind, using std::list and std::unordered_map pointing to each other.

#include <list>
#include <unordered_map>

template <typename A>
struct Cache {
    using key = unsigned;

    struct Composite {
        Composite(A &_a, std::list<key>::iterator _it) : a(_a), it(_it) {}
        A &a;
        std::list<key>::iterator it;
    };

    std::unordered_map<key, Composite> map;
    std::list <key> list;

    void insert(key k, A &a) { // Assuming inserting contains accessing                                                                                                          
        list.emplace_front(k);
        map[k] = Composite(a, list.front());
    }

    A &operator[](key k) {
        list.erase(map[k].it);
        list.emplace_front(k);
        return map[k].a;
    }

    A &last_accessed() { // or whatever else you wish to implement                                                                                                               
        assert(!list.empty());
        return map[list.front()].a;
    }
};

This solution is optimized for keeping track of which element was accessed last. If you want to sort given a different attribute, you can follow a similar process but use an std::set to store the values with your comparison function, and then iterators to that from an std::unordered_map hashed with a key of your choice.

Upvotes: 1

Related Questions