Подтвердить что ты не робот

Как хранить объекты без копирования или перемещения конструктора в std::vector?

Чтобы повысить эффективность std::vector<T>, базовый массив должен быть предварительно выделен и иногда перераспределен. Это, однако, требует создания и последующего перемещения объектов типа T с копией ctor или перемещением ctor.

Проблема, с которой я столкнулась, заключается в том, что T нельзя скопировать или переместить, потому что он содержит объекты, которые нельзя скопировать или переместить (например, atomic и mutex). (И, да, я реализую простой пул потоков.)

Я хотел бы избежать использования указателей, потому что:

  • Мне не нужен уровень косвенности, поэтому я не хочу этого.
  • (Указатели менее эффективны и увеличивают сложность. Использование указателей увеличивает фрагментацию памяти и снижает локальность данных, которые могут (но не обязательно должны) вызывать заметное влияние производительности. Не так важно, но все же стоит рассмотреть.)

Есть ли способ избежать уровня косвенности здесь?

ОБНОВЛЕНИЕ: я исправил некоторые неправильные предположения и переформулировал вопрос, основываясь на отзывах в комментариях и ответах.

4b9b3361

ОТВЕТЫ

Ответ 1

Подводя итог тому, что было предложено до сих пор:

  • Использовать vector<unique_ptr<T>> - Добавляет явный уровень косвенности и нежелателен OP.
  • Использовать deque<T> - я сначала попробовал deque, но удаление объектов из него также не работает. См. эту дискуссию о различиях между deque и list.

Решение заключается в использовании forward_list, который является односвязным списком (или вы можете использовать list, если вы хотите дважды связанный список). Как отметил @JanHudec, vector (и многие из его друзей) требуют перераспределения при добавлении или удалении элементов. Это не очень хорошо подходит для объектов, таких как mutex и atomic, которые не могут быть скопированы или перемещены. forward_list и list не требуют этого, потому что каждая ячейка распределяется независимо (я не могу ссылаться на этот стандарт, но метод индексирования дает это предположение). Поскольку они фактически связаны списками, они не поддерживают индексацию произвольного доступа. myList.begin() + i предоставит вам итератор элемента i 'th, но ему (конечно же) придется сначала прокрутить все предыдущие ячейки i.

Я не рассматривал стандарт promises по стандарту, но все отлично работает в 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>> (пока вы не используете слишком частое индексирование с произвольным доступом).

ПРЕДУПРЕЖДЕНИЕ. Использование forward_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 removed along the way

    // ...
}

Таким образом, он копируется "в случае его удаления по пути". Это означает, что list и forward_list даже не позволяют хранить unique_ptr. Я предполагаю, что это ошибка дизайна.

Обход прост: вы должны использовать remove_if вместо remove, потому что реализация этой функции ничего не копирует.

Многие из них относятся к другим ответам. Однако, поскольку ни одно из них не было полным решением без указателей, я решил написать этот ответ.

Ответ 2

Для начала 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;

или использовать std-алгоритмы:

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

Ответ 3

Это требует, однако, создания объектов типа T с копией ctor.

Это не совсем так, как с С++ 11, если вы используете конструктор std::vector, который по умолчанию будет создавать несколько элементов, тогда вам не нужно иметь конструктор копирования или перемещения.

Таким образом, если ни один поток не добавляется или не удаляется из вашего пула, вы можете просто сделать:

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

Если вы хотите динамически добавлять или удалять вещи, вам нужно использовать косвенную привязку.

  • Используйте std::vector + std::unique_ptr как уже было предложено
  • Используйте std::deque, который позволяет вам аккуратно использовать его с диапазоном, основанным на циклах или std-алгоритмами, и избегает всех указаний. (Который позволяет только добавления)
  • Используйте 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.

Ответ 4

Вы можете хранить элементы без перемещения или копирования конструкторов в std::vector, но вам просто нужно избегать методов, которые требуют, чтобы элементы имели перемещение или копирование конструкторов. Почти 1 все, что изменяет размер вектора (например, push_back, resize() и т.д.).

На практике это означает, что вам нужно выделить вектор фиксированного размера во время построения, который будет вызывать конструктор по умолчанию ваших объектов, который вы можете изменить с назначением. Это может, по крайней мере, работать для объектов std::atomic<>, которые могут быть назначены.

1clear() - единственный пример метода изменения размера, который не требует конструкторов копирования/перемещения, поскольку ему никогда не нужно перемещать или копировать какие-либо элементы (в конце концов, вектор после этой операции пуст). Конечно, вы никогда не сможете снова увеличить свой вектор нулевого размера после вызова этого!