C++ фиксированного размера связанного списка

Question

Non-дубликатами:

• Which STL C++ container to use for a fixed size list? (Specific вариант использования)
• std::list fixed size (см ниже)

Мотивы:

Распределение происходит один раз (в конструкторе), а освобождение происходит один раз (в деструкторе).

O (1) Вставка и удаление элемента в любом месте в списке без необходимости использования служебных данных управления памятью. Это невозможно при реализации на основе массива.

Есть ли простой подход для реализации этого с использованием стандартной библиотеки? Есть ли что-то подобное в Boost?

Answer 1

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

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

typedef std::list<...> list_t; 

struct fslist: private list_t 
{ 
    // reuse some parts from the baseclass 
    using list_t::iterator; 
    using list_t::const_iterator; 
    using list_t::begin; 
    using list_t::end; 
    using list_t::empty; 
    using list_t::size; 

    void reserve(size_t n) 
    { 
     size_t s = size(); 
     // TODO: Do what std::vector does when reserving less than the size. 
     if(n < s) 
      return; 
     m_free_list.resize(n - s); 
    } 

    void push_back(element_type const& e) 
    { 
     reserve_one(); 
     m_free_list.front() = e; 
     splice(end(), m_free_list, m_free_list.begin()); 
    } 

    void erase(iterator it) 
    { 
     m_free_list.splice(m_free_list.begin(), *this, it); 
    } 

private: 
    // make sure we have space for another element 
    void reserve_one() 
    { 
     if(m_free_list.empty()) 
      throw std::bad_alloc(); 
    } 
    list_t m_free_list; 
}; 

Это неполный, но он должен вас начать. Также обратите внимание, что splice() не становится общедоступным, потому что перемещение элементов из или в другой список изменит размер и емкость.

Answer 2

Я думаю, что самый простой способ сделать это - иметь 2 структуры данных. Массив/вектор, который имеет фиксированный размер и используется для «выделения». Вы просто извлекаете элемент из массива для создания узла и вставляете его в свой список. Нечто подобное, кажется, встретить вас требования:

struct node { 
    node *prev; 
    node *next; 
    int value; 
}; 

node storage[N]; 
node *storage_ptr = storage; 

затем создать новый узел:

if(node == &[storage + N]) { 
    /* out of space */ 
} 

node *new_node = *storage_ptr++; 
// insert new_node into linked list 

Это фиксированный размер, выделяется сразу, а когда storage выходит из области видимости, узлы будут уничтожены вместе с ним.

Что касается эффективного удаления элементов из списка, это выполнимо, но немного сложнее. У меня был бы вторичный связанный список для «удаленных» узлов. Когда вы удаляете node из основного списка, вставьте его в конец/начало списка «удаленных».

При распределении сначала проверьте удаленный список перед переходом к массиву storage. Если это NULL, используйте storage, в противном случае вырвите его из списка.

Answer 3

В итоге я написал шаблон для этого типа rigid_list. Это далеко не полный, но это только начало:

https://github.com/eltomito/rigid_list

(мотивировано ответ Ульриха Экхардта)