如何在std :: vector中存储没有复制或移动构造函数的对象？

Question

为了提高效率std::vector<T>,它的底层数组需要预先分配,有时需要重新分配.然而,这需要创建和稍后移动T具有复制ctor或移动ctor 的类型的对象.

我遇到的问题是T无法复制或移动,因为它包含无法复制或移动的对象(例如atomic和mutex).(是的,我正在实现一个简单的线程池.)

我想避免使用指针,因为:

1. 我不需要间接水平,所以我不想要一个.
2. (指针效率较低,增加了复杂性.使用指针会增加内存碎片并减少数据局部性,这可能(但不一定必须)导致明显的性能影响.不是那么重要,但仍值得考虑.)

有没有办法避免间接水平？

更新:根据评论和答案中的反馈,我修正了一些不正确的假设,并重新措辞了问题.

Answer 1

一开始,std::mutex无法复制或移动,因此您不得不使用某种间接方式.

由于您希望将互斥锁存储在矢量中,而不是复制它,我会使用std::unique_ptr.

vector<unique_ptr<T>> 不允许某些向量操作(例如for_each)

我不确定我理解这句话.完全有可能做范围:

std::vector< std::unique_ptr< int > > v;
// fill in the vector
for ( auto & it : v )
  std::cout << *it << std::endl;

或使用标准算法:

#include <iostream>
#include <typeinfo>
#include <vector>
#include <memory>
#include <algorithm>


int main()
{
    std::vector< std::unique_ptr< int > > v;
    v.emplace_back( new int( 3 ) );
    v.emplace_back( new int( 5 ) );
    std::for_each( v.begin(), v.end(), []( const std::unique_ptr< int > & it ){ std::cout << *it << std::endl; } );
}

Answer 2

然而,这需要使用copy ctor创建类型为T的对象.

这是不完全正确的,从C++ 11开始,如果使用其构造函数std::vector将默认构造许多元素,那么您不需要复制或移动构造函数.

因此,如果没有从池中添加或删除任何线程,则可以执行以下操作:

int num = 23;
std::vector<std::mutex> vec(num);

如果要动态添加或删除内容,则必须使用间接.

1. 使用std::vector+ std::unique_ptr已经提出
2. 使用a std::deque,允许您巧妙地使用基于范围的循环或std算法,并避免所有间接.(仅允许添加)
3. 使用std::list/forward_list此解决方案类似于第一,但它具有使用范围和算法更容易使用的额外好处.如果您只是按顺序访问元素,那么它可能是最好的,因为不支持随机访问.

像这样:

std::deque<std::mutex> deq;
deq.emplace_back();
deq.emplace_back();

for(auto& m : deq) {
    m.lock();
}

作为最后一点,std::thread当然是可以移动的,所以你可以使用std::vector+ std::vector::emplace_back.

Answer 3

总结一下到目前为止所提出的建议：

1. 使用vector<unique_ptr<T>>——添加显式的间接级别，并且是 OP 不需要的。
2. 使用deque<T>- 我第一次尝试过deque，但是从中删除对象也不起作用。请参阅关于和之间差异的讨论。dequelist

解决方案是使用forward_list单链表（或者list如果您想要双链表也可以使用）。正如@JanHudec 指出的，vector（以及它的许多朋友）在添加或删除项目时需要重新分配。mutex这与像和atomic那样不允许复制或移动的对象不太合适。forward_list并且list不需要这样做，因为每个单元格都是独立分配的（我无法引用相关标准，但索引方法产生了该假设）。由于它们实际上是链表，因此不支持随机访问索引。myList.begin() + i将为您提供第 'th 元素的迭代器i，但它（最肯定）必须i首先循环遍历所有先前的单元格。

我没有查看标准的承诺，但在 Windows (Visual Studio) 和 CompileOnline (g++) 上一切正常。请随意在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;
}

输出：

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

Removed '1'...

3
2
0

我希望这具有大致相同的性能vector<unique_ptr<T>>（只要您不经常使用随机访问索引）。

警告：Usingforward_list::remove目前在 VS 2012 中不起作用。这是因为它在尝试删除元素之前会复制该元素。头文件Microsoft Visual Studio 11.0\VC\include\forward_list（ 中的相同问题list）显示：

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

    // ...
}

因此，它被复制“以防它在途中被删除”。这意味着list甚至forward_list不允许存储unique_ptr. 我认为这是一个设计错误。

解决方法很简单：您必须使用remove_if而不是remove因为该函数的实现不会复制任何内容。

很大程度上归功于其他答案。然而，由于它们都不是没有指针的完整解决方案，所以我决定写这个答案。