1

std::map::find accepts const key_type& as an argument. This way it requires the argument to be convertible to key_type. That seems an oversight to me because the argument doesn't have to be convertible to key_type, it only has to be comparable to it.

I can make an arbitrary type comparable by defining two operator< overloads:

struct A;
bool operator<(const key_type&, const A&);
bool operator<(const A&, const key_type&);

map::find should itself be a template. But it's not. So now that I'm done whining I can ask the actual question: is there a way to easily work around this and search among map keys by a comparable but not convertible value?

My understanding is I could use std::find_if, but that would be linear search instead of binary search (O(n) instead of O(Log(N))). Naturally, I don't want to implement binary search by hand.

Violet Giraffe
  • 32,368
  • 48
  • 194
  • 335
  • 2
    http://stackoverflow.com/questions/20317413/what-are-transparent-comparators – LogicStuff Jun 28 '16 at 10:17
  • 2
    For C++11 I do not see any way (besides digging into the internal implementation) than altering the key_type (introducing a proxy) –  Jun 28 '16 at 10:35

1 Answers1

2

Since C++14, map::find is in fact a template and works exactly as you desire (at least when the given Compare::is_transparent condition described below is satisfied).

From cppreference:

std::map::find

C++ Containers library std::map

iterator find(const Key& key ); (1)

const_iterator find( const Key& key ) const; (2)

template< class K > iterator find( const K& x ); (3) (since C++14)

template< class K > const_iterator find( const K& x ) const; (4) (since C++14)

1,2) Finds an element with key equivalent to key.

3,4) Finds an element with key that compares equivalent to the value x. This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. It allows calling this function without constructing an instance of Key

Smeeheey
  • 9,906
  • 23
  • 39
  • Okay, but if I'm stuck with a C++11 compiler, what are my options? – Violet Giraffe Jun 28 '16 at 10:20
  • 2
    To be clear, `find` is only a template *if* the comparator is transparent, and the default comparator is not transparent. – Kerrek SB Jun 28 '16 at 10:27
  • Your options are to upgrade to a C++14 compiler. – Sam Varshavchik Jun 28 '16 at 10:48
  • 1
    @SamVarshavchik no, transparent comparators are implementable in C++11. OP just needs to use an alternative standard library with C++14 features. – ecatmur Jun 28 '16 at 11:08
  • @ecatmur Changing standard library seems like a *larger* commitment than changing complier. Seems more likely to break things... – Yakk - Adam Nevraumont Jun 28 '16 at 13:46
  • @Yakk that's dependent on circumstance. Also, you don't need a whole standard library, just the specific container. Boost.Container could be a starting point for a reimplementation; it doesn't have transparent comparators ATM, but they'd be easy enough to add, and I'm sure they'd accept an implementation if someone were to code one. – ecatmur Jun 28 '16 at 13:56