pair_iterator

[Vlad from Moscow]

Did anybody make a proposal about something as pair_iterator.

 

As an idea: the pair_iterator incorporates two iterators and its value_type is std::pair<typename Iterator1::value_type, typename Iterator2::value_type> 

 

For example

 

[code]

 

const size_t N = 10;

int a[N], b[N], c[N], d[N];

 

std::generate( std::begin( a ), std::end( a ), [] { return std::rand() % N; } );

std::generate( std::begin( b ), std::end( b ), [] { return std::rand() % N; } );

 

std::transform( std::begin( a ), std::end( a ), std::begin( b ),

                        std::make_pair_iterator( c, d ),

                        std::minmax );

[/code]

 

Array c is filled with minimum values of elements of arrays a and b while array d is filled with maximumj values of elements of arrays a and b.

 

[Vlad from Moscow]

I meant std::minmax<int>:)

пятница, 27 сентября 2013 г., 17:49:27 UTC+4 пользователь Vlad from Moscow написал:

[Zhihao Yuan]

Boost has zip_iterator

http://www.boost.org/doc/libs/1_54_0/libs/iterator/doc/zip_iterator.html

And we shortly discussed whether we should try to standardize it.
The major blocker is the current iterator category does not allow
arbitrary proxy iterator.

--
Zhihao Yuan, ID lichray
The best way to predict the future is to invent it.
___________________________________________________
4BSD -- http://4bsd.biz/

[Vlad from Moscow]

Why the pair_iterator may not have category of std::output_iterator?

 

пятница, 27 сентября 2013 г., 18:03:04 UTC+4 пользователь Zhihao Yuan написал:

[Zhihao Yuan]

On Fri, Sep 27, 2013 at 10:21 AM, Vlad from Moscow <vlad....@mail.ru> wrote:
> Why the pair_iterator may not have category of std::output_iterator?

It can be either Input or Output, but it's reasonable and helpful
to make it arbitrary.

[Vlad from Moscow]

Usually some algorithms and containers deal with pairs as shown by me in the example. So if the iterator will have std::output_iterator_tag it will be very useful.

At least I like the example of its using I showed.

пятница, 27 сентября 2013 г., 18:29:38 UTC+4 пользователь Zhihao Yuan написал:

[Vlad from Moscow]

I like the idea. I will write such a proposal. This code snip looks splendid

 

[code]

 

std::transform( std::begin( a ), std::end( a ), std::begin( b ),

                        std::make_iterator_pair( std::begin( c ), std::begin( d ) ),

                        std::minmax<int> );

 

[/code]

 

 

пятница, 27 сентября 2013 г., 17:49:27 UTC+4 пользователь Vlad from Moscow написал:

Did anybody make a proposal about something as pair_iterator.

[Nevin Liber]

On 27 September 2013 08:49, Vlad from Moscow <vlad....@mail.ru> wrote:

As an idea: the pair_iterator incorporates two iterators and its value_type is std::pair<typename Iterator1::value_type, typename Iterator2::value_type> 

-1.  Names are important, and "first" and "second" are bad names for the members.

(That's my only objection at this time.)

--
 Nevin ":-)" Liber  <mailto:ne...@eviloverlord.com>  (847) 691-1404

[Vlad from Moscow]

Do you want to say that names iterator_pair and make_iterator_pair are bad? What could you suggest?

суббота, 28 сентября 2013 г., 20:58:07 UTC+4 пользователь Nevin ":-)" Liber написал:

[Vlad from Moscow]

Or maybe I have understood you incorrectly. Inside the iterator the both iterators will be kept as std::pair<Iterator1, Iterator2> and there will be member function named something as base() that will return this pair.

суббота, 28 сентября 2013 г., 21:02:35 UTC+4 пользователь Vlad from Moscow написал:

[Vlad from Moscow]

Here is an outline of the iterator definition

 

[code]

namespace std
{

template <class Iterator1, class Iterator2>

class iterator_pair : public iterator<output_iterator_tag, void, void, void, void>
{
public:
 typedef pair<Iterator1, Iterator2> iterator_type;

 iterator_pair( Iterator1, Iterator2 );
 iterator_pair( pair<Iterator1, Iterator2> );

 iterator_type base() const;
 
 iterator_pair<Iterator1, Iterator2> &
 operator =( const pair<typename iterator_traits<Iterator1>::value_type,
                        typename iterator_traits<Iterator2>::value_type> & );

 iterator_pair<Iterator1, Iterator2> &
 operator =( pair<typename iterator_traits<Iterator1>::value_type,
                     typename iterator_traits<Iterator2>::value_type> && );

 iterator_pair<Iterator1, Iterator2> & operator *();
 iterator_pair<Iterator1, Iterator2> & operator ++();
 iterator_pair<Iterator1, Iterator2>   operator ++( int );

protected:
 iterator_type it;
};

template <class Iterator1, class Iterator2>
iterator_pair<Iterator1, Iterator2> make_iterator_pair( Iterator1, Iterator2 );

template <class Iterator1, class Iterator2>
iterator_pair<Iterator1, Iterator2> make_iterator_pair( pair<Iterator1, Iterator2> );

}

[/code]

 

пятница, 27 сентября 2013 г., 17:49:27 UTC+4 пользователь Vlad from Moscow написал:

Any feedback is appreciated. 

[Vlad from Moscow]

 

The constructor with the parameter std::pair is declared as explicir that is

 

explicit  iterator_pair( pair<Iterator1, Iterator2> );

 

Also it will be better if the parameter will passed by reference

 

explicit  iterator_pair( const pair<Iterator1, Iterator2> & );

 

суббота, 28 сентября 2013 г., 22:54:24 UTC+4 пользователь Vlad from Moscow написал:

[Vlad from Moscow]

With this iterator containers can be changed in place. That is for example  the code snippet for arrays a, b, c and d can be executed only for arrays a and b. Array a will contain minimal values of the two arrays while array b will contain maximum values of the two arrays

 

[code]

 

std::transform( std::begin( a ), std::end( a ), std::begin( b ),

                        std::make_iterator_pair( std::begin( a ), std::begin( b ) ),

                        std::minmax<int> );

 

[/code]

 

суббота, 28 сентября 2013 г., 23:47:28 UTC+4 пользователь Vlad from Moscow написал:

[Vlad from Moscow]

A revised version of the iterator definition

 

[code]

namespace usr
{

template <class Iterator1, class Iterator2>
class iterator_pair : public iterator<output_iterator_tag, void, void, void, void>
{
public:
 typedef pair<Iterator1, Iterator2> iterator_type;

 iterator_pair( Iterator1, Iterator2 );

 explicit iterator_pair( const pair<Iterator1, Iterator2> & );

 explicit iterator_pair( pair<Iterator1, Iterator2> && );

 iterator_type base() const;
 
 iterator_pair<Iterator1, Iterator2> &
 operator =( const pair<typename iterator_traits<Iterator1>::value_type,
                        typename iterator_traits<Iterator2>::value_type> & );

 iterator_pair<Iterator1, Iterator2> &
 operator =( pair<typename iterator_traits<Iterator1>::value_type,
                     typename iterator_traits<Iterator2>::value_type> && );

 iterator_pair<Iterator1, Iterator2> & operator *();
 iterator_pair<Iterator1, Iterator2> & operator ++();
 iterator_pair<Iterator1, Iterator2>   operator ++( int );

protected:
 iterator_type it;
};

template <class Iterator1, class Iterator2>
iterator_pair<Iterator1, Iterator2> make_iterator_pair( Iterator1, Iterator2 );

template <class Iterator1, class Iterator2>

iterator_pair<Iterator1, Iterator2> make_iterator_pair( const pair<Iterator1, Iterator2> & );

template <class Iterator1, class Iterator2>

iterator_pair<Iterator1, Iterator2> make_iterator_pair( pair<Iterator1, Iterator2> && );

}

[/code]

 

суббота, 28 сентября 2013 г., 22:54:24 UTC+4 пользователь Vlad from Moscow написал:

[Vlad from Moscow]

I tested my wonderfull iterator iterator_pair and it works fine. For example

 

[code]

std::map<int, std::string> m;

std::string s = "Hello new iterator \"std::iterator_pair\"!";
std::istringstream is( s );

int i = 0;

std::transform( std::istream_iterator<std::string>( is ),
  std::istream_iterator<std::string>(),
  std::inserter( m, m.begin() ),
  [&i]( const std::string &s ) { return ( std::make_pair( i++, s ) ); } );

 

std::vector<int> v1( m.size() );
std::vector<std::string> v2( m.size() );

std::copy( m.begin(), m.end(),
 usr::make_iterator_pair( v1.begin(), v2.begin() ) );

 

for ( int x : v1 ) std::cout << x << ' ';
std::cout << std::endl;

 

for ( const std::string &s : v2 ) std::cout << s << ' ';
std::cout << std::endl;

[/code]

 

 

However it seems that I found a very serious defect of the C++ Standard.

 

If to change the code above the following way

 

[code]

std::map<int, std::string> m;

std::string s = "Hello new iterator \"std::iterator_pair\"!";
std::istringstream is( s );

int i = 0;

std::transform( std::istream_iterator<std::string>( is ),
  std::istream_iterator<std::string>(),
  std::inserter( m, m.begin() ),
  [&i]( const std::string &s ) { return ( std::make_pair( i++, s ) ); } );

 

std::vector<int> v1;
std::vector<std::string> v2;

v1.reserve( m.size() );
v2.reserve( m.size() );

 

std::copy( m.begin(), m.end(),
 usr::make_iterator_pair( std::back_inserter( v1 ), std::back_inserter( v2 ) ) );

 

for ( int x : v1 ) std::cout << x << ' ';
std::cout << std::endl;

 

for ( const std::string &s : v2 ) std::cout << s << ' ';
std::cout << std::endl;
[/code]

 

It will not be compiled. The problem is that std::back_inserter is an output iterator and its value_type is defined as void. As the result I get std::pair<void, void>.

 

Let's consider the following two iterators

 

std::ostream_iterator<std::string> it1( std::cout, "\n" );
std::ostream_iterator<int> it2( std::cout, "\n" );

They are different though the both have the same template definitions. What is the difference?

 

You may write

 

it1 = "abc";
it2 = 123;

but you may not write

 

it1 = 123;
it2 = "abc";

 

What does this mean?

 

It means that these two iterators have different value types!

And as we see value type is an integral and important part of these iterators. So these iterators have defined value types.

However in the C++ Standard they are defined such a way that their value_type is defined as void.

It is a serious defect of the standard. The value_type for output iterators shall not be defined as void because each output iterator including above mentioned and also std::back_insert_iterator, std::front_insert_iterator, and std::insert_iterator have concrete value types as I showed in the example above with std::ostream_iterator.

 

So each output iterator either shall have its defined value_type or retranslate the value_type of an underlined iterator.

 

Let's consider another simple example.

 

template <OutputIterator>

void SomeFunction( OutputIterator iterator )

{

// some code

}

 

And let's assume that we are going to define a variable inside the function body that will have the type that may be processed by iterator. As the iterator has value_type void there is no possibility to determine the type of the variable.

 

template <OutputIterator>

void SomeFunction( OutputIterator iterator )

{

WhatType? our_variable;

}

 

I am sure that all output iterators must have a concrete value_type that will differ from void.

воскресенье, 29 сентября 2013 г., 0:59:11 UTC+4 пользователь Vlad from Moscow написал:

[Billy O'Neal]

[quote]

It means that these two iterators have different value types!

And as we see value type is an integral and important part of these iterators. So these iterators have defined value types.

However in the C++ Standard they are defined such a way that their value_type is defined as void.

[/quote]

Of course, there's nothing stopping an output iterator from having multiple effective value types. (I believe confusion over iterator categories is the reason zip iterator is held up if I am not mistaken... though that's completely anecdotal on my part)

Billy O'Neal

https://github.com/BillyONeal/

http://stackoverflow.com/users/82320/billy-oneal

Malware Response Instructor - BleepingComputer.com

--
 
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposal...@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

[Vlad from Moscow]

 

I am sure that the fact that outer iterators do not provide to the outer world the actual type of the value_type of objects that they can deal with and instead of this they report incorrectly type void is a serious defect of the C++ Standard.

The actual value of the value_type is integral, unique and important characteristic of any output iterator. An output iterator is not a Black Hole that can deal with any type of objects.

std::ostream_iterator has value_type that is the template parameter T. std::back_insert_iterator has value_type that is typename Container::value_type. And so on. This information shall be provided for the outer world. To provide instead of the actual value type type void is a gross error. 

 

I will prepare a defect report if there is no yet such a defect report. 

воскресенье, 29 сентября 2013 г., 8:54:03 UTC+4 пользователь Vlad from Moscow написал:

[Daniel Krügler]

2013/9/29 Vlad from Moscow <vlad....@mail.ru>:

>
> I am sure that the fact that outer iterators do not provide to the outer
> world the actual type of the value_type of objects that they can deal with
> and instead of this they report incorrectly type void is a serious defect of
> the C++ Standard.

I disagree. It was essentially much more obvious that output iterators
may not have a single value type during the time when the library was
"conceptualized":

auto concept OutputIterator<typename X, typename Value> {
requires Iterator<X>;
typename reference = Iterator<X>::reference;
typename postincrement_result = Iterator<X>::postincrement_result;
requires SameType<reference, Iterator<X>::reference>
&& SameType<postincrement_result, Iterator<X>::postincrement_result>
&& Convertible<postincrement_result, const X&>
&& HasAssign<reference, Value>
&& HasAssign<HasDereference<postincrement_result>::result_type, Value>;
}

Even without language concepts, the standard is clear in
[iterator.requirements.general] (emphasis mine):

"All output iterators support the expression *i = o where o is a value
**of some type that is in the set of types** that are writable to the
particular iterator type of i."

> The actual value of the value_type is integral, unique and important
> characteristic of any output iterator.

You are mislead here according to the standard.

> An output iterator is not a Black
> Hole that can deal with any type of objects.

Well, it *may* not, but it *can* (depending on the actual output
iterator). Of-course it doesn't hold for e.g. out put iterators that
belong to the more refined iterator concepts, such as forward
iterator.

> std::ostream_iterator has value_type that is the template parameter T.
> std::back_insert_iterator has value_type that is typename
> Container::value_type. And so on.

You cannot prove the general case by enumerating some examples that
are special models.

- Daniel

[Vlad from Moscow]

 

This statement

 

"All output iterators support the expression *i = o where o is a value
**of some type that is in the set of types** that are writable to the
particular iterator type of i."

 

does not prevent that an output iterator will have a well-formed value_type. std::ostream_iterator, std::back_insert_iterator and other insert iterators have and use implicitly defined value types. They only confuse the outer world reporting the false information that their value_type is void.

 

And I demonstrated at least in three examples that it is simply a bug of the Standard. There is no any reason that these iterators have to report void type as the value_type. This only prevents to wriye  flexible constructions.

 

If you will suggest some output iterator that will deal with several value types simultaneously then there is no problem. It is this iterator that will decide what to report as its value_type.

 

All iterators that have concrete value types shall report their value types.instead of void. void is simply a gross error for these iterators. It says that the iterator knows nothing about what types it may deals with. It is a false assumption.

 

 

воскресенье, 29 сентября 2013 г., 19:12:18 UTC+4 пользователь Daniel Krügler написал:

[Vlad from Moscow]

It is without controversy that std::ostream_iterator has value type T, where T is its template parameter. Similarly std::back_insert_iterator has value type typename Container::value_type. So there is no any reason that they have to report type void as its value type instead of the actual value type they use becasue it simply contradicts their realizations.

 

The more information an iterator can provide  the better.

 

At least you can use this information to write a conditional template code. For example if an iterator has value type void you can write one function or class specialization. If an iterator has value type that differs from void you can write another function or class specialization.

 

For example you can use this information in static_assert.

 

All what you are saying in fact is the following. It can be somewhere in the future that there will be a standard output iterator that will deal with several value types simultaneously. And by this reason you prohibit that iterators that have well-defined unique value types would report their actual value types.

 

A can not afree with such a logic. It is a destructive logic. it does not help programmers.

 

 

 

 

 

воскресенье, 29 сентября 2013 г., 19:12:18 UTC+4 пользователь Daniel Krügler написал:

2013/9/29 Vlad from Moscow <vlad....@mail.ru>:

[Vlad from Moscow]

As a note for example the proposed iterator std::iterator pair could have the following code

 

[code]

template <class Iterator1, class Iterator2>
class iterator_pair
 : public iterator<output_iterator_tag,

                   pair<typename iterator_traits<Iterator1>::value_type,

            typename iterator_traits<Iterator2>::value_type>,
       void,
       void,
       void>
{
static_assert( std::is_same<typename iterator_traits<Iterator1>::value_type, void>::value ||
               std::is_same<typename iterator_traits<Iterator2>::value_type, void>::value,
               "You may not use an iterator with value_type void" );

[/code]

 

it would work fine if such  iterators as std::ostream_iterator, std:;back_insert_iterator would report their actual value types.

 

 

 

воскресенье, 29 сентября 2013 г., 20:18:39 UTC+4 пользователь Vlad from Moscow написал:

[Mathias Gaunard]

On 27/09/13 16:03, Zhihao Yuan wrote:

> Boost has zip_iterator
>
> http://www.boost.org/doc/libs/1_54_0/libs/iterator/doc/zip_iterator.html
>
> And we shortly discussed whether we should try to standardize it.
> The major blocker is the current iterator category does not allow
> arbitrary proxy iterator.

I suppose that kind of thing is discussed as part of SG9 (Ranges)?

In Boost, the range interface and the iterator interface for this
functionality is not consistent. I'd like to see a good approach between
the iterator and range versions of all generators and adaptors.

[Vlad from Moscow]

I described the iterator adapter in my article in the issue of ACCU Overload N126 (April, 2015).

It is named "iterator_pair - A Simple and Useful Iterator Adapter".

You can read it either in the pdf format at this address or at iscpp.org

The articles also points to a serious defect of standard algorithms std::partial_sum and std::adjacent_difference and shows how to remedy it.

[Jeffrey Yasskin]

This is http://www.boost.org/doc/libs/1_58_0/libs/iterator/doc/zip_iterator.html,
right?

[Vlad from Moscow]

Jeffrey, they are different. I hope it is seen from thr article. The notion of pair is a magic notion in standard algorithms and containers. This iterator adapter is very simple and at the same time useful. It can find a usa for many tasks. And it is logically consistent with the notion of pair.