122

2つの違いは何ですか？つまり、方法はすべて同じです。したがって、ユーザーにとっては、同じように機能します。

あれは正しいですか？？

4

9 に答える 9

152

違いをリストアップしましょう：

  • Dequeは、動的配列を使用して要素を管理し、 ランダムアクセスを提供し、ベクトルとほぼ同じインターフェイスを備えています。
  • リストはその要素を 二重にリンクされたリストとして管理し、ランダムアクセスを提供しません。
  • Dequeは、最後と最初の両方で高速な挿入と削除を提供します。中央の要素の挿入と削除は、両端までのすべての要素を移動してスペースを空けたり、ギャップを埋めたりする可能性があるため、比較的時間がかかります。
  • リストでは、要素の挿入と削除は、両端を含む各位置で高速です。
  • Deque：最初または最後以外の要素を挿入または削除すると、dequeの要素を参照するすべてのポインター、参照、およびイテレーターが無効になります。
  • リスト：要素を挿入および削除しても、他の要素へのポインター、参照、およびイテレーターは無効になりません。

複雑

             Insert/erase at the beginning       in middle        at the end

Deque:       Amortized constant                  Linear           Amortized constant
List:        Constant                            Constant         Constant
于 2009-09-17T02:20:47.330 に答える
67

（日付はあるがまだ非常に便利な）SGI STLの要約からdeque：

dequeはベクトルに非常によく似ています。ベクトルと同様に、要素へのランダムアクセス、シーケンスの最後での要素の一定時間の挿入と削除、および中央での要素の線形時間の挿入と削除をサポートするシーケンスです。

dequeがvectorと異なる主な方法は、dequeがシーケンスの先頭での要素の一定時間の挿入と削除もサポートすることです。さらに、dequeには、vectorのcapacity（）およびreserve（）に類似したメンバー関数がなく、これらのメンバー関数に関連付けられているイテレーターの有効性を保証するものではありません。

list同じサイトからの要約は次のとおりです。

リストは二重にリンクされたリストです。つまり、これは、順方向と逆方向の両方のトラバーサル、および（償却された）一定時間の要素の最初または最後、あるいは途中での挿入と削除をサポートするシーケンスです。リストには、挿入とスプライシングによってリスト要素へのイテレータが無効にならないという重要な特性があり、削除しても、削除された要素を指すイテレータのみが無効になります。イテレータの順序は変更される可能性があります（つまり、list :: iteratorは、リスト操作後に以前とは異なる先行または後続を持つ可能性があります）が、その無効化がない限り、イテレータ自体が無効になったり、異なる要素を指すようになったりすることはありません。または突然変異が明示的です。

要約すると、コンテナには共有ルーチンがある場合がありますが、それらのルーチンの時間保証はコンテナごとに異なります。これは、これらのコンテナーのどれをタスクに使用するかを検討するときに非常に重要です。コンテナーが最も頻繁に使用される方法（たとえば、挿入/削除よりも検索に多く）を考慮することは、適切なコンテナーに誘導するのに大いに役立ちます。 。

于 2009-09-16T23:34:58.880 に答える
14

std::list基本的には二重にリンクされたリストです。

std::deque一方、は、のように実装されますstd::vector。インデックスごとのアクセス時間が一定で、最初と最後に挿入と削除が行われるため、リストとは劇的に異なるパフォーマンス特性が得られます。

于 2009-09-16T23:36:52.040 に答える
8

もう1つの重要な保証は、それぞれの異なるコンテナがデータをメモリに格納する方法です。

  • ベクトルは、単一の連続したメモリブロックです。
  • dequeは、リンクされたメモリブロックのセットであり、各メモリブロックに複数の要素が格納されます。
  • リストは、メモリに分散された要素のセットです。つまり、メモリ「ブロック」ごとに1つの要素のみが格納されます。

dequeは、それぞれの欠点なしに、vectorとlistの両方の利点のバランスをとろうとするように設計されていることに注意してください。これは、マイクロコントローラーなどのメモリが制限されたプラットフォームで特に興味深いコンテナーです。

メモリストレージ戦略は見過ごされがちですが、特定のアプリケーションに最適なコンテナを選択することが最も重要な理由の1つであることがよくあります。

于 2014-10-26T22:28:31.310 に答える
4

いいえ。両端キューは、前面と背面でのO（1）の挿入と削除のみをサポートします。たとえば、ラップアラウンドを使用してベクターに実装できます。また、O（1）ランダムアクセスが保証されるため、二重にリンクされたリストを（単に）使用していないことを確認できます。

于 2009-09-16T23:25:27.100 に答える
4

C++クラスの生徒のためにイラストを作成しました。これは、GCC STL実装（ https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/）の実装（私の理解）に（大まかに）基づいてい ますstl_deque.hおよびhttps://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_list.h）

両端キュー

std::dequeのイラスト

コレクション内の要素はメモリブロックに保存されます。ブロックあたりの要素数は、要素のサイズによって異なります。要素が大きいほど、ブロックあたりの要素は少なくなります。根底にある希望は、要素のタイプに関係なくブロックが同じサイズである場合、それがほとんどの場合アロケータに役立つはずであるということです。

メモリブロックを一覧表示する配列（GCC実装ではマップと呼ばれます）があります。最初に空きがある可能性がある最初のブロックと最後に空きがある可能性がある最後のブロックを除いて、すべてのメモリブロックがいっぱいです。マップ自体は、中心から外側に向かって塗りつぶされます。これは、逆に、std::vector両端での挿入を一定時間で行うことができる方法です。と同様にstd:::vector、ランダムアクセスは一定時間で可能ですが、1つではなく2つの間接アクセスが必要です。と同様にstd::vector、または逆にstd::list、中央の要素を削除または挿入すると、データ構造の大部分を再編成する必要があるため、コストがかかります。

二重リンクリスト

std::listのイラスト

二重リンクリストはおそらくもっと普通です。すべての要素は、他の要素から独立して割り当てられた独自のメモリブロックに格納されます。各ブロックには、要素の値と2つのポインターがあります。1つは前の要素へ、もう1つは次の要素へです。これにより、リスト内の任意の位置に要素を挿入したり、要素のサブチェーンをあるリストから別のリストに移動したりすることが非常に簡単になります（スプライシングと呼ばれる操作）。挿入の最初と最後でポインターを更新するだけです。点。欠点は、インデックスで1つの要素を見つけるには、ポインターのチェーンをたどる必要があるため、ランダムアクセスでは、リスト内の要素の数に線形のコストがかかることです。

于 2020-12-28T09:34:09.320 に答える
2

との間の顕著な違いの中dequeでlist

  • の場合deque：

    並べて保管されたアイテム。

    2つの側面（前面、背面）からのデータを追加するために最適化されています。

    数値（整数）でインデックス付けされた要素。

    イテレータ、さらには要素のインデックスで参照できます。

    データへの時間アクセスはより高速です。

  • にとってlist

    メモリに「ランダムに」保存されたアイテム。

    イテレータのみが閲覧できます。

    中央での挿入と取り外しに最適化されています。

    データへの時間アクセスは、空間的な局所性が非常に低いため、反復が遅くなります。

    非常に大きな要素をうまく処理します

次のリンクも確認できます。このリンクは、2つのSTLコンテナー間のパフォーマンスを比較しています（std :: vectorを使用）。

私がいくつかの有用な情報を共有したことを願っています。

于 2020-05-22T03:51:22.010 に答える
1

パフォーマンスの違いは他の人によってよく説明されています。オブジェクト指向プログラミングでは、類似または同一のインターフェースが一般的であるということを付け加えたかっただけです。これは、オブジェクト指向ソフトウェアを作成する一般的な方法論の一部です。2つのクラスが同じインターフェイスを実装しているという理由だけで同じように機能するとは限りません。また、attack（）とmake_noise（）を実装しているため、馬は犬のように機能すると想定する必要があります。

于 2009-09-17T00:05:45.630 に答える
1

これは、O（1）ルックアップとO（1）の正確なLRUメンテナンスを提供する、リスト、コード化されていないマップの概念実証コードの使用です。消去操作を生き残るために（消去されていない）イテレータが必要です。GPUメモリ上のCPUポインタ用にO（1）の任意の大きさのソフトウェア管理キャッシュで使用することを計画します。Linux O（1）スケジューラーにうなずきます（プロセッサーごとにLRU <->実行キュー）。unordered_mapは、ハッシュテーブルを介して一定時間アクセスできます。

#include <iostream> 
#include <list> 
#include <unordered_map>  
using namespace std; 

struct MapEntry {
  list<uint64_t>::iterator LRU_entry;
  uint64_t CpuPtr;
};
typedef unordered_map<uint64_t,MapEntry> Table;
typedef list<uint64_t> FIFO;
FIFO  LRU;        // LRU list at a given priority 
Table DeviceBuffer; // Table of device buffers

void Print(void){
  for (FIFO::iterator l = LRU.begin(); l != LRU.end(); l++) {
    std::cout<< "LRU    entry "<< *l << "   :    " ;
    std::cout<< "Buffer entry "<< DeviceBuffer[*l].CpuPtr <<endl;
  }  
}
int main() 
{ 

  LRU.push_back(0);
  LRU.push_back(1);
  LRU.push_back(2);
  LRU.push_back(3);
  LRU.push_back(4);

  for (FIFO::iterator i = LRU.begin(); i != LRU.end(); i++) {
    MapEntry ME = { i, *i}; 
    DeviceBuffer[*i] = ME;
  }

  std::cout<< "************ Initial set of CpuPtrs" <<endl;
  Print();

  {
    // Suppose evict an entry - find it via "key - memory address uin64_t" and remove from 
    // cache "tag" table AND LRU list with O(1) operations
    uint64_t key=2;
    LRU.erase(DeviceBuffer[2].LRU_entry);
    DeviceBuffer.erase(2);
  }

  std::cout<< "************ Remove item 2 " <<endl;
  Print();

  { 
    // Insert a new allocation in both tag table, and LRU ordering wiith O(1) operations
    uint64_t key=9;
    LRU.push_front(key); 
    MapEntry ME = { LRU.begin(), key };
    DeviceBuffer[key]=ME;
  }

  std::cout<< "************ Add item 9  " <<endl;
  Print();

  std::cout << "Victim "<<LRU.back()<<endl;
}
于 2020-05-22T00:49:16.720 に答える