standard library algorithms

S

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 AssociativeContainer, class Predicate>
inline void remove_if(AssociativeContainer& C, Predicate pred,
class associative_container_tag)
{
typedef typename AssociativeContainer::iterator iterator;
iterator cur = c.begin();
const iterator last = c.end();

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

Buster Copley

sks_cpp said:
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?

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_iterator' 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.
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.

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.
On the same note, should I use "find_if" or "remove_if" for the following
template:

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.
template <class AssociativeContainer, class Predicate>
inline void remove_if(AssociativeContainer& C, Predicate pred,
class associative_container_tag)
{
typedef typename AssociativeContainer::iterator iterator;
iterator cur = c.begin();
const iterator last = c.end();

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

In that final function parameter, the `class' keyword class is redundant
(unless the name associative_container_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_container_tag'.

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

Try

template <typename ForwardContainer, typename Pred>
inline void erase_if (ForwardContainer & 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
 
S

sks_cpp

For example, if "find_if", "remove_if", etc... valid for both lists,
deques,
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.


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?
 
B

Buster Copley

sks_cpp said:
deques, vectors, sets, and maps?

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?

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
 
S

sks_cpp

Buster Copley said:
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.

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(InputIterator 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.
 
S

Sam Holden

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?

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).
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top