How to store objects without copy or move constructor in std::vector?

c++, c++11, constructor, move-semantics, vector

Solution

To summarize what was proposed so far:

- Use `vector<unique_ptr<T>>` -- Adds an explicit level of indirection and was unwanted by OP.

- Use `deque<T>` -- I first tried `deque`, but erasing objects from it also does not work. See this discussion on differences between `deque` and `list`.

The solution is to use `forward_list` which is a singly-linked list (or you can use `list` if you want a doubly-linked list). As @JanHudec pointed out, `vector` (and many of it's friends) require re-allocation when adding or removing items. That does not sit well with objects like `mutex` and `atomic` which are not allowed to be copied nor moved. `forward_list` and `list` do not require that because each cell is allocated independently (I cannot cite the standard on that, but the indexing method gives rise to that assumption). Since they are actually linked lists, they do not support random access indexing. `myList.begin() + i` will get you an iterator of the `i`'th element, but it (most certainly) will have to loop through all previous `i` cells first.

I have not looked at the promises by the standard, but things work fine on Windows (Visual Studio) and CompileOnline (g++). Feel free to play around with the following test case on CompileOnline:

#include <forward_list>
#include <iostream>
#include <mutex>
#include <algorithm>

using namespace std;

class X
{
    /// Private copy constructor.
    X(const X&);
    /// Private assignment operator.
    X& operator=(const X&);

public:
    /// Some integer value
    int val;
    /// An object that can be neither copied nor moved
    mutex m;

    X(int val) : val(val) { }
};


int main()
{
    // create list
    forward_list<X> xList;

    // add some items to list
    for (int i = 0; i < 4; ++i)
       xList.emplace_front(i);

    // print items
    for (auto& x : xList)
       cout << x.val << endl;

    // remove element with val == 1    
    // WARNING: Must not use remove here (see explanation below)
    xList.remove_if([](const X& x) { return x.val == 1; });


    cout << endl << "Removed '1'..." << endl << endl;

    for (auto& x : xList)
       cout << x.val << endl;

   return 0;
}

Output:

Executing the program....
$demo 
3
2
1
0

Removed '1'...

3
2
0

I expect this to roughly have the same performance as `vector<unique_ptr<T>>` (as long as you don't use random access indexing too often).

WARNING: Using `forward_list::remove` does not currently work in VS 2012. That is because it copies the element before trying to remove it. The header file `Microsoft Visual Studio 11.0\VC\include\forward_list` (same problem in `list`) reveals:

void remove(const _Ty& _Val_arg)
{   // erase each element matching _Val
    const _Ty _Val = _Val_arg;  // in case it's removed along the way

    // ...
}

So, it is copied "in case it's removed along the way". This means that `list` and `forward_list` don't even allow for storing `unique_ptr`. I assume that this is a design bug.

The work-around is simple: You have to use `remove_if` instead of `remove` because the implementation of that function does not copy anything.

A lot of the credit goes to the other answers. However, since none of them was a complete solution without pointers, I decided to write this answer.

Problem

To improve efficiency of `std::vector<T>`, it's underlying array needs to be pre-allocated and sometimes re-allocated. That, however, requires the creation and later moving of objects of type `T` with a copy ctor or move ctor. The problem that I am having is that `T` cannot be copied or moved because it contains objects that cannot be copied or moved (such as `atomic` and `mutex`). (And, yes, I am implementing a simple thread pool.) I would like to avoid using pointers because: - I do not need a level of indirection and so I do not want one. - (Pointers are less efficient and increase complexity. Using pointers increases memory fragmentation and decreases data locality which can (but not necessarily must) cause a noticeable performance impact. Not so important, but still worth consideration.) Is there a way to avoid a level of indirection here? UPDATE: I fixed some incorrect assumptions and re-phrased the question, based on feedback in comments and answers.

Original source

Related problems