Re: [boost] Boost.Algorithm design question

Subject: Re: [boost] Boost.Algorithm design question
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2011-10-06 12:27:16

Thorsten Ottosen wrote:
> Den 06-10-2011 00:53, Stephan T. Lavavej skrev:
>> [Marshall Clow]
>>> So, what do people prefer (and why?):
>>
>>> template<typename InputIterator, typename V> bool none_of_equal (
>>> InputIterator first, InputIterator last, V const&val )
>>
>>> or
>>
>>> template<typename InputIterator,> bool none_of_equal (
>>> InputIterator first, InputIterator last,
>>> iterator_traits<InputIterator>::value_type const&val )
>>
>>> In the first case, I think there's (possible) conversion from V to
>>> iterator_traits<InputIterator>::value_type each time through the
>>> loop. In the second case, there is not.
>>
>> #1 is better. It follows the STL's conventions (e.g. look at
>> std::find()) and permits heterogeneous comparisons.
>>
>> Consider vector<string>  and val being "meow". string is directly
>> comparable to const char *, without any conversions or temporaries.
>>
>> Even better, consider vector<const char *>  and val being a string.
>> Here, the element type is still directly comparable to val's type,
>> but val's type is not implicitly convertible to the element type.
>
> Even better, don't use vector<const char*>. What o you need that for?

Here's a real motivating example where I want to use vector<const 
char*>.  I have a large file containing null-terminated strings which I 
memory map.  After opening the file, I construct some sort of index of 
those strings in a sorted vector.  Then I search for things using 
std::equal_range, std::lower_bound, or similar.

The important thing is that for efficiency the algorithms mustn't 
create temporary strings; they must compare the const char* with the 
string that I'm searching for directly.  std::string provides operator 
overloads to do this.  I want the algorithms to use those heterogeneous comparisons.

Dave Abrahams has said a couple of times that he doesn't even know what 
it means to try to do this.  This baffles me, but I trust that there is 
some validity in his argument.  But it does lead me to the point that I 
made in my review, and my answer to Marshall's question at the start of 
this thread: I don't want Boost to waste time on either of those 
none_of_equal implementations.  We are all capable of writing our own 
4-line none_of_equal implementations that do precisely what we want 
them to do.  Why argue about which is the "one true way" to do it, when 
we can all have whichever one we prefer?  Instead, let's spend time on 
things where the implementation is more than 4 lines long - like a 
variant of std::list with O(1) splice!

Regards,  Phil.