Looking up std::string keys with base::StringPiece

[Roland Bock]

Hi,

Assume 

std::set<std::string> my_set;

std::unordered_set<std::string> my_unorderd_set;

base::StringPiece key("sample");

Is there a way to do 

my_set.find(key);

my_unordered_set.find(key);

without converting the key to std::string?

If the answer is no, do we have alternative containers that would allow us to do so?

Thanks,

Roland

[dan...@chromium.org]

This was solved in C++14 by transparent comparators: https://www.fluentcpp.com/2017/06/09/search-set-another-type-key/

--
--
Chromium Developers mailing list: chromi...@chromium.org
View archives, change email options, or unsubscribe:
http://groups.google.com/a/chromium.org/group/chromium-dev
---
You received this message because you are subscribed to the Google Groups "Chromium-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to chromium-dev...@chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/chromium-dev/CAHq1K7QPiY%3DsgXU_%3DoOhe71Ty_9DrgfoXaZ8XpEMQuOrMZznLQ%40mail.gmail.com.

[Jeremy Roman]

i.e., for the former, use std::set<std::string, std::less<>>

I actually don't think there's a concise way to do the same for std::unordered_set, though.

Some of our other containers, like base::flat_map, use transparent comparators by default. 

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/chromium-dev/CAHtyhaSh6zPW7OFoqgcaJbS7LrfiZZ2tkomFKYs67Q0wZ-Prtg%40mail.gmail.com.

[Roland Bock]

On Fri, Sep 16, 2022 at 5:48 PM Jeremy Roman <jbr...@chromium.org> wrote:

i.e., for the former, use std::set<std::string, std::less<>>

I see, that's neat :-)

 

I actually don't think there's a concise way to do the same for std::unordered_set, though.

That might be possible with C++20 if the hash functions are equivalent.

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

 

Some of our other containers, like base::flat_map, use transparent comparators by default. 

Thanks for the pointer!

--

--

Roland Bock

Software Engineering Manager

rb...@google.com

Google Germany GmbH

Erika-Mann-Straße 33

80636 München

Geschäftsführer: Paul Manicle, Liana Sebastian

Registergericht und -nummer: Hamburg, HRB 86891

Sitz der Gesellschaft: Hamburg

This e-mail is confidential. If you received this communication by mistake, please don't forward it to anyone else, please erase all copies and attachments, and please let me know that it has gone to the wrong person.

The above terms reflect a potential business arrangement, are provided solely as a basis for further discussion, and are not intended to be and do not constitute a legally binding obligation. No legally binding obligations will be created, implied, or inferred until an agreement in final form is executed in writing by all parties involved.

[Daniel Cheng]

On Fri, 16 Sept 2022 at 08:53, 'Roland Bock' via Chromium-dev <chromi...@chromium.org> wrote:

On Fri, Sep 16, 2022 at 5:48 PM Jeremy Roman <jbr...@chromium.org> wrote:

i.e., for the former, use std::set<std::string, std::less<>>

I see, that's neat :-)

 

I actually don't think there's a concise way to do the same for std::unordered_set, though.

That might be possible with C++20 if the hash functions are equivalent.

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

We should rarely be using unordered_set and unordered_map, FWIW :)

Daniel

 

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/chromium-dev/CAHq1K7RK-xnc9i41_S0naN8Ri0d7qDoAqO-s9amH0-3fXEhrGQ%40mail.gmail.com.

[Roland Bock]

On Fri, Sep 16, 2022 at 5:56 PM Daniel Cheng <dch...@chromium.org> wrote:

On Fri, 16 Sept 2022 at 08:53, 'Roland Bock' via Chromium-dev <chromi...@chromium.org> wrote:

On Fri, Sep 16, 2022 at 5:48 PM Jeremy Roman <jbr...@chromium.org> wrote:

i.e., for the former, use std::set<std::string, std::less<>>

I see, that's neat :-)

 

I actually don't think there's a concise way to do the same for std::unordered_set, though.

That might be possible with C++20 if the hash functions are equivalent.

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

We should rarely be using unordered_set and unordered_map, FWIW :)

Daniel

Hi Daniel,

I am looking into replacing 

PrefService::GetValue(const std::string&) with PrefService::GetValue(base::StringPiece);

as you suggested a while ago. And for the same reasons, it seems to make sense to replace 

PrefService::FindPreference(const std::string&) with PrefService::FindPreference(const std::string&)

The former is using std::set and std::map, the latter is using std::unordered_map

Cheers,

Roland

 

 

[K. Moon]

Abseil's unordered containers already support heterogeneous access (https://abseil.io/tips/144), which might be another good reason to consider allowing them.

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/chromium-dev/CAHq1K7Q9fd-4wYwR1qYFVjBWvZCzHpqdXwkfM1dVDwH8SPiKfw%40mail.gmail.com.

[Roland Bock]

On Sat, Sep 17, 2022 at 1:32 PM K. Moon <km...@chromium.org> wrote:

Abseil's unordered containers already support heterogeneous access (https://abseil.io/tips/144), which might be another good reason to consider allowing them.

Even if we did, base::StringPieceHash is significantly different from std::hash<std::string>, isn't it?

So we would also have to wait until we replace base::StringPiece with std::string_view?

[Daniel Cheng]

absl doesn't use std::hash. IIRC, the Swiss Table maps are quite sensitive to the strength of the hashing functionality, plus there were concerns over the composability of std::hash.

I'm actually not sure about the exact mechanism for configuring heterogeneous lookup for absl containers; for starters, it looks like the hashers for all string-like objects yield the same hash value for the same character sequence: https://source.chromium.org/chromium/chromium/src/+/main:third_party/abseil-cpp/absl/hash/internal/hash.h;l=512;drc=6c9d33d6a27dfb75bed218615240acf6278dc332. In any case, I don't think this would be a blocker for supporting heterogeneous lookup of std::string from base::StringPiece.

Daniel