Concatenating C++ iterator ranges into a const vector member variable at construction time

Question

I have a class X, which I provide a snippet of here:

class X {
  public:
    template <typename Iter>
    X(Iter begin, Iter end) : mVec(begin, end) {}

  private:
    vector<Y> const mVec;
};

I now want to add a new concatenating constructor to this class, something like:

template <typename Iter1, typename Iter2>
X(Iter1 begin1, Iter1 end1, Iter2 begin2, Iter2 end2) : mVec(???) { ??? }

Such a constructor would catenate the two ranges [begin1, end1) and [begin2, end2) into mVec. The challenges are

1) I would like to preserve the const on mVec, so that it is considered constant throughout the other methods of X.

2) I would like to avoid unnecessary copies if at all possible. That is, one solution is to have a static method that constructs a non-const temporary to range 1, inserts range 2 and returns it, and then define the concatenating constructor to

template <typename Iter1, typename Iter2>
X(Iter1 begin1, Iter1 end1, Iter2 begin2, Iter2 end2) 
  : mVec(concatenate(begin1, end1, begin2, end2)) { }

but that copies all the values at least one extra time, I believe.

Answer 1

Nice problem. I would try to implement a particular iterator wrapper type that turns the two ranges into a single range. Something in the lines of:

// compacted syntax for brevity...
template <typename T1, typename T2>
struct concat_iterator
{
public:
   typedef std::forward_iterator_tag iterator_category;
   typedef typename iterator_traits<T1>::value_type value_type;
   typedef *value_type pointer; 
   typedef &value_type reference;

   concat_iterator( T1 b1, T1 e1, T2 b2, T2 e2 ) 
      : seq1( b1 ), seq1end( e1 ), seq2( b2 ), seq2end( e2 );
   iterator& operator++() {
      if ( seq1 != seq1end ) ++seq1;
      else ++seq2;
      return this;
   }
   reference operator*() {
      if ( seq1 != seq1end ) return *seq1;
      else return *seq2;
   }
   pointer operator->() {
      if ( seq1 != seq1end ) return &(*seq1);
      else return &(*seq2);
   }
   bool operator==( concat_iterator const & rhs ) {
      return seq1==rhs.seq1 && seq1end==rhs.seq2 
          && seq2==rhs.seq2 && seq2end==rhs.seq2end;
   }
   bool operator!=( contact_iterator const & rhs ) {
      return !(*this == rhs);
   }
private:
   T1 seq1;
   T1 seq1end;
   T2 seq2;
   T2 seq2end;
};

template <typename T1, typename T2>
concat_iterator<T1,T2> concat_begin( T1 b1, T1 e1, T2 b2, T2 e2 )
{
   return concat_iterator<T1,T2>(b1,e1,b2,e2);
}
template <typename T1, typename T2>
concat_iterator<T1,T2> concat_end( T1 b1, T1 e1, T2 b2, T2 e2 )
{
   return concat_iterator<T1,T2>(e1,e1,e2,e2);
}

Now you could use:

 class X {
 public:
    template <typename Iter, typename Iter2>
    X(Iter b1, Iter e1, Iter2 b2, Iter2 e2 ) 
      : mVec( concat_begin(b1,e1,b2,e2), concat_end(b1,e1,b2,e2) ) 
    {}

  private:
    vector<Y> const mVec;
};

or (I have just thought of it) you don't need to redeclare your constructor. Make your caller use the helper functions:

X x( concat_begin(b1,e1,b2,e2), concat_end(b1,e1,b2,e2) );

I have not checked the code, just typed it here off the top of my head. It could compile or it could not, it could work or not... but you can take this as a start point.

Answer 2

It would probably be best to drop const (why would you insist on it anyway?).

Otherwise, you have to build a concatenating iterator. It is quite a lot of code, see this thread for more.

Answer 3

One of the best or worst features of C++, depending on your viewpoint, is that you can abuse it when necessary to get the job done. In this case, const_cast is the victim:

template <typename Iter1, typename Iter2>
X(Iter1 begin1, Iter1 end1, Iter2 begin2, Iter2 end2) : mVec(begin1, end1) {
    const_cast<vector<Y>&>(mVec).insert(mVec.end(), begin2, end2);
}

I might have some of the details wrong, I didn't try to compile this. But it should give you the idea.

Answer 4

Your static method might not be as bad as you think, depending on the optimization your compiler does. And in C++0x, move constructors will remove any copying that is currently taking place.

In the meantime go with a wrapper iterator. The code is not likely to be as bad as the thread avakar links to, since you only need to implement an input iterator.

Answer 5

1) I would like to preserve the const on mVec, so that it is considered constant throughout the other methods of X.

• This is a curious use of const on a member variable. And it defies good design. By definition, construction is a process which requires the object to change.

• As for your requirement to keep the object non-modifiable -- use proper encapsulation. You should use const-member functions to expose any functionality based on your mVec for the clients of your class.

2) I would like to avoid unnecessary copies if at all possible. That is, one solution is to have a static method that constructs a non-const temporary to range 1, inserts range 2 and returns it, and then define the concatenating constructor to

You should be looking at move-constructors and r-value references in general (a promised goal of C++0x). Read this article.