Boost logo

Boost :

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.

Boost list run by bdawes at, gregod at, cpdaniel at, john at