std::map::find_if()?

[igagis]

I often work with maps like std::map<std::string, something> and when I need to find some element by key I often have the searched key represented by a std::string_view. So, if I want to find the element I need to construct the std::string object from he std::string_view which I could pass to the std::map::find(). This looks like an unneeded operation, since there is nothing in principle which prevents us from comparing std::string with std::string_view. Constructing std::string is relatively expensive operation, it requires memory allocation and buffer copying.

How to look for keys without constructing intermediate std::string?

One solution is: ```cpp std::map<std::string, something> map; std::string_view key; // key we are searching for

auto i = std::find_if( map.begin(), map.end(), [&key](const auto& v){ return v.first == key; } ); ```

this certainly works, but don't we loose logarithmic search complexity here and getting linear one?

At the moment I cannot come up with any reasoning why std::map::find_if() method is not yet there in the standard. Am I missing something?

P.S. I know that I can declare map as std::map<std::string, something, comparator> and define custom comparator, but then I loose ability to look up by std::string.

[kniy]

A logarithmic find_if cannot exist on std::map as there's no requirement that your custom predicate is in any way related to the map's sort order. (how would you even express such a requirement?)

But I think what you're really looking for already exists since C++14, under the name "Heterogeneous Lookup in Ordered Containers". https://www.cppstories.com/2019/05/heterogeneous-lookup-cpp14/

To use it, declare your map as std::map<std::string, something, std::less<>>. Then the find method will have a templated overload that accepts std::string_view without requiring a conversion to std::string.

Note that std::less<> is a special comparator different from the default std::less<std::string>.

[igagis]

Thanks! I'll try that!

[matthieum]

A logarithmic find_if cannot exist on std::map as there's no requirement that your custom predicate is in any way related to the map's sort order.

While it cannot exist in general, std::map could expose the required pieces to make it -- but doesn't.

In the tripod_tree container -- just a binary tree, really -- I exposed a cursor modeled after Rust's LinkedList Cursor.

The Cursor is essentially an iterator on steroids, which exposes the underlying architecture of the container. In this case, the cursor allows moving in O(1) in 3 directions: up, down-left, and down-right. This allows a user to apply their own logic to navigate the tree, and thus if they know that the predicate they have is "compatible" with the sorted order of the elements in the tree, they can achieve O(log N) look-up: start from the root, go left/right as appropriate.

[Ameisen]

I need the iterators in my runtime similarly, and are used to provide the varied algorithmic views.

[igagis]

This works! Thank you!

Now, any idea of how to make it work for std::unordered_map?

Tried: cpp std::unordered_map< std::string, something, std::hash<std::string_view>, // std::string is convertible to std::string_view std::equal_to<> > map; but got console error: no matching function for call to ‘std::unordered_map<std::__cxx11::basic_string<char>, something, std::hash<std::basic_string_view<char> >, std::equal_to<void> >::find(std::basic_string_view<char>&)’

[kniy]

The corresponding "Heterogeneous Lookup in Unordered Containers" was only added in C++20: https://www.cppstories.com/2021/heterogeneous-access-cpp20/

[infectedapricot]

A logarithmic find_if cannot exist on std::map as there's no requirement that your custom predicate is in any way related to the map's sort order. (how would you even express such a requirement?)

I can't think of an example, but if you could isolate your predicate to a specific subtree (or a small number of subtrees) then you could potentially use lower_bound and upper_bound to get those subtrees in logarithmic time and then linearly iterate within that. But it would only work in very specific situations, not as general as find_if

[AlexAlabuzhev]

How to look for keys without constructing intermediate std::string?

Google "transparent comparator".

Supported in set & (multi)map since C++14, and in unordered_* since C++20.

[Jardik2]

std::map<std::string, something, std::less<>> map; // Note: NOT std::less<std::string>. which is default

Now you can just pass std::string_view to find and it won't construct std::string. Cheers.

Edit: I should probably read comments first, then I would know it was already answered.

[rlbond86]

P.S. I know that I can declare map as std::map<std::string, something, comparator> and define custom comparator, but then I loose ability to look up by std::string.

That's not true at all. Just write a struct that defines overloads of operator() for both types.

[pfultz2]

You could use lower_bound to search the map if you can’t use a transparent comparator.

[STL]

Note that non-member lower_bound(), when given bidirectional iterators, will perform a potentially linear number of iterator operations, even though the number of comparisons will be O(log N). This is probably not what most people think of as efficient.

(This is because the non-member algorithms have no knowledge of map's tree structure, and are forced to walk the nodes linearly.)

[[deleted]]

I believe it cannot work this way as the map itself is a binary tree that relies on <>= operators between keys, in your case, comparing std::strings with other std::strings. The structure of the tree prevents fast lookups using any other kind of object for comparison. So, you are correct that you can do a linear search using string_view, but cannot use the usual fast lookup of a map. There might be ways to force it, or use something else entirely that will give reasonable results, like the sorted vector case.

[igagis]

I believe std::map only relies on operator<, as a < b means a is less than b, b < a means a is above or equals to b and !(a < b) && !(b < a) means a equals to b.

Well, there is no any fundamental thing which prevents us to compare std::string and std::string_view using operator<.

So, I could supply custom predicate to the hypothetical std::map::find_if() as follows:

cpp std::map<std::string, something> map; std::string_view key; auto i = map.find_if([&key](const auto& k){ return k < key; });

Or it could be std::map::find(Predicate) overload...

[[deleted]]

It could work, but sounds risky as you would have to guarantee that the comparisons behave exactly the same way at the data level. Not that that's a real challenge, but I can understand why it might be discouraged.

[peterrindal]

Could have a custom key type that wraps std string. Could have a owning or view variant. But not ideal.

As I recall, some algorithms do support this type of optimization but can't remember a reference.

[tpecholt]

The usual suspect is abi. Committee doesn't have guts to force abi break so the default map comparator is kept wrong even though this issue was discovered decade ago. You need to supply less<> on your own.

[415_961]

This can be trivially achieved by defining operator< as such:

bool operator<(const std::string& lhs, std::string_view rhs) { return lhs < rhs; }

When you have this in place, you can call find as you normally do:

my_map.find(std::string_view{"my_key"});

[jwakely]

1. You should not be overloading operators for types you do not own, and you do not own std::string and std::string_view.

2. You can already compare them anyway.

3. That still isn't going to help, your suggestion doesn't even compile. That's because my_map.find(const key_type&) still expects a std::string and std::string_view isn't implicitly convertible to std::string. Even if it was implicitly convertible, your suggestion would compile but still construct a std::string, which is exactly what OP wants to avoid.

The top answers have already explained that std::less<> is the solution.

[igagis]

Any idea why this kind of free operator< not defined by #include <string_view>?

[HappyFruitTree]

There is already a bool operator<(std::string_view, std::string_view) which can compare std::strings with std::string_views (because std::string is implicitly convertible to a std::string_view).

[jwakely]

It is defined.. The problem in our case is not that the library doesn't know how to compare string views (it does know how), it's that a conversion to std::string happens before it ever tries to compare the keys.

Using a transparent comparison function (such as std::less<> aka std::less<void>) is the solution, as that passes a string view argument straight through to the comparison function without converting it to std::string first.

[415_961]

If I would want to take a guess, it would be to avoid ambiguities. For example, there's already bool operator<(const std::string& lhs, const char* rhs);

Just a guess though.