standard library algorithms

Discussion in 'C++' started by sks_cpp, Jul 5, 2003.

  1. sks_cpp

    sks_cpp Guest

    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);
    }
    }
    sks_cpp, Jul 5, 2003
    #1
    1. Advertising

  2. 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
    Buster Copley, Jul 6, 2003
    #2
    1. Advertising

  3. sks_cpp

    sks_cpp Guest

    > > 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?
    sks_cpp, Jul 6, 2003
    #3
  4. 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
    Buster Copley, Jul 6, 2003
    #4
  5. sks_cpp

    sks_cpp Guest

    "Buster Copley" <> wrote in message
    news:be88l7$omq$...
    > 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.
    sks_cpp, Jul 6, 2003
    #5
  6. sks_cpp

    Sam Holden Guest

    On Sun, 06 Jul 2003 17:48:28 GMT, sks_cpp <> wrote:
    > "Buster Copley" <> wrote in message
    > news:be88l7$omq$...
    >> 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
    Sam Holden, Jul 6, 2003
    #6
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Barak
    Replies:
    0
    Views:
    810
    Barak
    Aug 7, 2003
  2. steve.leach

    How standard is the standard library?

    steve.leach, Apr 18, 2005, in forum: Python
    Replies:
    1
    Views:
    392
    Christos TZOTZIOY Georgiou
    Apr 18, 2005
  3. aum
    Replies:
    1
    Views:
    340
  4. funkyj
    Replies:
    5
    Views:
    1,128
    funkyj
    Jan 20, 2006
  5. Michael McGarry

    Open Source C Algorithms Library

    Michael McGarry, Apr 14, 2006, in forum: C Programming
    Replies:
    4
    Views:
    395
    Michael McGarry
    Apr 18, 2006
Loading...

Share This Page