Как показано ниже, набор интервалов по оси Y (т. Е. По вертикали) должен удовлетворять двум требованиям:
1) сортирует все интервалы снизу вверх;
2)он возвращает ошибку вставки, если новый интервал перекрывается с любым заданным интервалом.Это похоже на STL set<int> возвращает pair.second == false при вставке дубликата int.
Я предполагаю, что настраиваемая функция сравнения cmp_set вызывает ошибку сбоя поиска / стирания, а также порядок интерваловнисходящий (будет восходящим?).Так как набор STL опирается на двоичный поиск при поиске интервала, он не работает.
Как это исправить?Проблема состоит в том, что функция сравнения cmp_set должна обрабатывать два вышеуказанных требования 1) и 2), но возвращать значение int, поскольку -1/1/0, кажется, не работает.Изменение его на функцию сравнения bool возвращает только значение true / false, которое не может обнаружить перекрывающиеся интервалы.
#include <iostream>
#include <string>
#include <set>
using namespace std;
struct Interval {
int down;
int up;
Interval(int d, int u) {
down = d;
up = u;
}
bool operator==(const Interval& other) {
return down == other.down && up == other.up;
}
};
auto cmp_set = [](const Interval& a, const Interval& b) {
// if (a.up <= b.down) {//a's up is below b's down
// return -1; //sort a before b, like a < b
// } else if (a.down >= b.up) {//a's down is above b's up
// return 1; //sort a after b, like a > b
// } else {
// return 0; //overlap. Very similar to the Interval Overlap
// }
if (max(a.down, b.down) < min(a.up, b.up)) return 0; //overlap of intervals
else { //sort the two intervals
if(a.up <= b.down) return -1;
else return 1;
}
};
void print(set<Interval, decltype(cmp_set)>& s) {
for (auto it = s.begin(); it != s.end(); it++) {
cout << it->down << "->" << it->up << ", ";
}
cout << endl;
}
int main()
{
set<Interval, decltype(cmp_set)> s(cmp_set);
s.insert(Interval{1, 3});
s.insert(Interval{3, 4});
print(s); //3->4, 1->3,
auto iter = s.find(Interval{3, 4});
if (iter == s.end()) cout << "not find" << endl; //not find
s.erase(Interval{3, 4}); //fail to remove the Interval
print(s); //still contains 3->4, 1->3,
return 0;
}