I'm using the SG14 flat_map
as a container.
As per a standard map, it takes Key
and Value
template parameters.
Unlike a standard map, however, it doesn't store std::pair<Key, Value>
in a binary search tree, but rather stores the keys and values in two separate containers (additional template arguments which default to std::vector
)
template<
class Key,
class Mapped,
class Compare = std::less<Key>,
class KeyContainer = std::vector<Key>,
class MappedContainer = std::vector<Mapped>
>
class flat_map
It then defines a number of types as follows:
using key_type = Key;
using mapped_type = Mapped;
using value_type = std::pair<const Key, Mapped>;
using key_compare = Compare;
using const_key_reference = typename KeyContainer::const_reference;
using mapped_reference = typename MappedContainer::reference;
using const_mapped_reference = typename MappedContainer::const_reference;
using reference = std::pair<const_key_reference, mapped_reference>;
using const_reference = std::pair<const_key_reference, const_mapped_reference>;
If I attempt to use std::ranges::find_if
on the flat_map
, I get an error:
error: no type named ‘type’ in
‘struct std::common_reference<std::pair<const Key&, const Value&>&&,
std::pair<const Key, Value>&>’
121 | auto it = std::ranges::find_if(map, [](auto& kv) { return kv.second.name == "foo"; });
| ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
If I use a non-range find_if
, everything "just works"
auto it = std::find_if(map.begin(), map.end(), [](auto& kv) { return kv.second.name == "foo"; });
Why does the std::ranges::find_if
not work?
Example on godbolt: https://godbolt.org/z/r93f7qozr
Edit:
@Brian provided an exemplar which successfully compiles - albeit with slight differences to mine - notably my map is const
, and I take the lambda argument as a const ref
...
This begs the questions:
- Why does the combination of
const
range andconst auto&
lambda argument fail to compile, while pasing a mutable range works and taking the lambda argument by value works? - I believe it would be considered somewhat of an anti-pattern to take the non-range
std::find_if
algorithm's lambda arguments by value (auto
as opposed toconst auto&
) as this will cause every element to be copied - and therefore usingconst auto&
should be preferred... principle of least surprose means I assumed the same would be the case withstd::ranges
- is this not the case?
CodePudding user response:
Why does the combination of
const
range andconst auto&
lambda argument fail to compile, while pasing a mutable range works and taking the lambda argument by value works?
First, the operator*()
of the iterator of flat_map
is defined as follows:
reference operator*() const {
return reference{*kit_, *vit_};
}
And the type of reference
is pair
, this means that operator*()
will return a prvalue of pair
, so the parameter type of the lambda cannot be auto&
, that is, an lvalue reference, because it cannot bind rvalue.
Second, const flat_map
does not model the input_range
concept, that is, its iterator does not model input_iterator
which requires indirectly_readable
which requires common_reference_with<iter_reference_t<In>&&, iter_value_t<In>&>
, the former is pair<const int&, const int&>&&
, and the latter is pair<const int, int>&
, there is no common_reference
for the two.
The workaround is to just define common_reference
for them, just like P2321 does (which also means that your code is well-formed in C 23):
template<class T1, class T2, class U1, class U2,
template<class> class TQual, template<class> class UQual>
requires requires { typename pair<common_reference_t<TQual<T1>, UQual<U1>>,
common_reference_t<TQual<T2>, UQual<U2>>>; }
struct basic_common_reference<pair<T1, T2>, pair<U1, U2>, TQual, UQual> {
using type = pair<common_reference_t<TQual<T1>, UQual<U1>>,
common_reference_t<TQual<T2>, UQual<U2>>>;
};
For details on common_reference
, you can refer to this question.