C++ Indexed Queue data structure required

Question

I have a queue of watches. The watch at the front is supposed to expire sooner than the rest. So watches are pushed to the back of the queue and pop'ed from the front of the queue. So far it looks like queue is the data structure applicable for this scenario.

However each watch has an identifier key of type KeyT. KeyT is LessThanComparable. There can be multiple watches identified by the same key. Often a notification associated with a key is emitted. Then the corresponding watches identified with the same key has to be notified and removed from the queue (?). So it is desirable that the corresponding watches will be found in sub-linear time.

So the requirements of the container is

1. push back
2. pop front
3. indexed
4. remove middle

Currently I am using std::list because I am performing deletion in the middle. To find the matching watches I need to perform a linear search through the entire list (missed 3). std::queue cannot be used because its not iterable.

Another solution that I've not yet implemented is to have two containers. As std::list is a stable container, the iterators won't be invalidated by deletion of some other element. So its safe to store the iterator inside std::map. On the other hand the requirement 3 is satisfied.

1. std::list<watch>
2. std::multimap<KeyT, std::list<watch>::iterator>

On the other hand it increases memory requirement. Also every insertion and deletion has to be performed twice on two containers. Is there any other bottleneck / loophole ? Is there any existing alternative to solve this problem ? Is there any container data structure in boost that serves the requirements of this problem ?

Answer 1

Here's how to use Boost Multi-Index:

Live On Coliru

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/member.hpp>
#include <chrono>

#include <random>
#include <boost/range/istream_range.hpp> // make_iterator_range
#include <thread> // sleep_for
#include <iostream>

namespace bmi = boost::multi_index;
using namespace std::chrono_literals;
using Clock = std::chrono::high_resolution_clock;
using boost::make_iterator_range;

using KeyT = int;

namespace { // generate demo data
    std::mt19937 s_prng{ std::random_device{}() };

    auto gen_expiration() {
        return Clock::now() + std::chrono::milliseconds(std::uniform_int_distribution{1, 100}(s_prng));
    }
    auto gen_key() {
        return std::uniform_int_distribution{10, 20}(s_prng);
    }
}

struct Watch {
    size_t id;
    Watch(int id) : id(id) {}

    Clock::time_point expires_at = gen_expiration();
    KeyT key = gen_key();

    void notify() const {
        auto dt = (expires_at - Clock::now()) / 1.0ms;
        if (dt > 0) {
            std::cout
                << "Watch #" << id << " key " << key
                << " notified with " << dt << "ms to spare\n";
        } else {
            std::cout
                << "Watch #" << id << " key " << key
                << " expired " << -dt << "ms ago\n";
        }
    }
};

using Watches = bmi::multi_index_container<Watch,
    bmi::indexed_by<
        bmi::sequenced<>,
        bmi::ordered_non_unique<
            bmi::tag<struct by_expiration>,
            bmi::member<Watch, Clock::time_point, &Watch::expires_at>
        >,
        bmi::ordered_non_unique<
            bmi::tag<struct by_key>,
            bmi::member<Watch, KeyT, &Watch::key>
        >
    > >;

int main() {
    Watches ww;

    for (auto id=0; id<100; ++id) 
        ww.emplace_back(id);

    // pop ends
    ww.front().notify();
    ww.pop_front();

    ww.back().notify();
    ww.pop_back();

    // erase middle
    {
        auto it = std::next(ww.begin(), ww.size()/2);
        it->notify();
        ww.erase(it);
    }

    std::this_thread::sleep_for(50ms);
    std::cout << "\n--- notify the unlucky ones\n";
    auto& idx = ww.get<by_key>();
    for (auto [it,end] = idx.equal_range(13); it != end;) {
        it->notify();
        it = idx.erase(it);
    }

    ww.remove_if([](Watch const& w) { return w.key == 14; });
}

Which prints output like

Watch #0 key 10 notified with 42.7361ms to spare
Watch #99 key 11 notified with 12.8534ms to spare
Watch #50 key 12 notified with 30.7122ms to spare

--- notify the unlucky ones
Watch #7 key 13 expired 18.664ms ago
Watch #19 key 13 notified with 25.3537ms to spare
Watch #22 key 13 notified with 32.3545ms to spare
Watch #23 key 13 expired 29.6482ms ago
Watch #36 key 13 expired 23.6241ms ago
Watch #51 key 13 expired 17.5943ms ago
Watch #54 key 13 expired 41.5833ms ago
Watch #57 key 13 notified with 29.4185ms to spare
Watch #66 key 13 notified with 27.4347ms to spare
Watch #74 key 13 expired 25.5515ms ago
Watch #78 key 13 notified with 20.4526ms to spare
Watch #83 key 13 notified with 18.4592ms to spare
Watch #96 key 13 notified with 10.4945ms to spare

Note that I completely gratuitously threw in the index by expiration, which you may or may not need.