Re: iterate over vector in leaps

Discussion in 'C++' started by Alf P. Steinbach, Apr 12, 2010.

  1. * Baruch Burstein:
    > can I make an iterator in a vector iterate over, say, every third element?


    I should think so. Have you tried? If not, why not?


    Cheers & hth.,

    - Alf
    Alf P. Steinbach, Apr 12, 2010
    #1
    1. Advertising

  2. Baruch Burstein <> writes:
    > Let me explain. I want to pass an iterator of a vector to the sort
    > algorithim. I want to sort all the n-th items among themselves. How
    > can I use the vector::iterator? or do I need to create my own class
    > for it?


    IMHO, you will certainly need to implement your own custom iterator
    here. This will need careful handling, and will need to be implemented
    with significant differences compared to how you might implement an
    `ordinary' custom iterator. For instance, your iterator will need to
    maintain specific information about the vector that it is iterating over
    since it will need to handle checks against running over the ends.
    (This is not the case with, say, std::vector<T>::iterator since its use
    requires that the user code do this type of checking.)

    The following is a quick-and-dirty example of how you might begin to
    implement such an iterator. I do not present this as necessarily the
    right way to do this, and it won't work as-is with std::sort since it
    doesn't provide all the overloaded operators required of a random access
    iterator. However, it might give you enough ideas to enable you to
    decide if this is indeed the right way to go. Note: I say this because
    I am wondering if you are actually tied to using a vector here, and
    whether you have considered whether std::valarray might not better suit
    your needs. I realise that valarray has something of a `bad press' and
    there had even been calls (I believe) to deprecate it. However, it does
    permit viewing the container in `slices', which seems to fit,
    conceptually at least, with what you are trying to achieve.

    Example code below.

    Regards

    Paul Bibbings

    ==# Example code #==
    #include <cstddef>
    #include <iostream>
    #include <vector>
    #include <iterator>

    template<typename T>
    struct nth_iterator
    : public std::iterator<
    typename std::vector<T>::iterator::iterator_category,
    T,
    typename std::vector<T>::iterator::difference_type,
    typename std::vector<T>::iterator::pointer,
    typename std::vector<T>::iterator::reference
    >

    {
    typedef typename std::vector<T>::iterator v_iterator;

    typedef typename v_iterator::iterator_category iterator_category;
    typedef T value_type;
    typedef typename v_iterator::difference_type difference_type;
    typedef typename v_iterator::pointer pointer;
    typedef typename v_iterator::reference reference;

    nth_iterator(typename std::vector<T>& vec,
    v_iterator iter,
    size_t step)
    : vec_(vec)
    , iter_(iter)
    , step_(step)
    { }

    nth_iterator& operator++() {
    size_t i = 0;
    while (i < step_ && iter_ != vec_.end())
    {
    ++iter_; ++i;
    }
    return *this;
    }

    bool operator==(const v_iterator& rhs) {
    return iter_ == rhs;
    }

    bool operator!=(const v_iterator& rhs) {
    return iter_ != rhs;
    }

    T& operator*() { return *iter_; }
    private:
    typename std::vector<T>& vec_;
    v_iterator iter_;
    size_t step_;
    };

    void print_i_vec(const std::vector<int>& ci_vec)
    {
    for (std::vector<int>::const_iterator civ_iter = ci_vec.begin();
    civ_iter != ci_vec.end();
    ++civ_iter)
    {
    std::cout << *civ_iter << ' ';
    }
    std::cout << '\n';
    }

    int main()
    {
    std::vector<int> i_vec;

    for (int i = 1; i <= 10; ++i) i_vec.push_back(i);

    print_i_vec(i_vec);

    for (nth_iterator<int> nth_iter(i_vec, i_vec.begin(), 3);
    nth_iter != i_vec.end();
    ++nth_iter)
    {
    *nth_iter = 0;
    }

    print_i_vec(i_vec);

    return 0;
    }

    /* Output:
    14:25:02 Paul Bibbings@JIJOU
    /cygdrive/d/CPPProjects/CLCPP $./nth_iterator_vec
    1 2 3 4 5 6 7 8 9 10
    0 2 3 0 5 6 0 8 9 0
    */

    ==# End: Example code #==
    Paul Bibbings, Apr 12, 2010
    #2
    1. Advertising

  3. Alf P. Steinbach

    Kai-Uwe Bux Guest

    Baruch Burstein wrote:

    > On Apr 12, 1:50 pm, "Leigh Johnston" <> wrote:
    >> "Baruch Burstein" <> wrote in message
    >>
    >> news:hputa5$ufl$...
    >>
    >> > Let me explain. I want to pass an iterator of a vector to the sort
    >> > algorithim. I want to sort all the n-th items among themselves. How can
    >> > I use the vector::iterator? or do I need to create my own class for it?

    >>
    >> Yes make your own iterator and make sure you don't go off the end of the
    >> sequence (ensure you get the end() iterator right).
    >>
    >> /Leigh

    >
    > Could I inherit from vector::iterator as a public base class, and just
    > overwrite the ++,+=,--,-= operators? (I would just try it, but I'm not
    > at home at the moment)


    a) The standard does not guarantee you that you can derive from
    std::vector<T>::iterator. Whether you can or cannot depends on the
    implementation.

    b) If your implementation allows derivation from std::vector::iterator, you
    still need to handle the case of incrementing past end().


    Best

    Kai-Uwe Bux
    Kai-Uwe Bux, Apr 12, 2010
    #3
  4. Alf P. Steinbach

    Kai-Uwe Bux Guest

    Leigh Johnston wrote:

    >
    >
    > "Leigh Johnston" <> wrote in message
    > news:...
    >> "Kai-Uwe Bux" <> wrote in message
    >> news:hpveuv$ekf$...
    >>> Baruch Burstein wrote:
    >>>
    >>> a) The standard does not guarantee you that you can derive from
    >>> std::vector<T>::iterator. Whether you can or cannot depends on the
    >>> implementation.
    >>>

    >>
    >> Good point, std::vector<T>::iterator could be a plain pointer and for
    >> this reason you should probably never derive from standard container
    >> iterators, if you do your code will 1) not be portable and 2) not be
    >> generic (allowing derivation from one type of container's iterators and
    >> not
    >> another is inconsistent). Better to use composition in this case.
    >>

    >
    > Actually I am not sure I totally agree with point 2) of what I just said,
    > if your code is specific to a particular container then I guess deriving
    > from that container's iterator is OK if said iterators will always be of
    > class type (which should be the case for the node based containers).


    Well, as a practical matter, derivation is unlikely to be a problem with
    node-based containers.

    Technically, the standard defines the type iterator as "implementation
    defined". As a consequence, even as a class, it could be implemented in a
    way that prevents derivation (either using well-known trickery or compiler
    magic such as a __final keyword). However, an implementation has to go
    through some length to prevent derivation. (On the other hand, libraries
    implementing concept check go through some length to prevent code that would
    otherwise be working.)


    Best

    Kai-Uwe Bux
    Kai-Uwe Bux, Apr 12, 2010
    #4
  5. On Apr 12, 11:58 am, Juha Nieminen <> wrote:
    > On 04/12/2010 01:40 PM, Baruch Burstein wrote:
    >
    > > Let me explain. I want to pass an iterator of a vector to the sort
    > > algorithim. I want to sort all the n-th items among themselves. How can
    > > I use the vector::iterator? or do I need to create my own class for it?

    >
    > Since std::vector defines a random access iterator, you can use the +=
    > operator to jump forward more than one element (or -= to jump
    > backwards). You can also use the <= operator to compare an iterator with
    > the end iterator (to see if it passed it).


    Values past end() are undefined behavior. Ie

    i += n ;

    is undefined if (end - i) < n. (Think if the iterator is
    a built-in pointer to a built-in array then C++ guarantees
    only that the pointer can hold a value one past the last
    element of the array without undefined behavior.)

    So the trouble is that somewhere you have to first check
    n against end() or otherwise guarantee the iterator will
    not pass end() /before/ doing +=. In that context it seems
    that <= would have very little use /even if/ it were valid
    to have iterators past end().

    Regardless <= might as well be == for values past end()
    since one has already entered UB land.

    KHD
    Keith H Duggar, Apr 12, 2010
    #5
  6. Alf P. Steinbach

    SG Guest

    On 12 Apr., 15:52, Baruch Burstein wrote:
    >
    > Could I inherit from vector::iterator as a public base class, and just
    > overwrite the ++,+=,--,-= operators? (I would just try it, but I'm not
    > at home at the moment)


    I'm not 100% sure but it seems the Boost.Iterator library offers a
    class template (iterator_adaptor) which can help you.

    <http://www.boost.org/doc/libs/1_42_0/libs/iterator/doc/index.html>

    "The user of iterator_adaptor creates a class derived from an
    instantiation of iterator_adaptor and then selectively redefines
    some of the core member functions described in the iterator_facade
    core requirements table."

    The relevant functions you have to "redefine" in this case are
    increment, decrement and advance. All the operators (==, !=, ++, --,
    +=, -=, -, *, ->, [], etc) are automatically generated.

    Cheers,
    SG
    SG, Apr 12, 2010
    #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. Gogo
    Replies:
    1
    Views:
    2,088
    Sudsy
    Sep 4, 2003
  2. runescience
    Replies:
    0
    Views:
    1,444
    runescience
    Feb 9, 2006
  3. Replies:
    8
    Views:
    1,896
    Csaba
    Feb 18, 2006
  4. foxx
    Replies:
    4
    Views:
    553
    Marcus Kwok
    Nov 9, 2006
  5. foxx
    Replies:
    2
    Views:
    1,015
    Mark P
    Nov 9, 2006
Loading...

Share This Page