เวกเตอร์ 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 ที่เป็นจริง (องค์ประกอบจะต้องคัดลอกมอบหมายได้และสร้างสำเนาได้) สำหรับ C++11 และใหม่กว่า องค์ประกอบนั้นจำเป็นต้องลบได้เท่านั้น (ซึ่งโดยพื้นฐานแล้วหมายถึง p->~T() ถูกต้องหาก 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