standard library algorithms

[sks_cpp]

Are the standard library functions pertinent to both sequence containers and
associative containers?

For example, if "find_if", "remove_if" , etc... valid for both lists, deques,
vectors, sets, and maps?

I know that the word "iterator" is typedef'd from something for everyone of
these containers so I was curious if all these functions are valid.

On the same note, should I use "find_if" or "remove_if" for the following
template:

template <class AssociativeCont ainer, class Predicate>
inline void remove_if(Assoc iativeContainer & C, Predicate pred,
class associative_con tainer_tag)
{
typedef typename AssociativeCont ainer::iterator iterator;
iterator cur = c.begin();
const iterator last = c.end();

while ( (cur = std::find_if(cu r, last, pred)) != last)
{
iterator tmp = cur++;
c.erase(tmp);
}
}

[Buster Copley]

Re: standard library algorithms

sks_cpp wrote:[color=blue]
> Are the standard library functions pertinent to both sequence containers and
> associative containers?
>
> For example, if "find_if", "remove_if" , etc... valid for both lists, deques,
> vectors, sets, and maps?[/color]

These two functions take two objects of some forward iterator type as
arguments (the first forward iterator must be mutable). A container
which provides forward iterators is called a forward container.
Therefore, find_if can be used with any forward container. The same
applies to remove_if but the forward iterator type has to be a mutable
iterator type as well, so you have to have a mutable container.

You get a mutable container just by declaring it non-const. Mutable
iterators (e.g. vector <int>::iterator ) come from mutable containers.
A container that is declared const is not a mutable container, and the
iterators that come from them are not mutable. For example, `vector
<int>::const_it erator' is different from `const vector <int>::iterator '.

All five of the containers you mention are forward containers, so yes,
you can use both functions with all of the containers. In addition, a
pointer is a random access iterator and so certainly a forward iterator,
so you can use find_if with an array by passing pointers to the first
and one-past-the-end elements. You can also pass pointers to remove_if
too if the pointers are non-const.
[color=blue]
> I know that the word "iterator" is typedef'd from something for everyone of
> these containers so I was curious if all these functions are valid.[/color]

SGI's online documentation on the STL, which see, organizes classes into
concepts. It's a useful way of thinking about the C++ Standard Library's
containers and algorithms, and answering questions like this.
[color=blue]
> On the same note, should I use "find_if" or "remove_if" for the following
> template:[/color]

You should use std::remove_if. It might also be an idea to call your
template something other than remove_if, because everyone knows what
remove_if does, and this isn't it.
[color=blue]
>
> template <class AssociativeCont ainer, class Predicate>
> inline void remove_if(Assoc iativeContainer & C, Predicate pred,
> class associative_con tainer_tag)
> {
> typedef typename AssociativeCont ainer::iterator iterator;
> iterator cur = c.begin();
> const iterator last = c.end();
>
> while ( (cur = std::find_if(cu r, last, pred)) != last)
> {
> iterator tmp = cur++;
> c.erase(tmp);
> }
> }
>
>[/color]

In that final function parameter, the `class' keyword class is redundant
(unless the name associative_con tainer_tag is also in scope as an
identifier for something which is not a class or a template class, in
which case I give up). You declare an unnamed parameter of type
`associative_co ntainer_tag'.

Luckily, you don't need a tag in this instance, because an associative
container is a forward container.

Try

template <typename ForwardContaine r, typename Pred>
inline void erase_if (ForwardContain er & c, Pred & p)
{
c.erase (c.begin (), std::remove_if (c.begin (), c.end (), p);
}

You could provide a version that works for, say, a stack using partial
specialization, still without using a tag class. Having said that, I
hope you never feel the need to apply this algorithm to a stack.

Regards,
Buster

[sks_cpp]

Re: standard library algorithms

> > For example, if "find_if", "remove_if" , etc... valid for both lists,
deques,[color=blue][color=green]
> > vectors, sets, and maps?[/color]
>
> These two functions take two objects of some forward iterator type as
> arguments (the first forward iterator must be mutable). A container
> which provides forward iterators is called a forward container.
> Therefore, find_if can be used with any forward container. The same
> applies to remove_if but the forward iterator type has to be a mutable
> iterator type as well, so you have to have a mutable container.
>
> All five of the containers you mention are forward containers, so yes,
> you can use both functions with all of the containers. In addition, a
> pointer is a random access iterator and so certainly a forward iterator,
> so you can use find_if with an array by passing pointers to the first
> and one-past-the-end elements. You can also pass pointers to remove_if
> too if the pointers are non-const.[/color]


According to this article http://www.adtmag.com/joop/crarticle.asp?ID=850
you can't use "remove_if" or "remove" on a set or a map.
Is the article incorrect?

[Buster Copley]

Re: standard library algorithms

sks_cpp wrote:[color=blue][color=green][color=darkred]
>>>For example, if "find_if", "remove_if" , etc... valid for both lists,[/color][/color]
> deques, vectors, sets, and maps?[color=green]
>>
>>These two functions take two objects of some forward iterator type as
>>arguments (the first forward iterator must be mutable). A container
>>which provides forward iterators is called a forward container.
>>Therefore, find_if can be used with any forward container. The same
>>applies to remove_if but the forward iterator type has to be a mutable
>>iterator type as well, so you have to have a mutable container.
>>
>>All five of the containers you mention are forward containers, so yes,
>>you can use both functions with all of the containers. In addition, a
>>pointer is a random access iterator and so certainly a forward iterator,
>>so you can use find_if with an array by passing pointers to the first
>>and one-past-the-end elements. You can also pass pointers to remove_if
>>too if the pointers are non-const.[/color]
>
> According to this article http://www.adtmag.com/joop/crarticle.asp?ID=850
> you can't use "remove_if" or "remove" on a set or a map.
> Is the article incorrect?[/color]

No, the article is correct, and so are you. So is SGI's documentation.
I'm mostly right (which is to say I'm wrong). All I failed to notice was
that the iterators passed to remove_if are required to be mutable, but
the iterators provided by associative containers are constant.

I can't see which was the question you don't already know the answer to,
but I'll be happy if I can help.

Buster

[sks_cpp]

Re: standard library algorithms

"Buster Copley" <buster@none.co m> wrote in message
news:be88l7$omq $1@newsg4.svr.p ol.co.uk...[color=blue]
> No, the article is correct, and so are you. So is SGI's documentation.
> I'm mostly right (which is to say I'm wrong). All I failed to notice was
> that the iterators passed to remove_if are required to be mutable, but
> the iterators provided by associative containers are constant.
>
> I can't see which was the question you don't already know the answer to,
> but I'll be happy if I can help.[/color]

I just read in the "Associate Containers" section that keys are immutable.
So, for sets the value_type is not mutable and for maps, the key part of the
value_type is not mutable.

Well, if REMOVE_IF is not valid for a set then COPY shouldn't be either
since for COPY function, you have to assign from one container to another.
Right?

template <class InputIterator, class OutputIterator>
OutputIterator copy(InputItera tor first, InputIterator last, OutputIterator
result);
<standard header algorithm>
Copy copies elements from the range [first, last) to the range [result,
result + (last - first)). That is, it performs the assignments *result =
*first, *(result + 1) = *(first + 1), and so on. Generally, for every
integer n from 0 to last - first, copy performs the assignment *(result + n)
= *(first + n). Assignments are performed in forward order, i.e. in order of
increasing n.

I know I am wrong here so someone please explain to me what I am missing.

Thanks.

[Sam Holden]

Re: standard library algorithms

On Sun, 06 Jul 2003 17:48:28 GMT, sks_cpp <sksjava@hotmai l.com> wrote:[color=blue]
> "Buster Copley" <buster@none.co m> wrote in message
> news:be88l7$omq $1@newsg4.svr.p ol.co.uk...[color=green]
>> No, the article is correct, and so are you. So is SGI's documentation.
>> I'm mostly right (which is to say I'm wrong). All I failed to notice was
>> that the iterators passed to remove_if are required to be mutable, but
>> the iterators provided by associative containers are constant.
>>
>> I can't see which was the question you don't already know the answer to,
>> but I'll be happy if I can help.[/color]
>
> I just read in the "Associate Containers" section that keys are immutable.
> So, for sets the value_type is not mutable and for maps, the key part of the
> value_type is not mutable.
>
> Well, if REMOVE_IF is not valid for a set then COPY shouldn't be either
> since for COPY function, you have to assign from one container to another.
> Right?[/color]

Yes. (Though copy doesn't work on containers, it works on iterators which
don't necessarily have a container behind them...)

copy isn't valid using a set iterator as the destination (you can use
an insert_iterator just fine, though).

--
Sam Holden