GotW #16

Home Blog Talks Books & Articles Training & Consulting

On the
blog
RSS feed November 4: Other Concurrency Sessions at PDC
November 3
: PDC'09: Tutorial & Panel
October 26: Hoare on Testing
October 23
: Deprecating export Considered for ISO C++0x

This is the original GotW problem and solution substantially as posted to Usenet. See the book Exceptional C++ (Addison-Wesley, 2000) for the most current solutions to GotW issues #1-30. The solutions in the book have been revised and expanded since their initial appearance in GotW. The book versions also incorporate corrections, new material, and conformance to the final ANSI/ISO C++ standard.

Maximally Reusable Generic Containers
Difficulty: 8 / 10

How flexible can you make this simple container class? Hint: You'll learn more than a little about member templates along the way.

Problem

Implement copy construction and copy assignment for the following fixed-length vector class to provide maximum usability. Hint: Think about the kinds of things that client code might want to do.

  template<typename T, size_t size>
  class fixed_vector {
  public:
    typedef T*       iterator;
    typedef const T* const_iterator;

    iterator       begin()       { return v_; }
    iterator       end()         { return v_+size; }
    const_iterator begin() const { return v_; }
    const_iterator end()   const { return v_+size; }

  private:
    T v_[size];
  };

Notes

- Don't fix other things. This container is not intended to be fully STL-compliant, and has at least one subtle problem. It's only meant to illustrate some important issues in a simplified setting.

- This example is adapted from one presented by Kevlin Henney and later analyzed by Jon Jagger in Issues 12 and 20 of the British C++ user magazine Overload. (British readers beware: The answer to this GotW goes well beyond that presented in Overload #20. In fact, the efficiency optimization presented there won't work in the solution that I'm going to post.)

Solution

[Note: This original solution contains some bugs since fixed in Exceptional C++ and the Errata list.]

Implement copy construction and copy assignment for the following fixed-length vector class to provide maximum usability. Hint: Think about the kinds of things that client code might want to do.

For this GotW solution, we'll do something a little different: I'll present the solution code, and your mission is to supply the explanation.

Q: What is the following solution doing, and why? Explain each constructor and operator.

  template<typename T, size_t size>
  class fixed_vector {
  public:
    typedef T*       iterator;
    typedef const T* const_iterator;

    fixed_vector() { }

    template<typename O, size_t osize>
    fixed_vector( const fixed_vector<O,osize>& other ) {
      copy( other.begin(),
            other.begin()+min(size,osize),
            begin() );
    }

    template<typename O, size_t osize>
    fixed_vector<T,size>&
    operator=( const fixed_vector<O,osize>& other ) {
      copy( other.begin(),
            other.begin()+min(size,osize),
            begin() );
      return *this;
    }

    iterator       begin()       { return v_; }
    iterator       end()         { return v_+size; }
    const_iterator begin() const { return v_; }
    const_iterator end()   const { return v_+size; }

  private:
    T v_[size];
  };

Let's analyze this and see how well it measures up to what the question asked.

Copy Construction and Copy Assignment

First, note that the question as stated is a bit of a red herring: the original code already had a copy constructor and a copy assignment operator that worked fine. Our solution proposes to add a templated constructor and a templated assignment operator to make construction and assignment more flexible.

Congratulations to Valentin Bonnard and others who were quick to point out that the proposed copy constructor is not a copy constructor at all! In fact, we can go further: the proposed copy assignment operator is not a copy assignment operator at all, either.

Here's why: A copy constructor or copy assignment operator specifically constructs/assigns from another object of exactly the same type... including the same template arguments, if the class is templated. For example:

    struct X {
      template<typename T>
      X( const T& );    // NOT copy ctor, T can't be X

      template<typename T>
      operator=( const T& );
                        // NOT copy ass't, T can't be X
    };

"But," you say, "those two templated member functions could exactly match the signatures of copy construction and copy assignment!" Well, actually, no... they couldn't, because in both cases T may not be X. To quote from CD2 [note: also appears in the later official standard of 1998; "CD2" was "Comittee Draft 2" as of 1995]:

[12.8/2 note 4]

Because a template constructor is never a copy constructor, the presence of such a template does not suppress the implicit declaration of a copy constructor.

There's similar wording in [12.8/9 note 7] for copy assignment. So the proposed solution in fact still has the same copy constructor and copy assignment operator as the original code did, because the compiler still generates the implicit versions. What we've done is extended the construction and assignment flexibility, not replaced the old versions. For example, consider the following program:

    fixed_vector<char,4> v;
    fixed_vector<int,4>  w;

    fixed_vector<int,4>  w2(w);
            // calls implicit copy ctor
    fixed_vector<int,4>  w3(v);
            // calls templated conversion ctor

    w = w2; // calls implicit assignment operator
    w = v;  // calls templated assignment operator

So what the question was really looking for was for us to provide flexible "construction and assignment from other fixed_vectors," not specifically flexible "copy construction and copy assignment" which already existed.

Usability Issues for Construction and Assignment

There are two major usability considerations:

1. Support varying types (including inheritance).

While fixed_vector definitely is and should remain a homogeneous container, sometimes it makes sense to construct or assign from another fixed_vector which actually contains different objects. As long as the source objects are assignable to our type of object, this should be allowed. For example, clients may want to write something like this:

    fixed_vector<char,4> v;
    fixed_vector<int,4>  w(v);  // copy
    w = v;                      // assignment

    class B { /*...*/ };
    class D : public B { /*...*/ };

    fixed_vector<D,4> x;
    fixed_vector<B,4> y(x);     // copy
    y = x;                      // assignment

2. Support varying sizes.

Similarly, clients may want to construct or assign from fixed_vectors with different sizes. Again, it makes sense to support this feature. For example:

    fixed_vector<char,6> v;
    fixed_vector<int,4>  w(v);  // copy 4 objects
    w = v;                      // assign 4 objects

    class B { /*...*/ };
    class D : public B { /*...*/ };

    fixed_vector<D,16> x;
    fixed_vector<B,42> y(x);    // copy 16 objects
    y = x;                      // assign 16 objects

Alternative: The Standard Library Approach

I happen to like the syntax and usability of the above functions, but there are still some nifty things they won't let you do. Consider another approach that follows the style of the standard library:

1. Copying.

    template<Iter>
    fixed_vector( Iter first, Iter last ) {
      copy( first,
            first+min(size,last-first),
            begin() );
    }

Now when copying, instead of writing:

    fixed_vector<char,6> v;
    fixed_vector<int,4>  w(v);  // copy 4 objects

we need to write:

    fixed_vector<char,6> v;
    fixed_vector<int,4>  w(v.begin(), v.end());
                                // copy 4 objects

For construction, which style is better: the style of our proposed solution, or this standard library-like style? Here the former is somewhat easier to use and the latter is much more flexible (e.g., it allows users to choose subranges and copy from other kinds of containers), so you can take your pick or simply supply both flavours.

2. Assignment.

Note that we can't templatize assignment to take an iterator range, since operator=() may take only one parameter. Instead, we can provide a named function:

    template<Iter>
    fixed_vector<T,size>&
    assign( Iter first, Iter last ) {
      copy( first,
            first+min(size,last-first),
            begin() );
      return *this;
    }

Now when assigning, instead of writing:

    w = v;                      // assign 4 objects

we need to write:

    w.assign(v.begin(), v.end());
                                // assign 4 objects

Technically, assign() isn't even necessary since we could still get the same flexibility without it, but that would be uglier and less efficient:

    w = fixed_vector<int,4>(v.begin(), v.end());
                                // assign 4 objects

For assignment, which style is better: the style of our proposed solution, or this standard library-like style? This time the flexibility argument doesn't hold water because the user can just as easily (and even more flexibly) write the copy himself. Instead of writing:

    w.assign(v.begin(), v.end());

the user just writes:

    copy( v.begin(), v.end(), w.begin() );

There's little reason to write assign() in this case, so for assignment it's probably best to use the technique from the proposed solution and let clients use copy() directly whenever subrange assignment is desired.

Why Write the Default Constructor?

Finally, why does the proposed solution also write an empty default constructor, which merely does the same thing as the compiler-generated default constructor? This is necessary because as soon as you define a constructor of any kind the compiler will not generate the default one for you, and clearly client code like the above requires it.

Summary: What About Member Function Templates?

Hopefully this GotW has convinced you that member function templates are definitely handy. I hope that it's also helped to show why they're widely used in the standard library. If you're not familiar with them already, don't despair... not all compilers support member templates today, but it's in the standard and so soon all compilers will. (As of this writing, Microsoft Visual C++ 5.0 can compile the solution, but it can't deduce the osize parameters in some of the example client code.)

Use member templates to good effect when creating your own classes and you'll likely not just have happy users, but have more of them, as they flock to reusing the code that's best-designed for reuse.

Copyright 2009 Herb Sutter