Repository navigation
flat_set's transparent insertion requirements are deficient #4105
Description
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.
Activity
CaseyCarter commentedon Oct 19, 2023
I don't understand the issue, possibly because the example is incomplete. What's
key_comparer? What requirement are we unable to implement?The precondition seems sufficient to guarantee that
find(broken_key{2})will locateint(broken_key{2})(i.e.,-8) if and only if it exists in theflat_set; what else does it need to do?achabense commentedon Oct 19, 2023
To support
fs.insert(broken_key{ 2 });, theflat_setshould firstly findlower_bound(broken_key{2}), which is after0and before3. Thenflat_setdecides it is not contained, so convert it toint(-8), and try to do the insertion. However, thatlower_boundis unusable as insert position. The current impl is assuminglower_boundshould be insertable here. Otherwise,flat_sethave to make another commoninsert(int(-8))call. See 0296416.CaseyCarter commentedon Oct 19, 2023
This seems like a bug in the implementation.
Is that not conforming?
insertmust have linear complexity, we "have time" to perform two logarithmic searches. Ideally we'd perform another binary search for-8starting at the position we found looking forbroken_key{2}- with the expectation that it will often be close to the correct insertion position - but even that is an optimization, not a requirement.Heck, we could perform two linear searches and it would be poor Quality of Implementation, but still conforming.
achabense commentedon Oct 19, 2023
This issue is motivated by #4084 (comment). #4084 tried to make the insertion "conformant". However, I believe the current specification is a defect in the standard, and will put transparent insertion in a logically unsound state.
As long as
transparent comparisionandconversiondon't represent the same thing, under current precondition (find(transparent-key) == find(converted)), the insertion is valid on a value-dependent basis, relying on both the value of the key and the contents in flat_map. Take the sample code for example again, the expression is initially valid by the current standard(1); however, the same expression(2)will become invalid immediately after(1). This is generally true for such inconsistent types.And generally there is no way to decide whether such a transparent insertion will break invariants without doing the real conversion. For the first expression
(1), without knowingfshas{ 0, 3, 5 }, we have no way to decide whether that expression will be valid in advance. We can only knowfscontainsbroken_key{ 2 }byfindit. However if the transparent key doen't represent the same thing incomparisionandconversion, we can say nothing about what will be the result offind(conversion-result)without doing the real conversion.I believe allowing inconsistent types on a value-dependent basis makes no benefit. Worse, for user-provided transparent-key&comparator, we cannot decide whether inconsistency can happen - only the standard is able to rule out inconsistent types.
StephanTLavavej commentedon Oct 25, 2023
We talked about this at the weekly maintainer meeting, although we didn't have time to track down all of the Standardese. (The main question in our minds is whether this affects the existing ordered/unordered associative containers too.)
We strongly believe that the Standard's requirements for transparent insertion should say that the freshly constructed element should sort into the same position as the transparent comparison indicates, otherwise the Standard is asking for an additional comparison after the element has been constructed (which largely defeats the purpose of the transparent machinery), to avoid violating container invariants.
[-]Problems in implementing `flat_set`'s transparent insertion[/-][+]`flat_set`'s transparent insertion requirements are deficient[/+]timsong-cpp commentedon Oct 27, 2023
This wording was copied from an older revision of WG21-P2363. LWG review of that paper led to wording changes (see WG21-P2363R5) but we'll need an issue to apply the same changes to all the flat_meows.
frederick-vs-ja commentedon Jan 28, 2024
LWG-4048 is filed.