2

以下の目的が解決されるように、適切なデータ構造（C ++）を提案します。

  1. 最後に要素を挿入します。
  2. 要素を最後から読み取って削除します。
  3. 要素を最初から読み取って削除します。
  4. 特定の要素が存在するかどうかを調べます。

現在、私はベクトルを使用しています。しかし、特定の要素が存在するかどうかを見つけることは、私の要素がソートされていないため、ベクトルの時間計算量が非常に複雑です。

これを達成するために、ベクトルよりも優れたデータ構造がありますか？はいの場合は、どれを使用して例を挙げてください。

4

6 に答える 6

3

1つの可能性は、基本的にハッシュテーブルであるstd::setまたはstd::unordered_setを使用し、要素間の順序を自分で維持することです。これにより、O（log（n））または償却されたO（1）ルックアップの複雑さと、開始/終了時の一定の挿入/削除が可能になります。Javaでは、これはLinkedHashSetと呼ばれます。残念ながら、STLはこの種のデータ構造をそのままでは提供しませんが、set/unordered_setまたはmap/unordered_mapの上に簡単に実装できるはずです。

アイデアを説明するコードは次のとおりです。

template <typename T>
class linked_set {
 private:
  // Comparator of values with dereferencing.
  struct value_deref_less {
    bool operator()(const T *lhs, const T *rhs) const {
      return *lhs < *rhs;
    }
  };

  typedef std::set<const T*, value_deref_less> Set;
  Set set_;              // Used for quick lookup
  std::deque<T> store_;  // Used for ordered storage. deque is used instead of
                         // vector because the former doesn't invalidate
                         // pointers/iterators when elements are pushed.

 public:
  void push_back(const T& value) {
    store_.push_back(value);
    set_.insert(&store_.back());
    // TODO: handle the case of duplicate elements.
  }

  // TODO: better provide your own iterator.
  typedef typename Set::iterator iterator;

  iterator find(const T& value) { return set_.find(&value); }

  // ...
};
于 2012-07-03T21:47:00.053 に答える
2

少なくとも可能性をSTLに制限した場合、両側での高速挿入と同じコンテナーでの高速検索の両方を行うことはできません。よりエキゾチックな非標準のコンテナが役立つ場合があります。

しかし、これらの場合に私が一般的に選択するアプローチは、2つのコンテナーを使用することです。要素を格納するための明白なオプションはstd::dequeです。検索の場合は、std::map<K,V>ここで、Vは両端キューのイテレータです。dequesでの挿入/削除は、関係のないイテレータを無効にしないため、マップとdequeを常に同期することを忘れないでください（つまり、dequeで挿入または削除を行う場合は、マップでも同期してください）。 。イテレータを使用する代わりに、別のより簡単で安全なオプション（マップで検索した後、見つかった要素だけが必要な場合（近くの要素にアクセスする必要がない場合など））は、両端キューとマップの両方をスマートにすることです。実際のオブジェクト（より具体的には、shared_ptr）へのポインター。繰り返しますが、両方の同期を保つように注意する必要があります。同期が緩んでも壊滅的ではありませんが、もちろん、プログラムの一貫性が損なわれる可能性があります。

struct MyItem
{
    std::string name;
    int something;
    int another;
    MyItem(const std::string &name_, int something_, int another_)
        :name(name_), something(something_), another(another_) {}
};

class MyContainer
{
    public:
        typedef std::shared_ptr<MyItem> MyItemPtr;

        void push_front(MyItemPtr item)
        {
            deque.push_front(item);
            assert(map.find(item->name) == map.end());
            map[item->name] = item;
        }
        void push_back(MyItemPtr item)
        {
            deque.push_back(item);
            assert(map.find(item->name) == map.end());
            map[item->name] = item;
        }
        MyItemPtr pop_front()
        {
            item = deque.front();
            deque.pop_front();
            map.erase(item->name);
            return item;
        }
        MyItemPtr pop_back()
        {
            item = deque.back();
            deque.pop_back();
            map.erase(item->name);
            return item;
        }
        MyItemPtr find(const std::string &name)
        {
            std::map<std::string, MyItemPtr>::iterator iter = map.find(name);
            if (iter == map.end())
                return MyItemPtr();
            else
                return iter->second;
        }

    private:
        std::deque<MyItemPtr> deque;
        std::map<std::string, MyItemPtr> map;
};

それを使用するには：

MyContainer container;

MyContainer::MyItemPtr a(new MyItem("blah", 1, 2));
container.push_back(a);
MyContainer::MyItemPtr b(new MyItem("foo", 5, 6));
container.push_front(b);

MyContainer::MyItemPtr f = container.find("blah");
if (f)
    cout << f->name << ", " << f->something << ", " << f->another;
于 2012-07-03T21:59:29.483 に答える
1

std::map対数の複雑さが適切かどうかを確認するために、から始める必要があります。

B + Treeはもう少し複雑で、オープンソースの実装を見つけるために独自の実装または調査が必要になります。std::mapしかし、それでも不十分であることが判明した場合は、引用した（検索）要件と問題点を考慮すると、これは合理的な選択です。

たとえば、要素の値をそのイテレータにマップしますstd::list。すべての操作は、O（lg n）とstd::map。

于 2012-07-03T21:37:29.170 に答える
1

を保持できますが、高速クエリにはをvector使用することもできます。std::set

挿入した最初/最後の要素がどれであるかが実際にはわからないため、セットは最初/最後から要素を削除するのに十分ではありません。これらの要素への参照を保持することもできますが、削除をサポートするには、次の要素などが必要になります。これにより、もう1つのコンテナを使用するようになります。

于 2012-07-03T21:45:52.543 に答える
0

を使用しstd::dequeます。これは両端キューであり、などの標準インターフェイスのコンテナとしても使用されますstd::stack。

これは通常、準リンクリストの実装を使用し、エッジでの挿入と削除のO（1）時間計算量を償却します。

于 2012-07-03T21:36:38.433 に答える
0

挿入/削除が多い場合は、リンクリストの方が適切です。
リンクリスト（シングルまたはダブル）にはかなりのオーバーヘッドがあることに注意してください（通常はポインターのサイズですが、実装は異なります）。

標準テンプレートライブラリは、std::listを提供します。

于 2012-07-03T22:00:01.113 に答える