0 
#include <iostream>
#include <set>
#include <tuple>

struct Key {
  int field1;
  int field2;

  Key(int field1, int field2) : field1(field1), field2(field2) {}

  bool operator<(const Key& other) const {
    // Is this acceptable?! Seems to work
    if (field2 == 0 || other.field2 == 0) {
      return field1 < other.field1;
    } else {
      return std::tie(field1, field2) < std::tie(other.field1, other.field2);
    }
  }
};

int main() {
    std::set<Key> values{Key(4,3), Key(5,9), Key(5,7), Key(5,8), Key(6,1)};
    std::cout << values.find(Key(5,0))->field2 << std::endl; // Prints '7'
    auto range = values.equal_range(Key(5,0));
    for (auto i = range.first; i != range.second; i++) {
        std::cout << i->field2; // Prints '789'
    }
    return 0;
}

Field2 在我的数据中并不总是可用，所以有时我使用通配符值 0，它可以匹配 field1 匹配的任何值。如果我从不插入具有通配符值的元素并且只在集合中查找它们，这在 C++ 中是否有效？我可以接受 find 函数在这种情况下返回任何值，这在我的代码中很少发生，但希望在重复调用时它会是相同的值。

根据规范，binary_search 似乎不需要严格的弱排序，这应该是执行查找时在数据结构上使用的唯一算法，对吧？还是我应该担心一些未定义的行为？

25.4 排序及相关操作

...为了使 25.4.3 中描述的算法以外的算法正常工作，comp 必须对值进行严格的弱排序...

25.4.3 二分查找

4

1 回答 1

1

你错了。std::set::find在二叉搜索树中进行查找（在典型实现中）。这可能看起来像二分搜索算法，但 25.4.3 中的算法通常不用于查找。树只支持非随机访问迭代器，使用线性迭代器的二分查找比使用数据在 BST 中的查找要慢得多。

的比较器std::set必须符合比较概念，这确实需要严格的弱排序。

如果我从不插入具有通配符值的元素并且只在集合中查找它们，这在 C++ 中是否有效？

从技术上讲不是，因为您违反了要求。{x, 0}从包含{x, a}和的集合中查找时，至少您会得到不确定的结果{x, b}。任何一个都可以找到。如果这无关紧要，那么我怀疑典型的实现会带来麻烦。但是，您所做的事情并不能保证按标准工作，这足以让大多数人回避它。

于 2016-02-09T08:48:11.380 回答