Repository navigation
flat_set's transparent insertion requirements are deficient #4105
Description
Activity
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?Reacted by A. JiangWhat's key_comparer?
struct key_comparer { const auto& extract_key(const auto& obj) const { if constexpr (requires { obj.key; }) { return obj.key; } else { return obj; } } bool operator()(const auto& lhs, const auto& rhs) const { return extract_key(lhs) < extract_key(rhs); } using is_transparent = int; };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.The current impl is assuming lower_bound should be insertable here.
This seems like a bug in the implementation.
Otherwise,
flat_sethave to make another commoninsert(int(-8))call.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.
Reacted by A. JiangThis 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.flat_set<int, key_comparer/*comparator able to extract ".key" if present*/> fs{ 0, 3, 5 }; // [searching: fs.find(2) == fs.end()], and [converted: fs.find(2-10) == fs.end()], so this is currently // ↓ (1) allowed by the standard: fs.insert(broken_key{ 2 }); // ... (assert fs has "{-8, 0, 3, 5}") // ↓ (2) now precondition violation: [searching: fs.find(2) == fs.end()], but [converted: fs.find(2-10) != fs.end()] // fs.insert(broken_key{ 2 });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.
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.
- changed the title
[-]Problems in implementing `flat_set`'s transparent insertion[/-][+]`flat_set`'s transparent insertion requirements are deficient[/+]on Oct 25, 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.
LWG-4048 is filed.
The precondition of
flat_set's transparent insertion is specified as follows:... which is highly problematic. #4084 tried to add the following test. As
fs.find(2) == fs.end(), andfs.find(2-10) == fs.end(), this is currently allowed by the standard.The problem is that the precondition cannot ensure the
lower_bound(transparent-key)be the same aslower_bound(convert-result). If we must adhere to the current specification, after deciding that thetransparent-keyis not contained (by finding itslower_boundand doing the comparision), we still need to verify that the bound is also the reallower_boundfor theconvert-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: