この質問は、あらゆるタイプの静的データに適用されます。int例を単純にするためだけに使用しています。
int を含む大きな XML データ ファイルを読み込んで、vector<int>. 私が使用している特定のデータについては、同じ値が何度も連続して繰り返されることは非常に一般的です。
<Node value="4" count="4000">
このcount属性は、値が x 回繰り返されることを意味します。
for(int i = 0; i < 4000; i++)
vec.push_back(4);
4000回連続して現れることがわかっているのに、同じ値を繰り返し格納するのはメモリの無駄のようです。ただし、いつでもベクトルにインデックスを付けることができる必要があります。
より大きなデータ オブジェクトの場合、ポインタを格納するだけでよいことはわかっていますが、上記の例では 4000 個の同一のポインタを格納する必要があります。
このような問題に対処するための戦略はありますか?
2 つのベクトルを使用します。最初のベクトルにはインデックスが含まれ、2 番目のベクトルには実際の値が含まれます。
インデックス [i-1] とインデックス [i] の間のすべてのインデックスの値が値 [i] にあるように、インデックス ベクトルを埋めます。
次に、indexs 配列で二分探索を使用して、values 配列内の位置を特定します。二分探索は非常に効率的 (O(log n)) であり、元のアプローチと比較してメモリの一部しか使用しません。
次のデータを想定した場合:
4000 ints with value "4"
followed by 200 ints with value "3"
followed by 5000 ints with value "10"
インデックス ベクトルと値ベクトルを作成し、次のように入力します。
indices = {4000, 4200, 9200}; // indices[i+1] = indices [i] + new_count or 0
values = {4,3,10};
他の回答で示唆されているように、おそらくこれを operator[] でラップする必要があります。
を使用する代わりに、特定のクラスを作成することをお勧めしvectorます。クラスは、アイテムがリストに出現する回数を保持し、スマートな方法でインデックスを計算するだけで、インデックスに基づいて要素を簡単に取得できるようにする必要があります。
ベクトルのようなインターフェイス (など) を使用してデータをいくつかのオブジェクトにラップするようにしてください。operator[]これにより、実装の詳細を非表示にすることができます (つまり、実際には 4000 の数値を格納していません) が、同様のインターフェイスを提供します。