C++：ベクトルの非連続インデックスに値を割り当てる？

Question

未知のサイズのベクトルを宣言したい場合は、インデックス5、インデックス10、インデックス1、インデックス100の順番で値を割り当てます。ベクターで簡単に実行できますか？

簡単な方法はないようです。私は、サイズを持たないベクトルを初期化する場合、resize（）または5つのpush_back（）を実行することによって、最初にメモリを割り当てずにインデックス5にアクセスすることはできません。しかし、resizeは以前に格納された値をベクトルにクリアします。私はそれにサイズを与えてベクトルを構築することができますが、ベクトルの大きさはわかりません。

固定サイズを宣言する必要はなく、ベクトル内の非連続インデックスにもアクセスできますか？

（私は配列がこのタスクの方が簡単だろうと思う）。

Answer 1

サイズ変更でベクターがクリアされません。これは、ベクトル内のすべての値を保持し、インデックスnがアクセス可能になるように、必要なだけのデフォルト初期化された値を追加します

if (v.size() <= n) 
     v.resize(n+1); 
    v[n] = 42; 

：あなたは簡単のような何かを行うことができます。

つまり、すべてのインデックスや連続したメモリが必要ない場合は、別のデータ構造を考慮する必要があります。

Answer 2

整数キーと値の間のstd :: mapは簡単な解決法ではありませんか？ベクトルには連続したメモリの割り当てが必要なので、時折のインデックスのみを使用している場合は、多くのメモリを「無駄にする」でしょう。

Answer 3

resize()は、以前にベクトルに格納された値をクリアしません。
がthis documentation

を参照してください私はまた、これはあなたがvectorはあなたのためのコンテナではないかもしれないこと、その可能性を行うために必要なものである場合と主張します。おそらくmapの使用を検討しましたか？

Answer 4

連続した値のセットを含まないデータ構造は、スパースまたは圧縮データ構造と呼ばれます。これはあなたが探しているものだと思われます。

この場合、スパースベクトルが必要です。ブーストに実装されているものが1つあります。link text

通常、メモリを節約するために疎構造が使用されます。問題の説明からは、実際にメモリの使用を気にする必要はなく、まだ存在しない要素に対処すること（自動サイズ変更のコンテナを使用すること）が可能です。この場合、外部依存関係のない単純な解は次のようになります。

ベクトルを保持し、すべてのベクトルメソッドをそれに転送するテンプレートクラスを作成します。インデックスが範囲外の場合は、演算子[]を変更してベクトルのサイズを変更します。

// A vector that resizes on dereference if the index is out of bounds. 
template<typename T> 
struct resize_vector 
{ 
    typedef typename std::vector<T>::size_type size_type; 
    // ... Repeat for iterator/value_type typedefs etc 

    size_type size() const { return m_impl.size() } 
    // ... Repeat for all other vector methods you want 

    value_type& operator[](size_type i) 
    { 
     if (i >= size()) 
      resize(i + 1); // Resize 
     return m_impl[i]; 
    } 
    // You may want a const overload of operator[] that throws 
    // instead of resizing (or make m_impl mutable, but thats ugly). 

private: 
    std::vector<T> m_impl; 
}; 

他の回答に記載されているように、ベクトルのサイズを変更すると要素はクリアされません。代わりに、新しい要素がサイズ変更によって追加されると、デフォルトのコンストラクタが呼び出されます。したがって、このクラスを使用する際には、operator[]がデフォルトの構築オブジェクト参照を返す可能性があることを知る必要があります。したがって、<T>のデフォルトのコンストラクタは、オブジェクトをこの目的に合った適切な値に設定する必要があります。たとえば、要素に以前に値が割り当てられているかどうかを知る必要がある場合は、センチネル値を使用できます。

std::map<size_t, T>を使用することの提案は、余分なメモリの使用、不連続な要素記憶域、およびO（1）ではなくO（logN）ルックアップを考慮した場合のメリットがあります。これは、疎な表現か自動サイズ変更のどちらを必要とするかにかかっています。うまくいけば、この答えは両方をカバーします。