#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;
}
Поле 2 не всегда доступно в моих данных, поэтому иногда я использую значение с подстановочным знаком 0, которое может соответствовать любому значению, которому соответствует поле Field1. Является ли это допустимым в C ++, если я никогда не вставляю элементы, которые имеют подстановочное значение, и только когда-либо ищу их в наборе? Я в порядке с функцией find, которая возвращает любое из значений в этом случае, что редко встречается в моем коде, хотя, надеюсь, это будет одно и то же значение при повторном вызове.
Согласно Спецификация, Похоже, что строгий слабый порядок не требуется для binary_search, который должен быть единственным алгоритмом, используемым в структуре данных при выполнении поиска, верно? Или есть какое-то неопределенное поведение, о котором мне следует беспокоиться?
25.4 Сортировка и связанные с ней операции
… Для работы алгоритмов, отличных от описанных в 25.4.3
правильно, комп должен вызывать строгий слабый порядок значений …25.4.3 Бинарный поиск
Вы ошибаетесь std::set::find
выполняет поиск в бинарном дереве поиска (в типичной реализации). Это может показаться алгоритмом бинарного поиска, но алгоритмы в 25.4.3 обычно не используются для поиска. Дерево поддерживает только итераторы без произвольного доступа, а двоичный поиск с линейными итераторами намного медленнее, чем поиск с использованием знания о том, что данные находятся в BST.
Компаратор std::set
должен соответствовать сравнить концепция, которая требует строгий слабый порядок.
Является ли это допустимым в C ++, если я никогда не вставляю элементы, которые имеют подстановочное значение, и только когда-либо ищу их в наборе?
Технически нет, так как вы нарушаете требования. По крайней мере, вы будете иметь неопределенные результаты при поиске {x, 0}
из набора, который содержит {x, a}
а также {x, b}
, Либо можно было найти. Если это не имеет значения, то я сомневаюсь, что типичная реализация создаст проблемы. Однако то, что вы делаете, не гарантирует, что оно будет работать по стандарту, которого достаточно, чтобы большинство людей уклонялось от него.
Других решений пока нет …