ci sono deque o vettori di allocazione centrale nelle implementazioni STL?

Question

stavo leggendo deque s vs vector s, e mi sono imbattuto la sua wikipedia entry, che dice uno dei tre possibili implementazioni di deque usando gli array dinamici è:

Assegnazione contenuti deque dal centro della matrice sottostante, e ridimensionamento dell'array sottostante quando viene raggiunta una delle estremità. Questo approccio può richiedere ridimensionamenti più frequenti e sprecare più spazio, in particolare quando gli elementi vengono inseriti solo ad una estremità.

Mi chiedevo se esistono implementazioni STL (o STL) che utilizzano effettivamente questa strategia di allocazione centrale?

Sto chiedendo perché questa strategia sembra piuttosto allettante in quanto coinvolge solo un array sottostante, e quindi rimuove il problema di contiguità di memoria, che è probabilmente l'unico problema principale deque rispetto a vector. Se ho capito bene, questo potrebbe benissimo essere un sostituto per std::vector che consente O (1) pop_front (ammortizzato) o una sostituzione per deque con garanzie di contiguità di memoria. Suppongo che questo sia al costo di raddoppiare lo spazio di buffering di uno std::vector, che non è una preoccupazione importante per i miei casi d'uso.

Inoltre, è vero che l'inserimento/la cancellazione nel mezzo di un contenitore di questo tipo richiederebbe la metà del tempo di std::vector in media?

---

UPDATE:

Come @Lightness gare in orbita rilevare, tale implementazione non sarà utilizzato in base agli standard attuali, perché nessuno può beneficiare dei pregi per contratto con STL e tutti soffriranno dalla aspetti negativi. Un'ulteriore domanda che ho per quanto riguarda i lati negativi è questo:

E 'possibile implementare un nuovavector o deque come contenitore (ad esempio bivector) in modo che, oltre alle funzionalità/operatori di std::vector,

1) fornisce (ammortizzato) il tempo costante push_front() e le operazioni pop_front() e

2) garantisce contiguità di memoria ma non validità di iteratore dopo dimensioni crescenti?

Immagino che con uno schieramento dietro la scena, molti dei problemi di indiretta/prestazioni su deque andrebbero via.

Answer 1

Nessuna implementazione della libreria standard (non "STL") si preoccupa di questo, perché ha gli svantaggi che si menzionano, e gli svantaggi non fanno parte del requisito per std::deque.

Tali requisiti sono accuratamente costruiti, direttamente dalla complessità algoritmica per varie operazioni, fino alle regole di invalidazione dell'iteratore. Non vi è alcun vantaggio nell'implementazione di un contenitore in modo tale che nessuno possa fare affidamento sui lati positivi di tale implementazione.

Il comitato C++ potrebbe introdurre un nuovo contenitore in uno standard futuro con un nome diverso e con diversi vincoli, che i produttori potrebbero implementare come descritto? Sì, potrebbero.

Answer 2

Il tuo problema è che ti manca quel container. Iniziare con qualcosa di simile:

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

e aggiungere iteratori (sarei tentato di utilizzare boost aiutanti iteratori, o puntatori prime per iniziare) e tutto ciò che le interfacce necessari. Si noti che quanto sopra deve funzionare per garantire che rimanga eccezionalmente sicuro.