std::set::erase 意外擦除 3 个元素

Question

在最后一个erase之前，s1和s2中的元素相同

最后 erase 到 s1 擦除集合 s1 中的 1 个元素。没错。

最后 erase 到 s2 擦除集合 s2 中的 3 个元素。出乎意料。

#include <iostream>
#include <cstdlib>
#include <cassert>
#include <set>
#include <functional>

using namespace std;

struct Ev {
  int p = 0;
  int l = 0;
  int r = 0;
  bool open = false;

  friend ostream& operator<<(ostream& os, const Ev& ev);
};

ostream& operator<<(ostream& os, const Ev& ev) {
  os << "p = " << ev.p << ", l = " << ev.l << ", r = " << ev.r << boolalpha
     << ", open = " << ev.open;
  return os;
}

int main() {
  auto lr_cmp = [](const Ev& lhs, const Ev& rhs) {
    return lhs.r == rhs.l;
  };
  set<Ev, decltype(lr_cmp)> s1(lr_cmp);
  set<Ev, decltype(lr_cmp)> s2(lr_cmp);

  assert(s1.insert({0, 0, 1, true}).second);
  assert(s1.insert({1, 1, 3, true}).second);
  assert(s1.insert({2, 3, 4, true}).second);
  assert(s1.insert({0, 4, 5, true}).second);
  for (const auto& ev : s1) {
    cout << ev << endl;
  }
  assert(s1.erase({3, 1, 3, false}) == 1);
  
  cout << "--------------------------------" << endl;

  assert(s2.insert({1, 1, 3, true}).second);
  assert(s2.insert({1, 3, 4, true}).second);
  assert(s2.insert({0, 0, 1, true}).second);
  assert(s2.insert({0, 4, 5, true}).second);
  assert(s2.erase({2, 3, 4, false}) == 1);
  assert(s2.insert({2, 3, 4, true}).second);
  for (const auto& ev : s2) {
    cout << ev << endl;
  }
  assert(s2.erase({3, 1, 3, false}) == 1);
  return 0;
}

这是输出。

p = 0, l = 0, r = 1, open = true
p = 1, l = 1, r = 3, open = true
p = 2, l = 3, r = 4, open = true
p = 0, l = 4, r = 5, open = true
--------------------------------
p = 0, l = 0, r = 1, open = true
p = 1, l = 1, r = 3, open = true
p = 2, l = 3, r = 4, open = true
p = 0, l = 4, r = 5, open = true
prog.exe: prog.cc:51: int main(): Assertion `s2.erase({3, 1, 3, false}) == 1' failed.
Aborted

Answer 1

lr_cmp 不是 strict weak order。除了其他缺点外，它不是可传递的。

Requirements

if lr_cmp(a,b)==true and lr_cmp(b,c)==true then lr_cmp(a,c)==true

事实并非如此，例如

Ev a {1, 1, 3, true};
Ev b {1, 3, 4, true};
Ev c {0, 4, 5, true};

std::cout << std::boolalpha << lr_cmp(a,b) << lr_cmp(b,c) << lr_cmp(a,c);

因此您的程序的行为是未定义的。据推测，它正在擦除（一些？）在 lr_cmp 下等效的元素，或者没有找到您要删除的元素。

equiv(a, b), an expression equivalent to !lr_cmp(a, b) && !lr_cmp(b, a)

{3, 1, 3, false}等同于{1, 1, 3, true}和{0, 4, 5, true}.

std::set::erase 意外擦除 3 个元素

std::set::erase unexpectedly erases 3 elements

c++

stdset