map[string_view] not compiling

[Paavo Helde]

Hi all,

Let's say I have a std::map with std::string keys and want to access it
with std::string_view keys. For lookup there is a trick to add
std::less<> to the map definition, but it appears this does not help
with operator[] by some reason. Maybe some expert can clarify this?

Here is an example:

#include <map>
#include <string>
using namespace std::string_view_literals;


int main() {

std::string_view key = "foo"sv;

std::map<std::string, int> a;
//auto it = a.find(key); // not compiling
// cannot convert argument 1 from 'std::string_view' to 'const
std::basic_string ...

std::map<std::string, int, std::less<>> b;
auto it = b.find(key); // OK now

b[key] = 3; // still not compiling
// binary '[': no operator found which takes a right-hand operand of
type 'std::string_view'

b[std::string(key)] = 3; // OK now, but may construct a std::string
without reason

}

[Bo Persson]

Not an expert, but operator[] takes a Key parameter, which is
std::string here. And string_view is not implicitly convertible to
std::string.

https://en.cppreference.com/w/cpp/container/map/operator_at


map::find is different in that it has extra overloads for types
comparable to Key.

template< class K > iterator find( const K& x );

https://en.cppreference.com/w/cpp/container/map/find

You enable those by using the generic std::less<> comparator, that
accepts different types for the two objects we want to compare.


Finally

b[std::string(key)] = 3;

works because it explicitly constructs a std::string matching the
key-type. We specifically don't want this by default, as it has the cost
of an extra construction. So that constructor is marked "explicit".

[Paavo Helde]

01.08.2022 15:57 Stefan Ram kirjutas:

> Bo Persson <b...@bo-persson.se> writes:
>> Not an expert, but operator[] takes a Key parameter, which is
>> std::string here. And string_view is not implicitly convertible to
>> std::string.
>

> Even more not an expert, but I take it from the Web that
> even convertibililty alone would not suffice. The Web says:
>
> |Three things are required for something like this to happen:
> |
> |1. The map's comparator must be a transparent comparator
> |
> |2. The at() method must have an overload that participates in
> | overload resolution when the container has a transparent
> | comparator.
> |
> |3. the parameter must be convertible to the map's key_type.
> |
> |Neither of these are true in your example. The default
> |std::less comparator is not a transparent comparator, there
> |is no such overload for at(), and std::string does not have
> |an implicit conversion from std::string_view.
> |
> The World-Wide Web (2021).
>

Thanks, this is very clear for me now *how* it is not working. But I'm
more interested in *why* is it not working. This would be a quite
reasonable operation in my mind:

1. Look up the map element via a string_view.
2. If not found, only then create a string from string_view and insert
it as a new element.

As for now, it looks like I need to use a pessimization by creating a
string object always (together with the copy and dynamic allocation
penalties), or I need to devise some non-trivial workaround via
lower_bound and insert(hint).

[Öö Tiib]

Yes, the heterogeneous lookup of ordered containers was added by C++14,
but it was for things like find and lower_bound not for operator [].
C++17 added non-heterogeneous insert_or_assign().
C++20 added heterogeneous lookup to unordered containers but also did
not touch those access functions.
Perhaps no one proposed it.

The string_view is optimization and so it is livable that its usage does
not bring most elegant code. Also there have been controversy about
map operator[] before, maybe they did not want to risk with heterogenous
overload to it.

[Bo Persson]

One complication is that for find it is enough that a type is comparable
to the key. For operator[] it would also have to be convertible to the key.

For string and string_view this might be the same thing, but in general
it is not.

[Öö Tiib]

Yes, it is not same thing. The hash is also not same on general case, so
programmer has to provide synchronization of hash for having
heterogeneous lookup in unordered container. So conversion method
can be also made possible to be provided but that can maybe confuse
users with tiny details what is used when.

[Alf P. Steinbach]

`map::operator[]` may create a new `string` -> `int` mapping. But it
doesn't know how to create a `string` key from a `string_view`
key-comparable. Or from say a `double` key comparable, if one defined
such comparison (simply casting to `string` wouldn't even compile).

You may use code like the following, which I believe both clarifies the
issues and is one practical solution.

I chose to also address the silly `no operator[] for const` issue, but
this just-cobbled-together code lacks support for custom comparators.


#include <functional>
#include <map>
#include <stdexcept>
#include <string>
#include <string_view>
#include <utility>
using namespace std::literals;

namespace my {
using std::less,
std::map,
std::out_of_range,
std::string,
std::string_view,
std::forward;

template< class Key >
struct Default_key_factory_
{
template< class Key_id >
static auto make_key( Key_id&& key_id )
-> Key
{ return Key( forward<Key_id>( key_id ) ); }
};

template< class Key_, class Item_, class Key_factory_ =
Default_key_factory_<Key_> >
class Map_:
private map<Key_, Item_, less<>>
{
public:
using Key = Key_;
using Key_factory = Key_factory_;
using Item = Item_;

using Self = Map_;
using Std_map = map<Key, Item, less<>>;

using Std_map::Std_map;
using Std_map::find;
using Std_map::count;
using Std_map::lower_bound;
using Std_map::upper_bound;
using Std_map::equal_range;

template< class Key_id >
auto forced_item( const Key_id& key_id )
-> Item&
{
const auto it = Self::find( key_id );
if( it == Self::end() ) {
return Std_map::operator[]( Key_factory::make_key(
key_id ) );
}
return it->second;
}

template< class Key_id >
auto operator[]( const Key_id& key_id ) -> Item& { return
forced_item( key_id ); }

template< class Key_id >
auto operator[]( const Key_id& key_id ) const
-> const Item&
{
const auto it = Self::find( key_id );
if( it == Self::end() ) {
throw out_of_range( "const-Map_::operator[] - no such
key." );
}
return it->second;
}
};
} // namespace my

auto main() -> int

{
std::string_view key = "foo"sv;

my::Map_<std::string, int> a;
auto it_a = a.find(key); // OK

std::map<std::string, int, std::less<>> b;

auto it_b = b.find(key); // OK

//b[key] = 3; //! Gah

// binary '[': no operator found which takes a right-hand operand
of type 'std::string_view'

a[key] = 3; // OK
b[std::string(key)] = 3; // OK but may construct a std::string
without reason.
}


- Alf

[Juha Nieminen]

Alf P. Steinbach <alf.p.s...@gmail.com> wrote:
> using std::less,
> std::map,
> std::out_of_range,
> std::string,
> std::string_view,
> std::forward;

I love how you use 92 characters (and six lines of code) in order to
avoid writing "std::" three times, which would be a total of 15 characters.
Thus you saved a total of -77 characters and -6 lines of code.

> private map<Key_, Item_, less<>>

> using Std_map = map<Key, Item, less<>>;

> throw out_of_range( "const-Map_::operator[] - no such

While, at the same time, making the code less readable.
(Say what you want, but for example mixing "Map_" and "map" in the same
code is confusing. "std::map" would visually distinguish them much better.)

And why? What for? To this day this is a complete mystery to me.
(I most certainly do not subscribe to the brevity-over-clarity style of
programming.)

There's also a degree of irony in that "Std_map" name...

[Alf P. Steinbach]

On 3 Aug 2022 12:49, Juha Nieminen wrote:
> Alf P. Steinbach <alf.p.s...@gmail.com> wrote:
>> using std::less,
>> std::map,
>> std::out_of_range,
>> std::string,
>> std::string_view,
>> std::forward;
>
> I love how you use 92 characters (and six lines of code) in order to
> avoid writing "std::" three times, which would be a total of 15 characters.
> Thus you saved a total of -77 characters and -6 lines of code.

Noted, that the measure of number of letters is important to you.

>> private map<Key_, Item_, less<>>
>> using Std_map = map<Key, Item, less<>>;
>> throw out_of_range( "const-Map_::operator[] - no such


>
> While, at the same time, making the code less readable.

While at odds with objective reality (e.g. amount of text to parse), and
also at odds with your own above stated preference for succinct code,
i.e. contradicting yourself, here you're unfortunately in line with a
great many C++ programmers which by now may even constitute a majority.

But considering that also a majority of humans on Earth, near 90% I
think the number was, claim that they are religious, i.e. that they have
various serious delusions such as the common belief in personal
telepathic communication with an invisible alien in outer space,

I would not adopt the (probably) herd majority position without at least
one reason other than that it is believed by many people.

> (Say what you want, but for example mixing "Map_" and "map" in the same
> code is confusing. "std::map" would visually distinguish them much better.)
>
> And why? What for? To this day this is a complete mystery to me.
> (I most certainly do not subscribe to the brevity-over-clarity style of
> programming.)
>
> There's also a degree of irony in that "Std_map" name...

`Std_map` refers to a distinct specialization of `std::map`. It's
objectively much better to name it than to define it repeatedly every
place it's used. So there is no irony, even with your preferences.

Avoiding repetition is called the DRY principle, Don't Repeat Yourself,
yielding more DRY code. There are many advantages so the principle's
goodness is commonly accepted. Wikipedia has a page about it at <url:
https://en.wikipedia.org/wiki/Don%27t_repeat_yourself>.


- Alf

[Paavo Helde]

03.08.2022 12:34 Alf P. Steinbach kirjutas:
>         template< class Key_id >
>         auto forced_item( const Key_id& key_id )
>             -> Item&
>         {
>             const auto it = Self::find( key_id );
>             if( it == Self::end() ) {
>                 return Std_map::operator[]( Key_factory::make_key(
> key_id ) );

As far as I can see, this performs the map navigation twice, working
against the goal to use string_view as a performance optimization. I
believe one should use std::map::lower_bound() and an insert with a hint
instead.

[Alf P. Steinbach]

Yes, and also, pass the key id by forwarding reference, `&&`.

Sorry 'bout that.

- Alf

[Juha Nieminen]

Alf P. Steinbach <alf.p.s...@gmail.com> wrote:
> On 3 Aug 2022 12:49, Juha Nieminen wrote:
>> Alf P. Steinbach <alf.p.s...@gmail.com> wrote:
>>> using std::less,
>>> std::map,
>>> std::out_of_range,
>>> std::string,
>>> std::string_view,
>>> std::forward;
>>
>> I love how you use 92 characters (and six lines of code) in order to
>> avoid writing "std::" three times, which would be a total of 15 characters.
>> Thus you saved a total of -77 characters and -6 lines of code.
>
> Noted, that the measure of number of letters is important to you.

It should be a rather obvious thing that it's sarcasm, and pointing out the
irony that by trying to type less you are only typing more. By trying to
save work you are only doing more work. And for what? Just to make the
actual code less readable.

>> While, at the same time, making the code less readable.
>
> While at odds with objective reality (e.g. amount of text to parse), and
> also at odds with your own above stated preference for succinct code,
> i.e. contradicting yourself,

The "using" statements there are not code per se. They don't do anything.
They only exist to make the code shorter later. In other words, they
exist for the goal of brevity-over-clarity.

Avoiding brevity-over-clarity is not about the total length of the code,
but about the readability of the code. There are many ways to make code
less readable, and one of them is to use names that are too short. The
goal of avoiding brevity-over-clarity is not to make the code longer,
but to make it more readable.

Your excessive use of 'using' isn't achieving that, but the opposite.

> here you're unfortunately in line with a
> great many C++ programmers which by now may even constitute a majority.

Have you ever thought there may be a good reason for it?

There are two types of people reading your code: You, and everybody else.
Unfortunately quite often the ease of understanding of the code is very
different for those two groups of people. (And, in fact, you yourself
will eventually become part of the latter group over the years, with
respect to code you write today. The more time passes, the less you'll
remember what you wrote and the more the (un)readability of your code
will start affecting even you yourself, if you ever come back to your
own code.)

[Andrey Tarasevich]

On 8/1/2022 5:57 AM, Stefan Ram wrote:

> Bo Persson <b...@bo-persson.se> writes:
>> Not an expert, but operator[] takes a Key parameter, which is
>> std::string here. And string_view is not implicitly convertible to
>> std::string.
>

> Even more not an expert, but I take it from the Web that
> even convertibililty alone would not suffice. The Web says:
>
> |Three things are required for something like this to happen:
> |
> |1. The map's comparator must be a transparent comparator
> |
> |2. The at() method must have an overload that participates in
> | overload resolution when the container has a transparent
> | comparator.
> |
> |3. the parameter must be convertible to the map's key_type.
> |
> |Neither of these are true in your example. The default
> |std::less comparator is not a transparent comparator, there
> |is no such overload for at(), and std::string does not have
> |an implicit conversion from std::string_view.
> |
> The World-Wide Web (2021).
>

Well, the first on is true in the OP's example. The whole point of
explicitly specifying `std::less<>` as a template argument is to satisfy
this requirement. `std::less<>` is `std::less<void>`. And the latter is
a transparent comparator.

The other points indicate the actual issue: `std::map::[]` does not
support new element creation from anything other than they key type
itself. I.e. `[]` simply does not support that "transparent"
functionality. End of story.

--
Best regards,
Andrey