Re: unexpected unique_copy constness issue

From:

Kai-Uwe Bux <jkherciueh@gmx.net>

Newsgroups:

comp.lang.c++

Date:

Fri, 26 May 2006 04:30:37 -0400

Message-ID:

<127df5dsd4vo8e9@corp.supernews.com>

Luke Meyers wrote:

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

http://groups.google.com/group/comp.lang.c++/browse_frm/thread/5a3732e0cbaab918/35e6796296b79797?q=multimap&rnum=3#35e6796296b79797

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?

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