Is there a C ++ container with reasonable random access that never calls an instance constructor of an element type?

Question

I need a container that implements the following API (and should 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&); } 

Does the dose of such a beast exist?

vector<T> does not do this (resizes), and I'm not sure how fast deque<T> .

---

I do not need to highlight

Several people have suggested that the reason I cannot make copies is because of memory allocation problems. The reason for the restrictions is that the type of the element explicitly prohibits copying , and I cannot change it.

---

Looks like I have my answer: STL doesn't have one. But now I wonder why not?

Answer 1

I am sure that the answer here is a rather decisive "No". By your definition, resize() should allocate a new repository and initialize the default constructor if I read it correctly. You will then manipulate objects by indexing into the collection and manipulating the link instead of “pasting” into the collection. Otherwise, you need a copy operator and an assignment operator. All containers in the standard library have this requirement.

You might want to learn something like boost::ptr_vector<T> . Since you are inserting pointers, you do not need to worry about copying. This will require you to dynamically select all of your objects.

Answer 2

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

If the vector must contain elements, then std::vector< std::shared_ptr<T> > might be more appropriate.

And there is also a Boost Pointer Container Library that provides containers for safely handling pointers.

Answer 3

Use deque : performance is great.

The standard says: " deque is data sampling when most attachments and exceptions occur at the beginning or end of a sequence" (23.1.1). In your case, all insertions and deletions are done at the end, satisfying the criteria for using deque .

http://www.gotw.ca/gotw/054.htm contains some tips on how you can measure performance, although presumably you have a specific use case, so what you should measure.

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

The next best thing is probably to create arrays of elements built by default and create a container of pointers to these elements. Something like that, although it can probably be significantly changed.

 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 additional functions and operators are added, it will approach deque , but avoiding anything that requires a copy of type T.

Edit: think about it, my “reader exercise” cannot be done quite right in cases where someone does resize(10); resize(20); resize(15); resize(10); resize(20); resize(15); . You cannot delete half of the array. Therefore, if you want to correctly reproduce the semantics of the resize() container, immediately destroying the excess elements, you will have to select the elements separately (or familiarize yourself with the placement of a new one):

 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(); } }; 

Cleaner code not really keen on memory access patterns (but then I don't understand if performance is a problem or not since you were worried about deque speed.)

Answer 4

As you have discovered, all standard containers are not compatible with your requirements. If we can make a few additional assumptions, it would not be easy to write our own container.

• The container will always grow - resize will always be called with a larger number than before, but no less.
• OK for resize to make the container larger than required; creating a number of unused objects at the end of the container is acceptable.

Here begins. I leave you a lot of details.

 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 } 

PS If someone asks you why you want to do this, tell them you need the std::auto_ptr array. That should be good for a laugh.

Answer 5

All standard containers require items to copy. At least because push_back and insert a copy of the element passed to them. I don’t think you can get away with std :: deque because even its resizing method requires the parameter to be copied to fill the elements.

To use a completely non-copyable class in standard containers, you will need to store pointers to these objects. Sometimes this can be a burden, but using shared_ptr or various boost pointer containers can make it easier.

If you don't like any of these solutions, try looking at the rest of boost. Maybe there is something else suitable there. Perhaps intrusive containers ?

Otherwise, if you do not think that this suits your needs, you can always try to roll your own container, which will do what you want. (Or even more searching to see if anyone else has done such a thing.)

Answer 6

You should not choose a container based on how it handles memory. For example, deque is a double-end queue, so you should only use it when you need a double-end queue.

Almost every container will allocate memory if you change its size! Of course, you can change the power up by typing vector::reserve . Capacity is the number of physical elements in memory whose size depends on how much you are actively using.

Obviously, there will still be excretion if you outgrow your potential.

Answer 7

See ::boost::array . It does not allow you to resize the container after it is created, but it does not copy anything.

Getting both resize and no copying will become a trick. I would not trust ::std::deque , because maybe it can copy in some cases. If you really need to resize, I would encode my own container, similar to deque. Since the only way you are going to resize and not copy is to use a page system like ::std::deque .

In addition, having a page system necessarily means that at will not be as fast as for ::std::vector and ::boost::array with their adjacent memory layout, although it can still be pretty fast.