Is there a C++ container with reasonable random access that never calls the element type's copy constructor?

Question

I need a container that implements the following API (and need not implement anything else):

class C<T> {
  C();

  T& operator[](int); // must have reasonably sane time constant

    // expand the container by default constructing elements in place.
  void resize(int); // only way anything is added.
  void clear();

  C<T>::iterator begin();
  C<T>::iterator end();
}

and can be used on:

class I {
 public:
  I();
 private:  // copy and assignment explicate disallowed
  I(I&);
  I& operator=(I&);
}

Dose such a beast exist?

vector<T> doesn't do it (resize moves) and I'm not sure how fast deque<T> is.

---

I don't care about allocation

Several people have assumed that the reason I can't do copies is memory allocation issues. The reason the constraints is that the element type explicitly disallows copying and I can't change that.

---

Looks like I've got my answer: SLTL doesn't have one. But now I'm wondering Why not?

Answer 1

Use deque: performance is fine.

The standard says, "deque is the data structure of choice when most insertions and deletions take place at the beginning or at the end of the sequence" (23.1.1). In your case, all insertions and deletions take place at the end, satisfying the criterion for using deque.

http://www.gotw.ca/gotw/054.htm has some hints on how you might measure performance, although presumably you have a particular use-case in mind, so that's what you should be measuring.

Edit: OK, if your objection to deque is in fact not, "I'm not sure how fast deque is", but "the element type cannot be an element in a standard container", then we can rule out any standard container. No, such a beast does not exist. deque "never copies elements", but it does copy-construct them from other objects.

Next best thing is probably to create arrays of elements, default-constructed, and maintain a container of pointers to those elements. Something along these lines, although this can probably be tweaked considerably.

template <typename T>
struct C {
    vector<shared_array<T> > blocks;
    vector<T*> elements; // lazy, to avoid needing deque-style iterators through the blocks.
    T &operator[](size_t idx) { return *elements[idx]; }
    void resize(size_t n) {
        if (n <= elements.size()) { /* exercise for the reader */ }
        else {
            boost::shared_array<T> newblock(new T[elements.size() - n]);
            blocks.push_back(newblock);
            size_t old = elements.size();
            // currently we "leak" newblock on an exception: see below
            elements.resize(n);
            for (int i = old; j < n; ++i) {
                elements[i] = &newblock[i - old];
            }
    }
    void clear() {
        blocks.clear();
        elements.clear();
    }
};

As you add more functions and operators, it will approach deque, but avoiding anything that requires copying of the type T.

Edit: come to think of it, my "exercise for the reader" can't be done quite correctly in cases where someone does resize(10); resize(20); resize(15);. You can't half-delete an array. So if you want to correctly reproduce container resize() semantics, destructing the excess elements immediately, then you will have to allocate the elements individually (or get acquainted with placement new):

template <typename T>
struct C {
    deque<shared_ptr<T> > elements; // or boost::ptr_deque, or a vector.
    T &operator[](size_t idx) { return *elements[idx]; }
    void resize(size_t n) {
        size_t oldsize = elements.size();
        elements.resize(n);
        if (n > oldsize) {
            try {
                for (size_t i = oldsize; i < n; ++i) {
                    elements[i] = shared_ptr<T>(new T());
                }
            } catch(...) {
                // closest we can get to strong exception guarantee, since
                // by definition we can't do anything copy-and-swap-like
                elements.resize(oldsize);
                throw;
            }
        }
    }
    void clear() {
        elements.clear();
    }
};

Nicer code, not so keen on the memory access patterns (but then, I'm not clear whether performance is a concern or not since you were worried about the speed of deque.)

Answer 2

You shouldn't pick a container based on how it handles memory. deque for example is a double-ended queue, so you should only use it when you need a double-ended queue.

Pretty much every container will allocate memory if you resize it! Of course, you could change the capacity up front by calling vector::reserve. The capacity is the number of physical elements in memory, the size is how many you are actively using.

Obviously, there will still be an allocation if you grow past your capacity.

Answer 3

You could use a container of pointers, like std::vector<T*>, if the elements cannot be copied and their memory is managed manually elsewhere.

If the vector should own the elements, something like std::vector< std::shared_ptr<T> > could be more appropriate.

And there is also the Boost Pointer Container library, which provides containers for exception safe handling of pointers.

Answer 4

All the standard containers require copyable elements. At the very least because push_back and insert copy the element passed to them. I don't think you can get away with std::deque because even its resize method takes parameter to be copied for filling the elements.

To use a completely non-copyable class in the standard containers, you would have to store pointers to those objects. That can sometimes be a burden but usage of shared_ptr or the various boost pointer containers can make it easier.

If you don't like any of those solutions then take a browse through the rest of boost. Maybe there's something else suitable in there. Perhaps intrusive containers?

Otherwise, if you don't think any of that suits your needs then you could always try to roll your own container that does what you want. (Or else do more searching to see if anyone else has ever made such a thing.)

Answer 5

I'm pretty sure that the answer here is a rather emphatic "No". By your definition, resize() should allocate new storage and initialize with the default constructor if I am reading this correctly. Then you would manipulate the objects by indexing into the collection and manipulating the reference instead of "inserting" into the collection. Otherwise, you need the copy constructor and assignment operator. All of the containers in the Standard Library have this requirement.

You might want to look into using something like boost::ptr_vector<T>. Since you are inserting pointers, you don't have to worry about copying. This would require that you dynamically allocate all of your objects though.

Answer 6

As you've discovered, all of the standard containers are incompatible with your requirements. If we can make a couple of additional assumptions, it wouldn't be too hard to write your own container.

• The container will always grow - resize will always be called with a greater number than previously, never lesser.
• It is OK for resize to make the container larger than what was asked for; constructing some number of unused objects at the end of the container is acceptable.

Here's a start. I leave many of the details to you.

class C<T> { 
  C();
  ~C() { clear(); }

  T& operator[](int i) // must have reasonably sane time constant 
  {
      return blocks[i / block_size][i % block_size];
  }

    // expand the container by default constructing elements in place. 
  void resize(int n) // only way anything is added. 
  {
      for (int i = (current_size/block_size)+1; i <= n/block_size;  ++i)
      {
          blocks.push_back(new T[block_size]);
      }
      current_size = n;
  }

  void clear()
  {
      for (vector<T*>::iterator i = blocks.begin();  i != blocks.end();  ++i)
          delete[] *i;
      current_size = 0;
  }

  C<T>::iterator begin(); 
  C<T>::iterator end(); 
private:
  vector<T*> blocks;
  int current_size;
  const int block_size = 1024; // choose a size appropriate to T
} 

P.S. If anybody asks you why you want to do this, tell them you need an array of std::auto_ptr. That should be good for a laugh.

Answer 7

Look at ::boost::array. It doesn't allow the container to be resized after creating it, but it doesn't copy anything ever.

Getting both resize and no copying is going to be a trick. I wouldn't trust a ::std::deque because I think maybe it can copy in some cases. If you really need resizing, I would code your own deque-like container. Because the only way you're going to get resizing and no copying is to have a page system like ::std::deque uses.

Also, having a page system necessarily means that at isn't going to be quite as fast as it would be for ::std::vector and ::boost::array with their contiguous memory layout, even though it can still be fairly fast.