Vektor C++ dengan kapasitas tetap setelah inisialisasi

Saya memerlukan wadah C++ dengan persyaratan berikut:

  • Wadah dapat menyimpan objek yang tidak dapat disalin DAN tidak dapat dipindahkan dalam memori berkelanjutan. Untuk std::vector objek harus dapat disalin atau dipindahkan.
  • capacity kontainer diketahui selama konstruksi pada saat run-time, dan diperbaiki hingga kehancuran. Semua ruang memori yang dibutuhkan dialokasikan selama konstruksi. Untuk boost::static_vector kapasitasnya diketahui pada waktu kompilasi.
  • Ukuran penampung dapat bertambah seiring waktu ketika emplace_back lebih banyak elemen dalam penampung, tetapi tidak boleh melebihi capacity.
  • Karena objek tidak dapat disalin atau dipindahkan, realokasi tidak diperbolehkan.

Tampaknya baik STL maupun BOOST tidak memiliki tipe container yang saya perlukan. Saya juga telah mencari di sisi ini secara ekstensif tetapi tidak menemukan jawaban. Jadi saya telah menerapkannya.

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

Pertanyaan saya adalah:

  • Mengapa saya melakukan ini dengan tangan? Saya tidak dapat menemukan wadah standar. Atau mungkin saya tidak melihat tempat yang tepat? Atau karena apa yang saya coba lakukan tidak konvensional?
  • Apakah wadah tulisan tangan diterapkan dengan benar? Bagaimana dengan keamanan pengecualian, keamanan memori, dll.?

person Tony Xiang    schedule 26.12.2018    source sumber
comment
Untuk jenis kontainer yang biasa dibutuhkan... salah. Bisakah objek Anda yang tidak dapat disalin dan tidak dapat dipindahkan disimpan di std::shared_ptr, dan kemudian std::shared_ptr disimpan di std::vector?   -  person Eljay    schedule 26.12.2018
comment
@Eljay Terima kasih atas komentarnya. Objek-objek tersebut kemudian tidak berada dalam memori berkelanjutan. Sebenarnya itulah yang dilakukan program sekarang (menggunakan std::vector<std::unique_ptr>). Mungkin sebaiknya saya tidak menyebutkan jenis container yang umum dibutuhkan seperti itu.   -  person Tony Xiang    schedule 26.12.2018
comment
Apakah objek yang tidak dapat disalin dan tidak dapat dipindahkan perlu disimpan dalam memori berkelanjutan?   -  person Eljay    schedule 26.12.2018
comment
Mengapa tidak membungkus std::vector saja yang diubah ukurannya sesuai kebutuhan maksimum, dan melacak berapa banyak elemen yang sebenarnya digunakan? Jika vektor tersebut adalah anggota privat kelas Anda, Anda dapat memastikan vektor tersebut tidak pernah diubah ukurannya setelah inisialisasi, apa pun yang dilakukan pengguna kelas Anda. Lagi pula, bahkan jika pengguna meminta kelas Anda untuk emplace_back() sesuatu, kelas Anda (atau implementasi fungsi anggotanya) tidak perlu mengubahnya menjadi panggilan emplace_back() vektor.   -  person Peter    schedule 26.12.2018
comment
@Peter Sebenarnya itulah hal pertama yang saya pikirkan. Tetapi std::vector<T> tidak akan dikompilasi jika T tidak dapat disalin dan dipindahkan.   -  person Tony Xiang    schedule 26.12.2018
comment
@TonyXiang - jika menggunakan C++ sebelum C++11 itu benar (elemen harus dapat dialihkan dan dapat disalin). Untuk C++11 dan yang lebih baru, elemen hanya harus Dapat Dihapus (yang pada dasarnya berarti p->~T() valid jika p adalah penunjuk ke T yang tidak dirusak. Namun, Anda harus berhati-hati dalam memilih operasi pada vektor, karena beberapa fungsi anggota std::vector memiliki persyaratan yang lebih ketat (misalnya, emplace() vektor [dari memori] mengharuskan elemennya adalah Move Assignable, Move Insertable, dan Emplace Constructible - sebagai pembeda dari salinan dapat dialihkan dan dapat disalin).   -  person Peter    schedule 26.12.2018
comment
@Peter Saya baru saja mencoba membuat instance std::vector<T> untuk T yang tidak dapat disalin-tidak dapat dipindahkan. Seperti yang Anda katakan, instantiasi itu sendiri dapat dikompilasi. Namun, metode ini tidak dapat digunakan untuk menambahkan elemen ke vektor. Saya pikir emplace_back dapat digunakan karena tidak memerlukan tindakan salin atau pindahkan jika tidak diperlukan realokasi. Namun kompiler masih mengeluhkan konstruktor salinan yang dihapus. Apakah Anda tahu cara menambahkan elemen ke vektor dalam kasus ini?   -  person Tony Xiang    schedule 26.12.2018
comment
Jelasnya, jika sebuah container dapat diubah ukurannya setelah konstruksi, maka fungsi apa pun yang menambahkan item mungkin perlu menyalin atau memindahkan item yang sudah ada   -  person Phil1970    schedule 12.11.2019
comment
Meskipun kode Anda tampaknya benar, menurut saya seharusnya mungkin (dan lebih aman) untuk menulisnya tanpa banyak pemeran.   -  person Phil1970    schedule 12.11.2019


Jawaban (3)


Ini mungkin tidak menjawab pertanyaan sepenuhnya tetapi sepertinya fixed_capacity_vector dapat ditambahkan ke standar C++ di masa depan menurut makalah berikut:

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

Perkenalan

Makalah ini mengusulkan versi modern dari boost::container::static_vector [1]. Artinya, vektor yang dapat diubah ukurannya secara dinamis dengan kapasitas tetap pada waktu kompilasi dan penyimpanan tertanam yang berdekatan di mana elemen disimpan di dalam objek vektor itu sendiri.

API-nya sangat mirip dengan std::vector. Ini adalah wadah yang berdekatan dengan penyisipan dan penghapusan elemen O(1) di bagian akhir (tidak diamortisasi) dan kasus terburuk penyisipan dan penghapusan O(ukuran()) sebaliknya. Seperti std::vector, elemen diinisialisasi saat penyisipan dan dimusnahkan saat penghapusan. Untuk value_types yang sepele, vektor dapat digunakan sepenuhnya di dalam fungsi constexpr.

person dshvets1    schedule 12.11.2019
comment
Dari Ulasan: Hai, meskipun tautan adalah cara yang bagus untuk berbagi pengetahuan, tautan tersebut tidak akan menjawab pertanyaan jika rusak di kemudian hari. Tambahkan ke jawaban Anda konten penting dari tautan yang menjawab pertanyaan tersebut. Jika kontennya terlalu rumit atau terlalu besar untuk dimuat di sini, jelaskan gagasan umum dari solusi yang diusulkan. Ingatlah untuk selalu menyimpan referensi tautan ke situs web solusi asli. Lihat: Bagaimana cara menulis jawaban yang baik? - person sɐunıɔןɐqɐp; 12.11.2019

Mengapa saya melakukan ini dengan tangan? Saya tidak dapat menemukan wadah standar. Atau mungkin saya tidak melihat tempat yang tepat? Atau karena apa yang saya coba lakukan tidak konvensional?

Ini tidak konvensional. Berdasarkan konvensi, sesuatu yang MoveConstructible juga MoveAssignable

Apakah wadah tulisan tangan diterapkan dengan benar? Bagaimana dengan keamanan pengecualian, keamanan memori, dll.?

data bermasalah. Penelepon cenderung berasumsi bahwa mereka dapat menaikkan penunjuk tersebut untuk mendapatkan elemen lain, tetapi hal itu tidak ditentukan secara ketat. Anda sebenarnya tidak memiliki array T. Standar ini memerlukan keajaiban yang ditentukan implementasi di std::vector.

person Caleth    schedule 12.11.2019

Saya tahu ini postingan yang agak lama dan tidak mengusulkan persyaratan yang tepat, tetapi kami menjadikan implementasi FixedCapacityVector sebagai sumber terbuka yang digunakan dalam kode produksi perusahaan saya sejak bertahun-tahun, tersedia di sini. Kapasitas harus berupa konstanta waktu kompilasi.

Ini memerlukan kompiler C++11 tetapi API sesuai dengan std::vector C++17.

person Stéphane Janel    schedule 29.05.2021