在STL實現中是否有中心分配雙向或向量？

Question

我正在讀約deque s和vector s，而在其wikipedia entry，它說的使用動態陣列deque三種可能的實現方式之一是傳來：

分配從底層陣列的中心雙端隊列內容，和 當達到任一端時調整底層數組的大小。這種方法可能需要更頻繁的重做並浪費更多的空間，特別是當元素僅在一端插入時。

我想知道是否有任何實際使用這種中心分配策略的STL（或STL樣式）實現？

我在問，因爲這個策略看起來相當有吸引力，因爲它只涉及一個底層陣列，因此消除了內存分散性問題，這可能是deque與vector相比唯一的主要問題。如果我的理解正確的話，這很可能是std::vector的替代品，它允許O（1）pop_front（攤銷）或替換deque以保證內存連續性。我認爲這是以減少std::vector的緩衝空間爲代價的，這對我的用例來說不是主要關心的問題。

另外，在這樣的容器中插入/刪除的時間是否平均需要花費一半的時間std::vector？

---

UPDATE：

由於@Lightness種族在軌道中指出，這樣的實施將不會在目前的標準中，因爲沒有人可以從每份合約的上漲空間與STL中受益，每個人都會從遭受缺點。我有一個關於該缺點的另一個問題是：

是否有可能實現新vector或deque類似容器（比如bivector），使得除了std::vector功能/運營商，

1 ）提供（攤銷）恆定時間push_front()和pop_front()操作和

2）保證內存連續性，但不增長大小後的迭代器有效性？

我想在場景後面有一個陣列，deque上的很多間接/性能問題就會消失。

Answer 1

沒有標準庫（不是「STL」）實現會打擾這一點，因爲它有你提到的缺點，並且上升不是std::deque要求的一部分。

這些需求是仔細構建的，從各種操作的算法複雜性到迭代器失效規則。在實施容器方面沒有任何好處，因爲沒有人可以依靠這個實施的優勢。

C++委員會能否在未來的標準中引入一個新的容器，使用不同的名稱和不同的約束條件，供應商可以如你所描述的那樣實施？是的，他們可以。

Answer 2

你的問題是你缺乏那個容器。開始是這樣的：

template<typename T> 
class bi_vec { 
    std::unique_ptr<char[]> raw; 
    std::size_t first = 0; 
    std::size_t last = 0; 
    std::size_t capacity = 0; 
    char* raw_get(std::size_t index) { 
    return &raw[index*sizeof(T)]; 
    } 
    char const* raw_get(std::size_t index) const { 
    return &raw[index*sizeof(T)]; 
    } 
    T& get(std::size_t index) { 
    return *reinterpret_cast<T*>(raw_get(index)); 
    } 
    T const& get(std::size_t index) const { 
    return *reinterpret_cast<T const *>(raw_get(index)); 
    } 
    char* raw_before() { 
    if (first < 1) 
     grow(); 
    --first; 
    return raw_get(first); 
    } 
    char* raw_after() { 
    if (last+1 >= capacity) 
     grow(); 
    ++last; 
    return raw_get(last-1); 
    } 
    void grow() { 
    std::vector new_capacity = (capacity+1)*2; 
    std::size_t new_first = (new_capacity - (last-first))/2; 
    std::size_t new_last = new_capacity - new_first; 
    std::unique_ptr<char[]> new_buff(new char[new_capacity*sizeof(T)]); 
    T* b = &get(0); 
    T* e = &get(last-first); 
    std::move(b, e, reinterpret_cast<T*>(&new_buff[new_first*sizeof(T)])); 
    std::swap(buff, raw); 
    std::swap(new_capacity, capacity); 
    std::swap(new_first, first); 
    std::swap(new_last, last); 
    for (T* it = b; it != e; ++it) { 
     it->~T(); 
    } 
    } 
public: 
    T& operator[](std::size_t index) { return get(index); } 
    T const& operator[](std::size_t index) const { return get(index); } 
    template<class... Us> 
    void emplace_back(Us&&...us) { 
    char* a = raw_after(); 
    new (a) T(std::forward<Us>(us)); 
    } 
    template<class... Us> 
    void emplace_front(Us&&...us) { 
    char* a = raw_before(); 
    new (a) T(std::forward<Us>(us)); 
    } 
    ~bi_vec() { 
    for(std::size_t i = 0; i != last-first; ++i) { 
     get(i).~T(); 
    } 
    } 
}; 

，並添加迭代器（我會嘗試使用boost迭代器助手，或裸指針開始），無論您需要的接口。請注意，以上需求確保它仍然是異常安全的。