C++ std::set 带有基于时间的比较器？

Question

C++ std::set 中使用的比较器取决于时间是否不好？即比较器一次将 return 一件事情，但即使对于完全相同的对象，也可能 return 在不同的时间产生另一个结果？

我读到 std::sets 是用给定的比较器弱排序的。 也许有办法在获取 mySet.begin() 或 myset.end() 值之前刷新排序？

作为可能随时间变化的比较器的示例，考虑事件并希望优先考虑更接近当前时间的事件：

class Event {
public:
    int64_t nTime;
}

class EventComparator {
    // pa < pb
    bool operator()(Event* pa, Event* pb) {
        int64_t now = GetTime();
        return (std::abs(pa->nTime - now) > std::abs(pb->nTime - now));
    }
}

也许有更好的方法来按时间对事件进行排序？显然，我可以只做一个向量并循环查找最大的事件，但只是认为将内置插槽用于比较器会很好。

Answer 1

C++ 高手指正我的错误：

我相信 std::set 实例使用的比较器对底层容器中集合中包含的元素进行排序。这对于最小化 std::set 定义的操作和函数的复杂性是必要的。由于集合依赖于此排序，因此更改顺序是极其不明智的 - 它会导致间歇性（有时顺序可能仍然正确），集合函数中依赖于集合元素正确排序的未定义行为。

在没有看到您的代码的情况下进行猜测，我会说 std::list or std::vector would probably be more appropriate for your application. Check the complexity of the operations and functions you will be using, and make sure that all of them are present on the chosen container. You may need to fall back on the std::algorithm class 是为了帮助完成一些任务，但如果可能的话尽量坚持使用容器的内置功能。

Answer 2

如果 std::set 中元素的相对顺序发生变化，结果是未定义的行为。

在你的情况下，只要事情永远不会发生在未来，时间永远不会溢出，-now就没有意义。如果事情在当前时间之前和之后的任何时间发生，您的代码将表现出未定义的行为。

如果您简单地按时间对所有内容进行排序，然后现在查找附近的元素，并从那里进行处理，您会得到类似的结果，但没有未定义的行为。

即，有一张从 int64_t 到 Event* 的地图。将时间戳存储在 int64_t 中（这使一些事情变得更容易）。然后获取当前时间的lower_bound，并仔细检查它周围以找到到现在的偶数"nearest"（或您选择的任何window）。

如果您的编译器支持透明比较器（C++14 功能），您可以使用 std::set 执行此操作。简单地在 Event* 和 int64_t 时间戳之间实现一个透明的比较器。

Answer 3

我大体上同意 and 所说的：不要让你的比较器依赖于全局状态，真的。为了更权威地支持这一点，Herb Sutter 和 Andrei Alexandrescu 的 C++ 编码标准 中的第 87 项说：

Make predicates pure functions.

Predicate purity: A predicate is a function object that returns a yes / no answer, typically as a bool value. A function is pure in a mathematical sense if its result depends only on its arguments (note that this use of “pure” has nothing to do with pure virtual functions).

Don't allow predicates to hold or access state that affects the result of their operator(), including both member and global state. Prefer to make operator() a const member function for predicates.

我最想添加到讨论中的是实现多个排序的简单解决方案，在我看来应该是首选。

使用永不更改的任意顺序将所有元素（Foo 类型）存储在 std::vector<Foo> 中。显而易见的选择当然是在它们出现时简单地 push_back()。
对于您希望使用的每个排序，定义一个带有 bool operator()(const Foo *, const Foo *) const; 和对应的 std::set<Foo *, Compare> 的纯排序函子 Compare（使用接受两个迭代器和一个比较器的构造函数）这是指向向量的指针的轻量级结构。
如果一个订单过时了，只需处理相应的集合。

只有当您打算多次（按元素数量的顺序）访问每个排序时，这种方法才值得。如果您只想查找少量元素以进行各种排序，请考虑改用 std::partial_sort or std::partial_sort_copy。考虑对 std::vector<Foo *> 个复制成本较低的指针进行排序，而不是对原始 Foo 个对象进行排序。

现在是一些代码：

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <set>
#include <string>
#include <utility>
#include <vector>

using Foo = std::pair<float, float>;
using FooIter = std::vector<Foo>::iterator;

std::ostream&
operator<<(std::ostream& os, const Foo& foo)
{
  os << std::fixed << std::setprecision(4)
     << "["
     << std::setw(8) << foo.first
     << ", "
     << std::setw(8) << foo.second
     << "]";
  return os;
}

// Ugly template, irrelevant for this discussin, don't use in production code.
template<typename ContainerT>
void
print_container(const ContainerT& container, const std::string& name)
{
  std::cout << name << "\n\n";
  for (const auto& it : container)
    std::cout << *it << "\n";
  std::cout << std::endl;
}

int
main()
{
  // Create a vector of 10 'Foo's.
  std::vector<Foo> items {};
  for (float x = 0.0f; x < 10.0f; x += 1.0f)
    items.emplace_back(x, std::sin(x));
  // For convenience, also create a vector of iterators into that vector.
  std::vector<FooIter> item_iterators {};
  for (auto it = items.begin(); it != items.end(); ++it)
    item_iterators.push_back(it);
  // Comparator based on the first element.
  const auto cmp1 = [](const FooIter it1, const FooIter it2)->bool{
    return it1->first < it2->first;
  };
  // Comparator based on the second element.
  const auto cmp2 = [](const FooIter it1, const FooIter it2)->bool{
    return it1->second < it2->second;
  };
  {
    // Create a set ordered by the value of the first element.
    std::set<FooIter, decltype(cmp1)> set1 {
      item_iterators.begin(), item_iterators.end(), cmp1
    };
    print_container(set1, "set1");
  }
  {
    // Create a set ordered by the value of the second element.
    std::set<FooIter, decltype(cmp2)> set2 {
      item_iterators.begin(), item_iterators.end(), cmp2
    };
    print_container(set2, "set2");
  }
  {
    // Create a vector of the three smallest (by the first element) values.
    std::vector<FooIter> vec1(3);
    std::partial_sort_copy(item_iterators.begin(), item_iterators.end(),
                           vec1.begin(), vec1.end(), cmp1);
    print_container(vec1, "vec1");
  }
  {
    // Create a vector of the three smallest (by the second element) values.
    std::vector<FooIter> vec2(3);
    std::partial_sort_copy(item_iterators.begin(), item_iterators.end(),
                           vec2.begin(), vec2.end(), cmp2);
    print_container(vec2, "vec2");
  }
  return 0;
}

输出为：

set1

[  0.0000,   0.0000]
[  1.0000,   0.8415]
[  2.0000,   0.9093]
[  3.0000,   0.1411]
[  4.0000,  -0.7568]
[  5.0000,  -0.9589]
[  6.0000,  -0.2794]
[  7.0000,   0.6570]
[  8.0000,   0.9894]
[  9.0000,   0.4121]

set2

[  5.0000,  -0.9589]
[  4.0000,  -0.7568]
[  6.0000,  -0.2794]
[  0.0000,   0.0000]
[  3.0000,   0.1411]
[  9.0000,   0.4121]
[  7.0000,   0.6570]
[  1.0000,   0.8415]
[  2.0000,   0.9093]
[  8.0000,   0.9894]

vec1

[  0.0000,   0.0000]
[  1.0000,   0.8415]
[  2.0000,   0.9093]

vec2

[  5.0000,  -0.9589]
[  4.0000,  -0.7568]
[  6.0000,  -0.2794]

C++ std::set 带有基于时间的比较器？

C++ std::set with a comparator that is time based?

c++

comparator