The precondition of flat_set's transparent insertion is specified as follows:
https://eel.is/c++draft/flat.set#modifiers-2
Preconditions: The conversion from x into value_type constructs an object u, for which find(x) == find(u) is true.
... which is highly problematic. #4084 tried to add the following test. As fs.find(2) == fs.end(), and fs.find(2-10) == fs.end(), this is currently allowed by the standard.
void test_insert_transparent_partially_inconsistent() {
struct broken_key {
int key;
explicit operator int() const {
return key - 10;
}
};
flat_set<int, key_comparer/*comparator able to extract ".key" if present*/> fs{ 0, 3, 5 };
// fs.find(2) == fs.end(), and fs.find(2-10) == fs.end(), so this is currently allowed by the standard:
fs.insert(broken_key{ 2 });
// ... (assert fs has "{-8, 0, 3, 5}")
// ...
}
The problem is that the precondition cannot ensure the lower_bound(transparent-key) be the same as lower_bound(convert-result). If we must adhere to the current specification, after deciding that the transparent-key is not contained (by finding its lower_bound and doing the comparision), we still need to verify that the bound is also the real lower_bound for the convert-result; and if not, we need to fall back to another (non-transparent) insert function.
The condition above is unlikely useful but is generally undetectable, and the solution will have considerable performance impact. As commented in #4084, the real solution might be making the precondition more restrictive in the standard.
The current implementation will work fine if the precondition is specified as:
The conversion from x into value_type constructs an object u, for which "contains(x) == contains(u) && lower_bound(x) == lower_bound(u)" is true.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4