I had considered once to replace a map not just with a sorted vector
but, for some efficiency reasons, with two "parallel"
vectors(vector<key_type>, vector<data_type>). It came natural to me to
make up an iterator with value_type something like pair<key_type,
data_type> and reference type pair<key_type&, data_type&>.
Unfortunately this is obviously not a valid forward iterator.
(Saying obviously I mean for those that have read the standard,
because the information that it is not valid to specify a reference
type(other than the default) for forward iterators is not widely
available in c++ (or even STL) handbooks. And if you are unlucky (or
lucky?) enough to use a compiler (like gcc) that supports proxy
iterators you end up with a solution that is not portable)

Well, I was able to compile such an iterator with the new version of
ConceptGCC (that claims to support proxy iterators) and it worked just
fine(at least with the sort algorithm). But is really going to be a
valid mutable random-access iterator according to new iterator
concepts? There are two problems i can think of.
First the requirement that a==b iff *a, *b are the same object for
forward iterators a,b.
And second, the constrain imposed by ConceptGCC that the pointer of
the iterator must be convertible to value_type*. This does not make
sense for this iterator because iter->second must be equivalent to
(*iter).second and thus the pointer must be reference*.

Thanks in advance for any comment, info.
Regards
Kostas Skolarikis

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

on Thu May 17 2007, kostas <skolarik-AT-gmail.com> wrote:

> I had considered once to replace a map not just with a sorted vector
> but, for some efficiency reasons, with two "parallel"
> vectors(vector<key_type>, vector<data_type>). It came natural to me to
> make up an iterator with value_type something like pair<key_type,
> data_type> and reference type pair<key_type&, data_type&>.

c.f. http://www.boost.org/libs/iterator/doc/zip_iterator.html

> Unfortunately this is obviously not a valid forward iterator.

Right.

> Well, I was able to compile such an iterator with the new version of
> ConceptGCC (that claims to support proxy iterators) and it worked just
> fine(at least with the sort algorithm).

I believe that's because of the following in the ForwardIterator
concept:

    // Note: The standard specifies an exact requirement, but in this
    // case there can be no refinement relationship between mutable and
    // non-mutable iterators. We want that relationship, and the
    // standard needs it, so we choose to require convertibility.
    requires Convertible<reference, const value_type&>;

> But is really going to be a
> valid mutable random-access iterator according to new iterator
> concepts?


No, but that's an old iterator concept.  It would be a valid mutable
random access _traversal_ iterator.

> There are two problems i can think of.  First the requirement that
> a==b iff *a, *b are the same object for forward iterators a,b.

Yeah, that's undetectable by the compiler ;-)

Good question though.

> And second, the constrain imposed by ConceptGCC that the pointer of
> the iterator must be convertible to value_type*. This does not make
> sense for this iterator because iter->second must be equivalent to
> (*iter).second and thus the pointer must be reference*.

I think that might be why I never wanted to require that operator->
return the pointer type.

--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com

Don't Miss BoostCon 2007! ==> http://www.boostcon.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On May 20, 7:16 pm, David Abrahams <d...@boost-consulting.com> wrote:
> on Thu May 17 2007, kostas <skolarik-AT-gmail.com> wrote:
>
> > I had considered once to replace a map not just with a sorted vector
> > but, for some efficiency reasons, with two "parallel"
> > vectors(vector<key_type>, vector<data_type>). It came natural to me to
> > make up an iterator with value_type something like pair<key_type,
> > data_type> and reference type pair<key_type&, data_type&>.
>
> c.f.http://www.boost.org/libs/iterator/doc/zip_iterator.html

zip_iterator is different from the iterator I described above. Its
reference and value_type are the same. Actually I tested it recently
and was very surprised to find that this code
--------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
#include <boost/tuple/tuple.hpp>
#include <boost/iterator/zip_iterator.hpp>

struct zip_comp
{
        bool operator()(const boost::tuple<int&, int&>& t1, const
boost::tuple<int&, int&>& t2)
        {
                return t1.get<0>()<t2.get<0>();
        }
};

int main()
{
        const int items = 10;
        std::vector<int> keys;
        std::vector<int> data;
        for(int i=0;i<items;i++) {
                keys.push_back(items-i);
                data.push_back(i);
        }
        std::sort(
                boost::make_zip_iterator(
                        boost::make_tuple(keys.begin(), data.begin())
                ),
                boost::make_zip_iterator(
                        boost::make_tuple(keys.end(), data.end())
                ),
                zip_comp()
        );

        std::copy(keys.begin(), keys.end(),
std::ostream_iterator<int>(std::cout, " "));
        std::cout<<std::endl;
        return 0;
}

--------------------------------------------------------------------------------
compiles without any problem with my gcc 4.1.2 compiler. The result
was of course disappointing.

10 10 10 10 10 10 10 10 10 10

Have I done something wrong? I was expecting at least some warning.

> > But is really going to be a
> > valid mutable random-access iterator according to new iterator
> > concepts?
>
> No, but that's an old iterator concept.  It would be a valid mutable
> random access _traversal_ iterator.

I was referring to the "new old iterator concepts" for which I have
found only this announcement
http://conceptgcc.wordpress.com/2007/05/03/the-new-old-iterator-concepts

> I think that might be why I never wanted to require that operator->
> return the pointer type.

Thanks for the hint. I didn't know that it is not required the
operator -> to return the pointer type.

Regards
Kostas

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

on Sun May 20 2007, kostas <skolarik-AT-gmail.com> wrote:

> On May 20, 7:16 pm, David Abrahams <d...@boost-consulting.com> wrote:
>> on Thu May 17 2007, kostas <skolarik-AT-gmail.com> wrote:
>>
>> > I had considered once to replace a map not just with a sorted vector
>> > but, for some efficiency reasons, with two "parallel"
>> > vectors(vector<key_type>, vector<data_type>). It came natural to me to
>> > make up an iterator with value_type something like pair<key_type,
>> > data_type> and reference type pair<key_type&, data_type&>.
>>
>> c.f.http://www.boost.org/libs/iterator/doc/zip_iterator.html
>
> zip_iterator is different from the iterator I described above. Its
> reference and value_type are the same.

Hmm, that's odd.  I didn't remember that, and I don't remember the
reason for it.

> Actually I tested it recently
> and was very surprised to find that this code
> --------------------------------------------------------------------------------
> #include <iostream>
> #include <vector>
> #include <algorithm>
> #include <boost/tuple/tuple.hpp>
> #include <boost/iterator/zip_iterator.hpp>
>
> struct zip_comp
> {
>         bool operator()(const boost::tuple<int&, int&>& t1, const
> boost::tuple<int&, int&>& t2)
>         {
>                 return t1.get<0>()<t2.get<0>();
>         }
> };
>
> int main()
> {
>         const int items = 10;
>         std::vector<int> keys;
>         std::vector<int> data;
>         for(int i=0;i<items;i++) {
>                 keys.push_back(items-i);
>                 data.push_back(i);
>         }
>         std::sort(
>                 boost::make_zip_iterator(
>                         boost::make_tuple(keys.begin(), data.begin())
>                 ),
>                 boost::make_zip_iterator(
>                         boost::make_tuple(keys.end(), data.end())
>                 ),
>                 zip_comp()
>         );
>
>         std::copy(keys.begin(), keys.end(),
> std::ostream_iterator<int>(std::cout, " "));
>         std::cout<<std::endl;
>         return 0;
> }
>
> --------------------------------------------------------------------------------
> compiles without any problem with my gcc 4.1.2 compiler. The result
> was of course disappointing.
>
> 10 10 10 10 10 10 10 10 10 10
>
> Have I done something wrong?

Doubtful.  I find value_type == reference to be suspicious.

> I was expecting at least some warning.
>
>> > But is really going to be a
>> > valid mutable random-access iterator according to new iterator
>> > concepts?
>>
>> No, but that's an old iterator concept.  It would be a valid mutable
>> random access _traversal_ iterator.
>
> I was referring to the "new old iterator concepts" for which I have
> found only this announcement
> http://conceptgcc.wordpress.com/2007/05/03/the-new-old-iterator-concepts

Oh, interesting.  Well, somehow I was out of the loop on that development.

>> I think that might be why I never wanted to require that operator->
>> return the pointer type.
>
> Thanks for the hint. I didn't know that it is not required the
> operator -> to return the pointer type.

It may depend where you look.  The last documents I had influence over
did not make that requirement.

--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On May 21, 2:39 am, David Abrahams <d...@boost-consulting.com> wrote:
> >> I think that might be why I never wanted to require that operator->
> >> return the pointer type.
>
> > Thanks for the hint. I didn't know that it is not required the
> > operator -> to return the pointer type.
>
> It may depend where you look.  The last documents I had influence over
> did not make that requirement.

The Convertible requirement for the pointer type is incorrect. It was
an approximation that worked well before we fixed forward iterators to
not require true references. We'll need to bring back some kind of
"Arrowable" concept (which is a tricky, recursive concept) to model
operator->.

Of course, I'd really rather just axe the requirement for "operator-
>". It's never actually needed in generic algorithms, and it causes oh-
so-much pain.

  - Doug

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]