2

非重复：

动机：

分配发生一次（在构造函数中），释放发生一次（在析构函数中）。

O(1) 在列表中的任何位置插入和删除元素，而无需处理内存管理的开销。这对于基于数组的实现是不可能的。

是否有使用标准库实现此功能的简单方法？在 Boost 中有这样的实现吗？

4

3 回答 3

1

我认为最简单的方法是拥有 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超出范围时，节点将被销毁。

至于有效地从列表中删除项目，它是可行的，但稍微复杂一些。我将有一个用于“已删除”节点的二级链表。从主列表中删除 anode时，将其插入“已删除”列表的末尾/开头。

分配时，先检查已删除的列表，然后再进入storage数组。如果是NULLuse storage，否则，将其从列表中删除。

于 2013-04-07T01:43:07.107 回答
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() 未公开，因为将元素移入或移入不同的列表会改变大小和容量。

于 2013-04-07T09:09:41.010 回答
0

我最终为此编写了一个名为rigid_list 的模板。它远未完成，但它是一个开始：

https://github.com/eltomito/rigid_list

（受 Ulrich Eckhardt 回答的启发）

于 2015-12-22T12:05:40.717 回答