1

我正在设置一个 std::map 对象，它将一系列时间范围（键）链接到对象。

我的目的是确保不能将两个重叠的时间范围值添加到此映射中 - 我知道我可以通过创建一个比较器函数来做到这一点，如果存在重叠则返回 true 并将其作为第三个比较器模板项传递给标准::地图。

但是，我想根据单个时间点而不是范围来查找值。

我想我需要覆盖一个运算符，但我不确定哪个 - 有什么想法吗？

我需要快一点，因为我认为办公室即将关闭，因此对缺乏细节/代码表示歉意。

4

3 回答 3

2

当您比较两个范围时，您有三种可能的结果：

  1. 第一个开始并在第二个之前结束。
  2. 第一个开始并在第二个之后结束。
  3. 两者重叠。

您需要对比较函数进行编码以反映这种关系。

bool RangeLess(const range &r1, const range &r2)
{
    return r1.end < r2.start;
}

那很容易，不是吗？如果有任何重叠，两者都RangeLess(r1,r2)将RangeLess(r2,r1)返回false，并且两者将被视为等效。map如果地图中已经存在等效项，则尝试插入 a将失败。

要查找单个时间，请使用开始值和结束值相同的范围。

于 2013-09-11T18:40:54.967 回答
1

  1. 添加接受单个值（时间）的构造函数，并生成由单点组成的范围 - 开始和结束是相同的。

  2. 覆盖您的范围的运算符 ==，以便在范围重叠时返回 true，否则返回 false。

现在，您可以查找传递单个值（时间）的键，这将默认构造正确的范围，如果范围重叠，则返回 true。

于 2013-09-11T18:27:39.880 回答
0

在这种情况下，我建议使用按结束时间排序的向量或双端队列（这优化了“调度”尽可能多的间隔），并简单地迭代列表，跳过重叠的项目：

#include <string>
#include <deque>
#include <algorithm>

using Timepoint = unsigned; // std::chrono::system_clock::time_point;
struct Entry {
    Timepoint start, end;
    std::string data;
};

#include <iostream>
int main()
{
    std::deque<Entry> schedule { 
        {  77472, 77504, "A" },
        {  77301, 77371, "B" },
        {  77406, 77439, "C" },
        {  77270, 77303, "D" },
        {  77302, 77570, "E" },
    };

    // order by end time_point
    std::sort(begin(schedule), end(schedule), [](Entry const& a, Entry const& b) { return a.end < b.end; });

    // now, iterate the schedule entries, skipping overlapping items
    for(auto it = begin(schedule); it != end(schedule); )
    {
        auto const& entry = *it;
        std::cout << "entry: " << entry.data << " from " << entry.start << " to " << entry.end << "\n";

        // find next entry that doesn't overlap:
        while (++it != end(schedule))
                if (it->start > entry.end)
                    break;
    }
}

这个算法可能有一个名字：它基本上是一种调度算法，它通过总是调度下一个最快完成的条目来优化作业的数量（而不是，例如总“占用”间隔） 。

上面的代码打印：（住在 Coliru 上）：

entry: D from 77270 to 77303
entry: C from 77406 to 77439
entry: A from 77472 to 77504
于 2013-09-11T19:13:18.693 回答