2

非重複:

動機:

割り当ては (コンストラクタで) 1 回発生し、割り当て解除は (デストラクタで) 1 回発生します。

メモリ管理のオーバーヘッドを処理する必要のない、リスト内の任意の場所の要素の O(1) 挿入および削除。これは、配列ベースの実装では不可能です。

標準ライブラリを使用してこれを実装する簡単な方法はありますか? Boostにこのような実装はありますか？

4

3 に答える 3

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 に答える
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、範囲外になるとノードが破棄されます。

リストからアイテムを効率的に削除することは可能ですが、少し複雑です。「削除された」ノードのセカンダリ リンク リストがあります。メイン リストからa を削除する場合nodeは、「削除済み」リストの末尾/先頭に挿入します。

storage割り当てるときは、配列に移動する前に、まず削除済みリストを確認してください。それがNULLuseの場合storage、そうでない場合は、リストから抜き取ります。

于 2013-04-07T01:43:07.107 に答える
0

最終的に、rigid_list という名前のテンプレートを作成しました。完全にはほど遠いですが、それは始まりです：

https://github.com/eltomito/rigid_list

（Ulrich Eckhardtの回答に動機付けられた）

于 2015-12-22T12:05:40.717 に答える