Требуется структура данных C ++ Indexed Queue

Question

У меня есть queue часов. watch на фронте должен истечь раньше, чем остальные. Таким образом, часы помещаются в конец очереди и выскакивают из передней части очереди. Пока что похоже, что очередь - это структура данных, применимая для этого сценария.

Однако каждые часы имеют идентификационный ключ типа KeyT. KeyT это LessThanComparable. Может быть несколько часов, идентифицированных одним и тем же ключом. Часто отправляется уведомление, связанное с ключом. Затем соответствующие часы, идентифицированные с тем же ключом, должны быть уведомлены и удалены из queue (?). Поэтому желательно, чтобы соответствующие часы были найдены в сублинейном времени.

Таким образом, требования к контейнеру

1. pu sh назад
2. pop front
3. проиндексирован
4. удалить середину

В настоящее время я использую std::list, поскольку выполняю удаление в середине. Чтобы найти подходящие часы, мне нужно выполнить линейный поиск по всему списку (пропущено 3). std::queue нельзя использовать, потому что он не повторяется.

Другое решение, которое я еще не реализовал, - это наличие двух контейнеров. Поскольку std::list является стабильным контейнером, итераторы не будут аннулированы удалением какого-либо другого элемента. Поэтому безопасно хранить итератор внутри std::map. С другой стороны, выполняется требование 3.

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

С другой стороны, это увеличивает потребность в памяти. Также каждая вставка и удаление должны выполняться дважды на двух контейнерах. Есть ли другие узкие места / лазейки? Есть ли альтернатива для решения этой проблемы? Есть ли в boost какая-либо структура данных контейнера, которая удовлетворяет требованиям этой проблемы?

Answer 1

Вот как использовать мультииндекс повышения:

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; });
}

Какая распечатка выводится как

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

Обратите внимание, что я совершенно случайно добавил индекс по истечении срока, который вам может понадобиться, а может и не понадобиться.