unexpected unique_copy constness issue

I was trying to come up with a neat STL-heavy response to this thread
about multimaps:

http://groups.google.com/group/comp....e6796296b79797

My implementation involved using unique_copy to uniquify the set of
keys. However, the compiler (gcc 4.0.2) complains because it's trying
to (internally) use

std::pair<const int, int> & std::pair<const int,
int>::operator=(std::pair<const int,int> const&)

which it has synthesized. The code is as follows:

#include <map>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> value;

bool cmp(value const& lhs, value const& rhs)
{
return lhs.first == rhs.first;
}

int main()
{
typedef map<int, int> m_t;
m_t m;

vector<value> v;

copy(m.begin(),
m.end(),
back_inserter<vector<value> >(v));

unique_copy(m.begin(),
m.end(),
back_inserter<vector<value> >(v),
cmp);

return EXIT_SUCCESS;
}

Note that the call to copy() proceeds without problem. I can
understand why the map holds std::pair<const int, int> rather than
std::pair<int, int>, but I don't see why it would need to assign to a
value of that type to do unique_copy. Especially because copy() works
just fine... anyone got an idea here?

Luke

Luke Meyers wrote:[color=blue]
> I was trying to come up with a neat STL-heavy response to this thread
> about multimaps:
>
> http://groups.google.com/group/comp....e6796296b79797
>
> My implementation involved using unique_copy to uniquify the set of
> keys. However, the compiler (gcc 4.0.2) complains because it's trying
> to (internally) use
>
> std::pair<const int, int> & std::pair<const int,
> int>::operator=(std::pair<const int,int> const&)
>
> which it has synthesized. The code is as follows:
>
> #include <map>
> #include <algorithm>
> #include <vector>
>
> using namespace std;
>
> typedef pair<int, int> value;
>
> bool cmp(value const& lhs, value const& rhs)
> {
> return lhs.first == rhs.first;
> }
>
> int main()
> {
> typedef map<int, int> m_t;
> m_t m;
>
> vector<value> v;
>
> copy(m.begin(),
> m.end(),
> back_inserter<vector<value> >(v));
>
> unique_copy(m.begin(),
> m.end(),
> back_inserter<vector<value> >(v),
> cmp);
>
> return EXIT_SUCCESS;
> }
>
> Note that the call to copy() proceeds without problem. I can
> understand why the map holds std::pair<const int, int> rather than
> std::pair<int, int>, but I don't see why it would need to assign to a
> value of that type to do unique_copy. Especially because copy() works
> just fine... anyone got an idea here?[/color]

A look at the unique_copy implementation gives the clue. I am using g++
3.4.2 and here is how it looks

template<typename _InputIterator, typename _OutputIterator,
typename _BinaryPredicate>
_OutputIterator
__unique_copy(_InputIterator __first, _InputIterator __last,
_OutputIterator __result,
_BinaryPredicate __binary_pred,
output_iterator_tag)
{
// concept requirements -- iterators already checked

__glibcxx_function_requires(_BinaryPredicateConcep t<_BinaryPredicate,
typename iterator_traits<_InputIterator>::value_type,
typename iterator_traits<_InputIterator>::value_type>)

typename iterator_traits<_InputIterator>::value_type __value =
*__first;
*__result = __value;
while (++__first != __last)
if (!__binary_pred(__value, *__first))
{
__value = *__first;
*++__result = __value;
}
return ++__result;
}

The offending line is

__value = *__first;

in the inner loop which tries to assign to a variable of type
InputIterator::value_type. That fails as its a std::pair<const int,
int> whose *first* is *const int*.

Ram

Ram wrote:[color=blue]
> typename iterator_traits<_InputIterator>::value_type __value =
> *__first;
> *__result = __value;
> while (++__first != __last)
> if (!__binary_pred(__value, *__first))
> {
> __value = *__first;
> *++__result = __value;
> }
>
> The offending line is
>
> __value = *__first;
>
> in the inner loop which tries to assign to a variable of type
> InputIterator::value_type. That fails as its a std::pair<const int,
> int> whose *first* is *const int*.[/color]

Is this correct, though? It strikes me as an irritating and
unnecessary restriction, and while I'm loath to suggest that the gcc
STL implementation is wrong, I find nothing more plausible. I believe
it's correct for map to store pair<const int, int>. It seems like
unique_copy should be able to operate within the constraint of a
non-assignable value type, so long as that type is copy-constructible.
It may not be as efficient, but that could perhaps be addressed by
template specialization. Am I missing something here?

Luke

Luke Meyers wrote:
[color=blue]
> I was trying to come up with a neat STL-heavy response to this thread
> about multimaps:
>
>[/color]
http://groups.google.com/group/comp....e6796296b79797[color=blue]
>
> My implementation involved using unique_copy to uniquify the set of
> keys. However, the compiler (gcc 4.0.2) complains because it's trying
> to (internally) use
>
> std::pair<const int, int> & std::pair<const int,
> int>::operator=(std::pair<const int,int> const&)
>
> which it has synthesized. The code is as follows:
>
> #include <map>
> #include <algorithm>
> #include <vector>
>
> using namespace std;
>
> typedef pair<int, int> value;
>
> bool cmp(value const& lhs, value const& rhs)
> {
> return lhs.first == rhs.first;
> }
>
> int main()
> {
> typedef map<int, int> m_t;
> m_t m;
>
> vector<value> v;
>
> copy(m.begin(),
> m.end(),
> back_inserter<vector<value> >(v));
>
> unique_copy(m.begin(),
> m.end(),
> back_inserter<vector<value> >(v),
> cmp);
>
> return EXIT_SUCCESS;
> }
>
> Note that the call to copy() proceeds without problem. I can
> understand why the map holds std::pair<const int, int> rather than
> std::pair<int, int>, but I don't see why it would need to assign to a
> value of that type to do unique_copy. Especially because copy() works
> just fine... anyone got an idea here?[/color]

I had a look at the g++ implementation of unique_copy. Apparently, it uses a
variable of type iterator_traits<InIter>::value_type to keep track of runs
of equal elements. This is reasonable since input iterators have very weak
guarantees. This variable is updated using assignment. That is where the
error message comes from.

Here is a draft for a less restrictive unique_copy. It only uses
initialization of the variable:

template < typename InIter, typename OutIter, typename BinPred >
OutIter unique_copy ( InIter from, InIter to, OutIter where, BinPred eq ) {
typedef typename std::iterator_traits<InIter>::value_type value_type;
while ( from != to ) {
value_type last_value = *from++;
*where++ = last_value;
//skip loop:
while ( ( from != to ) && eq( last_value, *from ) ) {
++from;
}
}
return ( where );
}

Warning, this is totally untested code.

Also, I am not sure whether the g++ STL is in error: unique_copy is listed
under the modifying sequence operations, but the effects section for that
algorithm does not list any modification of the input sequence. I think
that [25/5] should then imply that the value_type is not supposed to be
modifyable.


Best

Kai-Uwe Bux

> > typename iterator_traits<_InputIterator>::value_type __value =[color=blue][color=green]
> > *__first;
> > *__result = __value;
> > while (++__first != __last)
> > if (!__binary_pred(__value, *__first))
> > {
> > __value = *__first;
> > *++__result = __value;
> > }
> >
> > The offending line is
> >
> > __value = *__first;
> >
> > in the inner loop which tries to assign to a variable of type
> > InputIterator::value_type. That fails as its a std::pair<const int,
> > int> whose *first* is *const int*.[/color]
>
> Is this correct, though? It strikes me as an irritating and
> unnecessary restriction, and while I'm loath to suggest that the gcc
> STL implementation is wrong, I find nothing more plausible. I believe
> it's correct for map to store pair<const int, int>. It seems like
> unique_copy should be able to operate within the constraint of a
> non-assignable value type, so long as that type is copy-constructible.
> It may not be as efficient, but that could perhaps be addressed by
> template specialization. Am I missing something here?[/color]

I too wouldn't like to suggest that the implementation is wrong. But
its possible for the implementation to be less restrictive (to be able
to work with non-assignable value type). Instead of saving the values
one could save the iterator position for doing comparisons. Here's the
modified code (original commented out)-

// typename iterator_traits<_InputIterator>::value_type __value =
*__first;
_InputIterator __previous = __first;
// *__result = __value;
*__result = *__previous;
while (++__first != __last) {
// if (!__binary_pred(__value, *__first))
if (!__binary_pred(*__previous, *__first))
{
// __value = *__first;
__previous = __first;
// *++__result = __value;
*++__result = *__previous;
}
}

That puts the requirement of _InputIterator to be assignable though.
Not sure whether this might be a restriction. Also Kai-Uwe Bux
suggested an alternate implementation. Time to raise a bug-report with
g++ maintainers? :-)

Ram

ramashishb@gmail.com wrote:
[color=blue][color=green][color=darkred]
>> > typename iterator_traits<_InputIterator>::value_type __value =
>> > *__first;
>> > *__result = __value;
>> > while (++__first != __last)
>> > if (!__binary_pred(__value, *__first))
>> > {
>> > __value = *__first;
>> > *++__result = __value;
>> > }
>> >
>> > The offending line is
>> >
>> > __value = *__first;
>> >
>> > in the inner loop which tries to assign to a variable of type
>> > InputIterator::value_type. That fails as its a std::pair<const int,
>> > int> whose *first* is *const int*.[/color]
>>
>> Is this correct, though? It strikes me as an irritating and
>> unnecessary restriction, and while I'm loath to suggest that the gcc
>> STL implementation is wrong, I find nothing more plausible. I believe
>> it's correct for map to store pair<const int, int>. It seems like
>> unique_copy should be able to operate within the constraint of a
>> non-assignable value type, so long as that type is copy-constructible.
>> It may not be as efficient, but that could perhaps be addressed by
>> template specialization. Am I missing something here?[/color]
>
> I too wouldn't like to suggest that the implementation is wrong. But
> its possible for the implementation to be less restrictive (to be able
> to work with non-assignable value type). Instead of saving the values
> one could save the iterator position for doing comparisons. Here's the
> modified code (original commented out)-
>[/color]
[color=blue]
> _InputIterator __previous = __first;
> *__result = *__previous;
> while (++__first != __last) {
> if (!__binary_pred(*__previous, *__first))[/color]

This will *not* work: __previous is invalidated by incrementing __first. The
postconditions for ++r on input iterator are stated as follows [24, Table
72]:

++r X&
pre: r is dereferenceable.
post: r is dereferenceable or r is past-the-end.
post: any copies of the previous value of r are no longer
required either to be dereferenceable or to be in the domain of ==

[color=blue]
> {
> __previous = __first;
> *++__result = *__previous;
> }
> }
>
> That puts the requirement of _InputIterator to be assignable though.
> Not sure whether this might be a restriction.[/color]

No, input iterators are assignable. However, you cannot use stored values of
an iterator that has been incremented for dereferencing.


Best

Kai-Uwe Bux

[...][color=blue][color=green]
> > _InputIterator __previous = __first;
> > *__result = *__previous;
> > while (++__first != __last) {
> > if (!__binary_pred(*__previous, *__first))[/color]
>
> This will *not* work: __previous is invalidated by incrementing __first. The
> postconditions for ++r on input iterator are stated as follows [24, Table
> 72]:
>
> ++r X&
> pre: r is dereferenceable.
> post: r is dereferenceable or r is past-the-end.
> post: any copies of the previous value of r are no longer
> required either to be dereferenceable or to be in the domain of ==
>
>[color=green]
> > {
> > __previous = __first;
> > *++__result = *__previous;
> > }
> > }
> >
> > That puts the requirement of _InputIterator to be assignable though.
> > Not sure whether this might be a restriction.[/color]
>
> No, input iterators are assignable. However, you cannot use stored values of
> an iterator that has been incremented for dereferencing.
>[/color]

Oh yes. It won't work with iterators which wrap an input stream for
example..

In article <1148631610.356551.294040@j33g2000cwa.googlegroups .com>,
"Luke Meyers" <n.luke.meyers@gmail.com> wrote:
[color=blue]
> Is this correct, though? It strikes me as an irritating and
> unnecessary restriction, and while I'm loath to suggest that the gcc
> STL implementation is wrong, I find nothing more plausible. I believe
> it's correct for map to store pair<const int, int>. It seems like
> unique_copy should be able to operate within the constraint of a
> non-assignable value type, so long as that type is copy-constructible.
> It may not be as efficient, but that could perhaps be addressed by
> template specialization. Am I missing something here?[/color]

The standard is in error. I've attempted to correct it (twice now):

http://www.open-std.org/jtc1/sc22/wg...ctive.html#538

The corrected standard will have the effect of making gcc incorrect, and
your example code conforming. However gcc has already been corrected
(not sure which release) so that it will be conforming by the time this
defect report becomes normative.

-Howard

Howard Hinnant wrote:[color=blue]
> In article <1148631610.356551.294040@j33g2000cwa.googlegroups .com>,
> "Luke Meyers" <n.luke.meyers@gmail.com> wrote:[color=green]
> > Am I missing something here?[/color]
> The standard is in error.[/color]

Ah, sweet vindication!
[color=blue]
> I've attempted to correct it (twice now):
>
> http://www.open-std.org/jtc1/sc22/wg...ctive.html#538[/color]

Thank you very much for providing this response, and for Fighting the
Good Fight.
[color=blue]
> The corrected standard will have the effect of making gcc incorrect, and
> your example code conforming. However gcc has already been corrected
> (not sure which release) so that it will be conforming by the time this
> defect report becomes normative.[/color]

Fantastic. I'll see if a gcc update does the trick.

Cheers,
Luke