Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Re: iterate over vector in leaps

Reply
Thread Tools

Re: iterate over vector in leaps

 
 
Alf P. Steinbach
Guest
Posts: n/a
 
      04-12-2010
* 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
 
Reply With Quote
 
 
 
 
Paul Bibbings
Guest
Posts: n/a
 
      04-12-2010
Baruch Burstein <(E-Mail Removed)> 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:ointer,
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:ointer 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 #==
 
Reply With Quote
 
 
 
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      04-12-2010
Baruch Burstein wrote:

> On Apr 12, 1:50 pm, "Leigh Johnston" <(E-Mail Removed)> wrote:
>> "Baruch Burstein" <(E-Mail Removed)> wrote in message
>>
>> news:hputa5$ufl$(E-Mail Removed)...
>>
>> > 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

 
Reply With Quote
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      04-12-2010
Leigh Johnston wrote:

>
>
> "Leigh Johnston" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
>> "Kai-Uwe Bux" <(E-Mail Removed)> wrote in message
>> news:hpveuv$ekf$(E-Mail Removed)...
>>> 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

 
Reply With Quote
 
Keith H Duggar
Guest
Posts: n/a
 
      04-12-2010
On Apr 12, 11:58 am, Juha Nieminen <(E-Mail Removed)> 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
 
Reply With Quote
 
SG
Guest
Posts: n/a
 
      04-12-2010
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
 
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
Iterate over a vector or vectors, etc foxx C++ 4 11-09-2006 09:08 PM
Iterate over a vector of vectors, etc foxx C++ 2 11-09-2006 06:47 PM
Free memory allocate by a STL vector, vector of vector, map of vector Allerdyce.John@gmail.com C++ 8 02-18-2006 12:48 AM
nested:iterate or logic: iterate with multibox?? runescience Java 0 02-09-2006 12:57 AM
<logic:iterate /> iterate beyond items in the collection Gogo Java 1 09-04-2003 08:40 PM



Advertisments