Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > standard library algorithms

Reply
Thread Tools

standard library algorithms

 
 
sks_cpp
Guest
Posts: n/a
 
      07-05-2003
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);
}
}


 
Reply With Quote
 
 
 
 
Buster Copley
Guest
Posts: n/a
 
      07-05-2003
sks_cpp wrote:
> 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

 
Reply With Quote
 
 
 
 
sks_cpp
Guest
Posts: n/a
 
      07-06-2003
> > 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.
>
> 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?


 
Reply With Quote
 
Buster Copley
Guest
Posts: n/a
 
      07-06-2003
sks_cpp wrote:
>>>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.
>>
>>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?


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

 
Reply With Quote
 
sks_cpp
Guest
Posts: n/a
 
      07-06-2003
"Buster Copley" <(E-Mail Removed)> wrote in message
news:be88l7$omq$(E-Mail Removed)...
> 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.


 
Reply With Quote
 
Sam Holden
Guest
Posts: n/a
 
      07-06-2003
On Sun, 06 Jul 2003 17:48:28 GMT, sks_cpp <(E-Mail Removed)> wrote:
> "Buster Copley" <(E-Mail Removed)> wrote in message
> news:be88l7$omq$(E-Mail Removed)...
>> 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?


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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
add pexpect to the standard library, standard "install" mechanism. funkyj Python 5 01-20-2006 08:35 PM
ANN: pygene0.12 - Genetic Programming&Algorithms Library aum Python 1 12-11-2005 07:35 PM
How standard is the standard library? steve.leach Python 1 04-18-2005 04:07 PM
Computational Geometry Algorithms Library (CGAL) bindings for Python? Dennis Benzinger Python 0 06-16-2004 07:19 PM
JGraphT - a free Java library of graph-theory objects and algorithms Barak Java 0 08-07-2003 10:07 AM



Advertisments