STL question: where is find_first_not_of?

64 views
Skip to first unread message

Xiao-Hui Wu

unread,
Aug 30, 2001, 8:25:47 PM8/30/01
to
Hi,

I need to use something like std::find_first_not_of for a general
container. But I can only find such a function for std::string in
STL. Is there any reason for this?

Xiao-Hui

[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]

Hadrian Zbarcea

unread,
Aug 31, 2001, 2:08:48 PM8/31/01
to

"Xiao-Hui Wu" <x9...@hotmail.com> wrote in message
news:33084b89.01083...@posting.google.com...

> Hi,
>
> I need to use something like std::find_first_not_of for a general
> container. But I can only find such a function for std::string in
> STL. Is there any reason for this?

Try std::find_if.

Hadrian

Carl Barron

unread,
Sep 1, 2001, 3:57:34 PM9/1/01
to
better yet:
template <class For1,class For2>
For1 find_first_not_of(For1 begin1,For1 end1,For2 begin2,For2 end2)
{
return std::find_first_of(begin1,end1,begin2,end2,std::not1(
std::equal_to<typename
std::iterator_traits<For1>::value_type>()));
}


Hadrian Zbarcea wrote:

>"Xiao-Hui Wu" <x9...@hotmail.com> wrote in message
>news:33084b89.01083...@posting.google.com...
>
>>Hi,
>>
>>I need to use something like std::find_first_not_of for a general
>>container. But I can only find such a function for std::string in
>>STL. Is there any reason for this?
>>
>
>Try std::find_if.

[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]

David Leimbach

unread,
Sep 1, 2001, 4:04:51 PM9/1/01
to
Hadrian Zbarcea wrote:

>
> "Xiao-Hui Wu" <x9...@hotmail.com> wrote in message
> news:33084b89.01083...@posting.google.com...
>> Hi,
>>
>> I need to use something like std::find_first_not_of for a general
>> container. But I can only find such a function for std::string in
>> STL. Is there any reason for this?
>
> Try std::find_if.
>

Or find_first_of and write a predicate that finds the compliment of the set
being searched for. Think of it like writing a sort with the "less-than"
functor written as greater so it sorts in reverse order.

Xiao-Hui Wu

unread,
Sep 1, 2001, 8:21:59 PM9/1/01
to
"Hadrian Zbarcea" <hzba...@ieee.org> wrote in message news:<z4Oj7.42655$hT4.11...@news1.rdc1.md.home.com>...

> "Xiao-Hui Wu" <x9...@hotmail.com> wrote in message
> news:33084b89.01083...@posting.google.com...
> > Hi,
> >
> > I need to use something like std::find_first_not_of for a general
> > container. But I can only find such a function for std::string in
> > STL. Is there any reason for this?
>
> Try std::find_if.
>
> Hadrian
>

I may have to rephrase the question (I know there are other ways to
achieve the effect I want). Is there some subtle reaon that
find_first_of is available for general containers but not
find_first_not_of (both are available for std::string), or this is
just a careless omission by the standard? To me both functions are
simple to implement, then why favor one against the other.

Xiao-Hui

Carlos Moreno

unread,
Sep 2, 2001, 9:57:24 AM9/2/01
to

Xiao-Hui Wu wrote:
>
> I may have to rephrase the question (I know there are other ways to
> achieve the effect I want). Is there some subtle reaon that
> find_first_of is available for general containers but not
> find_first_not_of (both are available for std::string), or this is
> just a careless omission by the standard? To me both functions are
> simple to implement, then why favor one against the other.

Tell me about it... I can't complain enough about the omission
of copy_if in the STL...

Ironically, there is a copy_if_not (only that it is called
remove_copy_if -- talk about counter-intuitiveness: an algorithm
called remove* that does not remove at all :-( )

We should probably organize a protest march against these STL
omissions and inconsistencies -- c'mon guys, let's take our
banners and show up at the next ANSI committee reunion!!!
(don't bring any fire or bombs, please! :-))

Carlos
--

Francis Glassborow

unread,
Sep 2, 2001, 12:56:10 PM9/2/01
to
In article <3B91A290...@mochima.com>, Carlos Moreno
<mor...@mochima.com> writes

>We should probably organize a protest march against these STL
>omissions and inconsistencies -- c'mon guys, let's take our
>banners and show up at the next ANSI committee reunion!!!
>(don't bring any fire or bombs, please! :-))

Fine, see you in Redmond October 21-26 (Oh, please do bring the bombs, I
am sure our hosts will ensure that it is your last protest:). Those that
are unarmed will be welcome at the meeting as long as they are prepared
to do some of the work.

Seriously, a detailed listing of the inconsistencies and omissions is a
perfectly reasonable thing to offer for consideration.

Francis Glassborow ACCU
64 Southfield Rd
Oxford OX4 1PA +44(0)1865 246490
All opinions are mine and do not represent those of any organisation

Matt Messina

unread,
Sep 3, 2001, 5:58:37 AM9/3/01
to
Carlos Moreno <mor...@mochima.com> wrote:
>Tell me about it... I can't complain enough about the omission
>of copy_if in the STL...

copy_if seems like a no-brainer. I'd love to know the story behind:
"Unfortunately, copy_if() was somehow dropped from the set of
algorithms provided by the standard library (mea culpa)." (_C++PL3_,
S18.6.1) Was it voted out because some thought there were too many
algorithms? Or was it a copy-editing or bookkeeping error that
accidently got standardized?

On the other hand, adding filter iterators would give us the equivalent
of copy_if(), transform_if(), for_each_if(), and whatever_else_if(), all
for the "price" of adding just one "thing" to the standard library. But
filter iterators are more complicated than _if algorithms. (A filter
iterator iterating over [first,last) needs to know what last is so it
isn't filtered away.)
--
Matt Messina
mes...@yahoo.com

Matt Messina

unread,
Sep 3, 2001, 5:59:17 AM9/3/01
to
Carl Barron <cba...@adelphia.net> wrote:
> template <class For1,class For2>
> For1 find_first_not_of(For1 begin1,For1 end1,For2 begin2,For2 end2)
> {
> return std::find_first_of(begin1,end1,begin2,end2,std::not1(
> std::equal_to<typename
>std::iterator_traits<For1>::value_type>()));
> }

Wrong. Let's describe find_first_not_of as, "Find the first element of
a sequence that has no match in a second sequence." The above algorithm
finds the first element of a sequence not equal to *every* element in
a second sequence. That's only right if all the elements in the second
sequence are equivalent.


>Hadrian Zbarcea wrote:
>>Try std::find_if.

template<class ForIt>
class not_of_t
{
public:
not_of_t(ForIt first, ForIt last)
: first_(first), last_(last) { }
template<class T> bool operator()(const T& value) const
{ return (std::find(first_, last_, value) == last_); }
private:
ForIt first_, last_;
};

template<class ForIt>
not_of_t<ForIt> not_of(ForIt first, ForIt last)
{
return not_of_t<ForIt>(first, last);
}

template<class InIt, class ForIt>
InIt find_first_not_of(InIt first1, InIt last1, ForIt first2, ForIt last2)
{
return std::find_if(first1, last1, not_of(first2, last2));
}
--
Matt Messina
mes...@yahoo.com

John Potter

unread,
Sep 3, 2001, 12:09:22 PM9/3/01
to
On 1 Sep 2001 15:57:34 -0400, Carl Barron <cba...@adelphia.net> wrote:

> better yet:
> template <class For1,class For2>
> For1 find_first_not_of(For1 begin1,For1 end1,For2 begin2,For2 end2)
> {
> return std::find_first_of(begin1,end1,begin2,end2,std::not1(
> std::equal_to<typename
> std::iterator_traits<For1>::value_type>()));
> }

Maybe you should ask DeMorgan why the output of the following is 'A'.

int main () {
char test[] = "ABC";
char pat[] = "AB";
cout << *find_first_not_of(test, test + 3, pat, pat + 2) << endl;
}

I don't think there is any functor that will get find_first_of to do
find_first_not_of.

John

Carlos Moreno

unread,
Sep 3, 2001, 2:32:16 PM9/3/01
to

Matt Messina wrote:
>
> copy_if seems like a no-brainer. I'd love to know the story behind:
> "Unfortunately, copy_if() was somehow dropped from the set of
> algorithms provided by the standard library (mea culpa)." (_C++PL3_,
> S18.6.1)

You read my mind!! :-) After reading that very paragraph in TC++PL,
I had been meaning to write and ask exactly what Stroustrup meant by
that "mea culpa"? Is it that he asked that it be removed? Or is it
out of guilt for letting it happen? I've been curious... Hopefully,
some historian in this NG (:-)) will know details about this...?

Carlos
--

David Leimbach

unread,
Sep 3, 2001, 11:30:22 PM9/3/01
to
John Potter wrote:

[snip]


> I don't think there is any functor that will get find_first_of to do
> find_first_not_of.

Agreed.

It seems that find_first_of cannot be modified to be find_first_not_of with
just a functor change. find_first_of will stop when the functor is true:


template <class InputIterator, class ForwardIterator, class BinaryPredicate>
InputIterator find_first_of(InputIterator first1, InputIterator last1,
ForwardIterator first2, ForwardIterator last2,
BinaryPredicate comp);

Pseudocode:

for i in [first1, last1)
for j in [first2, last2)
if (comp(*i, *j) is true)
return *i

There is a different basic algorithm at the heart of find_first_not_of that
would require that the algorithm doesn't immediately terminate at the first
"truth of the predicate".

more pseudocode:
truth = false
for i in [first1, last1)
for j in [first2, last2)
if (comp(*i, *j) is true)
truth = true
else
truth = false
if (truth is true)
return *i

Basically we need to make sure that the current *i doesn't match any from
[first2, last2) in order to know that it is not of that set. Clearly
changing comp is not enough. I will have to retract my previous post about
it being a simple fix on find_first_of.

So why the heck isn't there find_first_not_of ? :)

Dave

Assaf Lavie

unread,
Sep 4, 2001, 7:10:33 AM9/4/01
to

"Carlos Moreno" <mor...@mochima.com> wrote in message
news:3B93B89A...@mochima.com...

>
> Matt Messina wrote:
> >
> > copy_if seems like a no-brainer. I'd love to know the story behind:
> > "Unfortunately, copy_if() was somehow dropped from the set of
> > algorithms provided by the standard library (mea culpa)." (_C++PL3_,
> > S18.6.1)
>
> You read my mind!! :-) After reading that very paragraph in TC++PL,
> I had been meaning to write and ask exactly what Stroustrup meant by
> that "mea culpa"? Is it that he asked that it be removed? Or is it
> out of guilt for letting it happen? I've been curious... Hopefully,
> some historian in this NG (:-)) will know details about this...?

"Effective STL" has some info about why it was dropped and how it can be
implemented in terms of remove_copy_if (IIRC).
Unfortunately I don't remember the exact details and I left the book at
home.

Carlos Moreno

unread,
Sep 4, 2001, 4:38:30 PM9/4/01
to

Assaf Lavie wrote:
>
> "Effective STL" has some info about why it was dropped and how it can be
> implemented in terms of remove_copy_if (IIRC).

Nope!! Actually, Scott Meyers somewhat sells this as an abominable,
unforgiveable omission by the standard!! (the emphasis and the exact
words are mine -- you know, since Scott said not long ago that he
wouldn't be reading the newsgroup these days, we can do this ;-))

And also, he does say that copy_if can NOT be (correctly) implemented
in terms of remove_copy_if (because the solution would require an
adaptable function object), and it mentions that even he once fell
for it and came up with that solution. He then presents the [only?]
valid solution, which is coding it manually (i.e., with a for or
while loop), as Bjarne Stroustrup does in his TC++PL.

Carlos
--

Nicola Musatti

unread,
Sep 5, 2001, 8:58:45 AM9/5/01
to

Carlos Moreno wrote:
[...]


> You read my mind!! :-) After reading that very paragraph in TC++PL,
> I had been meaning to write and ask exactly what Stroustrup meant by
> that "mea culpa"? Is it that he asked that it be removed? Or is it
> out of guilt for letting it happen? I've been curious... Hopefully,
> some historian in this NG (:-)) will know details about this...?

Maybe some of those in the know will put together this and other stories
for a future book in the "C++ In Depth" series: C++ Gossip :-)

Cheers,
Nicola Musatti

Bjarne Stroustrup

unread,
Sep 6, 2001, 4:19:52 PM9/6/01
to

Carlos Moreno <mor...@mochima.com> wrote

> Matt Messina wrote:
> >
> > copy_if seems like a no-brainer. I'd love to know the story behind:
> > "Unfortunately, copy_if() was somehow dropped from the set of
> > algorithms provided by the standard library (mea culpa)." (_C++PL3_,
> > S18.6.1)
>
> You read my mind!! :-) After reading that very paragraph in TC++PL,
> I had been meaning to write and ask exactly what Stroustrup meant by
> that "mea culpa"? Is it that he asked that it be removed? Or is it
> out of guilt for letting it happen? I've been curious... Hopefully,
> some historian in this NG (:-)) will know details about this...?

Before the STL was proposed to the committee, there was a meeting at HP
where Alex explained his ideas and half-a-dozen or so experienced library
builders and users discussed what was feasible and desirable. We decided
that for the STL to have any chance of acceptance it would have to be
stripped of about two thirds of its algorithms and function objects.
Those that were considered non-essential, "esoteric", hard to explain,
or hard to document couldn't be included in the standard.

Please note that nobody has ever doubted that this slimming down of the
STL was essential for the STL's acceptance. The sheer volume of the
documentation and the time needed to produce it would have doomed the
project.

I took the lead in that rather unpleasent exercise and cut "to the bone".
By and large, I'm not too unhappy with the result, but I shouldn't have
cut copy_if. My main defense is that I don't think anyone could have
cut the necessary amount without making at least one bad mistake.
To make amends, I featured copy_if in my book (and apologized).

- Bjarne
Bjarne Stroustrup - http://www.research.att.com/~bs

Carlos Moreno

unread,
Sep 6, 2001, 8:29:33 PM9/6/01
to

Bjarne Stroustrup wrote:
>
> (...)

> I took the lead in that rather unpleasent exercise and cut "to the bone".
> By and large, I'm not too unhappy with the result, but I shouldn't have
> cut copy_if. My main defense is that I don't think anyone could have
> cut the necessary amount without making at least one bad mistake.
> To make amends, I featured copy_if in my book (and apologized).

Thanks for sharing the anecdote with us!

I guess that now that the STL has been accepted and keeps taking more
and more momentum, it wouldn't hurt or bother anyone if the committe
decides to add it to the standard (it certainly would make a few
people happy!). The same argument could (should?) be used for the
OP's question (where is find_first_not_of?).

On the minus side, adding copy_if to the standard would render obsolete
one of the sections of Scott Meyers' "Effective STL" :-)

Thanks!

Carlos
--

Reply all
Reply to author
Forward
0 new messages