1

我有一块queue手表。前面watch的应该比其他的更早到期。所以手表被推到队列的后面并从队列的前面弹出。到目前为止，队列似乎是适用于这种情况的数据结构。

但是，每个手表都有一个类型为 的标识符键KeyT。KeyT 是LessThanComparable. 同一个键可以识别多个手表。通常会发出与键关联的通知。然后必须通知以相同密钥标识的相应手表并将其从queue (?). 因此，希望在亚线性时间中找到相应的手表。

所以容器的要求是

  1. 推回
  2. 流行前线
  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可以满足此问题的要求？

4

1 回答 1

1

以下是使用 Boost Multi-Index 的方法：

住在科利鲁

#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

请注意，我在到期时完全无偿地投入了索引，您可能需要也可能不需要。

于 2020-05-01T16:35:22.707 回答