Вектор C++ с фиксированной емкостью после инициализации

Мне нужен контейнер C++ со следующими требованиями:

  • Контейнер может хранить некопируемые И неподвижные объекты в непрерывной памяти. Для std::vector объект должен быть либо копируемым, либо перемещаемым.
  • capacity контейнера известен во время построения во время выполнения и фиксируется до уничтожения. При построении выделяется весь необходимый объем памяти. Для boost::static_vector емкость известна во время компиляции.
  • Размер контейнера может увеличиваться со временем, когда в контейнере становится emplace_back элемента, но никогда не должен превышать capacity.
  • Поскольку объект нельзя копировать или перемещать, перераспределение не допускается.

Похоже, что ни в STL, ни в BOOST нет нужного мне типа контейнера. Я также много искал в этой стороне, но не нашел ответа. Итак, я реализовал один.

#include <memory>

template<class T>
class FixedCapacityVector {
private:
    using StorageType = std::aligned_storage_t<sizeof(T), alignof(T)>;
    static_assert(sizeof(StorageType) == sizeof(T));
public:
    FixedCapacityVector(FixedCapacityVector const&) = delete;
    FixedCapacityVector& operator=(FixedCapacityVector const&) = delete;
    FixedCapacityVector(size_t capacity = 0):
        capacity_{ capacity },
        data_{ std::make_unique<StorageType[]>(capacity) }
    { }
    ~FixedCapacityVector()
    {
        for (size_t i = 0; i < size_; i++)
            reinterpret_cast<T&>(data_[i]).~T();
    }
    template<class... Args>
    T& emplace_back(Args&&... args) 
    {
        if (size_ == capacity_)
            throw std::bad_alloc{};
        new (&data_[size_]) T{ std::forward<Args>(args)... };
        return reinterpret_cast<T&>(data_[size_++]);
    }
    T& operator[](size_t i) 
    { return reinterpret_cast<T&>(data_[i]); }
    T const& operator[](size_t i) const 
    { return reinterpret_cast<T const&>(data_[i]); }
    size_t size() const { return size_; }
    size_t capacity() const { return capacity_; }
    T* data() { return reinterpret_cast<T*>(data_.get()); }
    T const* data() const { return reinterpret_cast<T const*>(data_.get()); }
private:
    size_t const capacity_;
    std::unique_ptr<StorageType[]> const data_;
    size_t size_{ 0 };
};

Мои вопросы:

  • Зачем мне делать это вручную? Я не смог найти стандартный контейнер. А может я не там смотрел? Или потому, что то, что я пытаюсь сделать, не является обычным?
  • Правильно ли реализован рукописный контейнер? Как насчет безопасности исключений, безопасности памяти и т. д.?

person Tony Xiang    schedule 26.12.2018    source источник
comment
Для такого часто необходимого типа контейнера... неверно. Может ли ваш некопируемый и неперемещаемый объект храниться в std::shared_ptr, а затем std::shared_ptr храниться в std::vector?   -  person Eljay    schedule 26.12.2018
comment
@Eljay Спасибо за комментарий. Тогда объекты не находятся в непрерывной памяти. На самом деле это то, что программа сейчас делает (используя std::vector<std::unique_ptr>). Может быть, я не должен говорить такой часто используемый тип контейнера.   -  person Tony Xiang    schedule 26.12.2018
comment
Должны ли некопируемые и неперемещаемые объекты находиться в непрерывной памяти?   -  person Eljay    schedule 26.12.2018
comment
Почему бы просто не обернуть std::vector, размер которого изменен до максимально необходимого, и не отслеживать, сколько элементов фактически используется? Если этот вектор является закрытым членом вашего класса, вы можете гарантировать, что его размер никогда не изменится после инициализации, что бы ни делал пользователь вашего класса. В конце концов, даже если пользователь просит ваш класс что-то emplace_back(), вашему классу (или реализации его функций-членов) не нужно превращать это в вызовы emplace_back() вектора.   -  person Peter    schedule 26.12.2018
comment
@Peter На самом деле это первое, о чем я подумал. Но std::vector<T> не будет компилироваться, если T нельзя ни копировать, ни перемещать.   -  person Tony Xiang    schedule 26.12.2018
comment
@TonyXiang - при использовании C ++ до C ++ 11 это верно (элемент должен быть копируемым и копируемым). p — это указатель на неразрушенный T). Однако вам нужно быть осторожным при выборе операций над вектором, так как некоторые функции-члены std::vector имеют более строгие требования (например, [из памяти] вектор emplace() требует, чтобы элементы были Move Assignable, Move Insertable и Emplace Constructible — в отличие от копирования присваиваемый и копируемый).   -  person Peter    schedule 26.12.2018
comment
@Peter, я только что попытался создать экземпляр std::vector<T> для некопируемого-неподвижного T. Как вы сказали, сам экземпляр может быть скомпилирован. Однако ни один из методов не может быть использован для добавления элемента в вектор. Я подумал, что можно использовать emplace_back, поскольку он не требует копирования или перемещения, если не требуется перераспределение. Но компилятор все еще жалуется на удаленный конструктор копирования. У вас есть идеи, как добавить элемент в вектор в этом случае?   -  person Tony Xiang    schedule 26.12.2018
comment
Очевидно, что если размер контейнера может быть изменен после создания, то любая функция, добавляющая элемент, может потребовать копирования или перемещения существующих элементов.   -  person Phil1970    schedule 12.11.2019
comment
Хотя ваш код кажется правильным, я думаю, что должно быть возможно (и безопаснее) написать его без такого большого количества приведений.   -  person Phil1970    schedule 12.11.2019


Ответы (3)


Вероятно, это не дает полного ответа на вопрос, но похоже, что fixed_capacity_vector может быть добавлен в будущие стандарты C++ в соответствии со следующей статьей:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0843r1.html

Введение

В этой статье предлагается модернизированная версия boost::container::static_vector [1]. То есть динамически изменяемый вектор с фиксированной емкостью во время компиляции и непрерывным встроенным хранилищем, в котором элементы хранятся в самом векторном объекте.

Его API очень похож на std::vector. Это непрерывный контейнер с O(1) вставкой и удалением элементов в конце (без амортизации) и в худшем случае O(size()) вставкой и удалением в противном случае. Как и std::vector, элементы инициализируются при вставке и уничтожаются при удалении. Для тривиальных value_types вектор можно полностью использовать внутри функций constexpr.

person dshvets1    schedule 12.11.2019
comment
Из отзыва: Привет, хотя ссылки и являются отличным способом обмена знаниями, они на самом деле не ответят на вопрос, если они сломаются в будущем. Добавьте к своему ответу основное содержание ссылки, которая отвечает на вопрос. Если содержание слишком сложное или слишком большое, чтобы поместиться здесь, опишите общую идею предлагаемого решения. Не забывайте всегда сохранять ссылку на веб-сайт исходного решения. См.: Как написать хороший ответ? - person sɐunıɔןɐqɐp; 12.11.2019

Зачем мне делать это вручную? Я не смог найти стандартный контейнер. А может я не там смотрел? Или потому, что то, что я пытаюсь сделать, не является обычным?

Это необычно. По соглашению, то, что является MoveConstructible, также является MoveAssignable.

Правильно ли реализован рукописный контейнер? Как насчет безопасности исключений, безопасности памяти и т. д.?

data проблематично. Вызывающие, вероятно, предполагают, что они могут увеличить этот указатель, чтобы получить доступ к другим элементам, но это строго неопределенно. На самом деле у вас нет массива T. Стандарт требует определяемой реализацией магии в std::vector.

person Caleth    schedule 12.11.2019

Я знаю, что это немного старый пост и не предлагает точных требований, но мы открыли реализацию FixedCapacityVector, используемую в производственном коде моей компании на протяжении многих лет, доступную здесь. Емкость должна быть константой времени компиляции.

Для этого требуется компилятор C++11, но API соответствует std::vector C++17.

person Stéphane Janel    schedule 29.05.2021