0

私はかなり単純で明白なイテレータソリューションを持っていますが、SOをタップして、誰かがここで答えに現れる時折の素晴らしいレシピの1つを思い付くかどうかを確認すると思いました:)

状況は次のとおりです。

  • 現在 a に格納されている既知の使用可能なサイズの int の複数のベクトルは、vector<vector<int>>実行時にのみ認識される API 要求と vect の数が混在しているため、これを回避できません。
  • これらはいくつあってもかまいませんが、現実的に言えば、常に数個から数十個程度です (ベクター)。
  • 順序は重要ではないので、並べ替えと順序付けのトリックと最適化は公正なゲームです (この段階では必要性を見つけたわけではありませんが、以下のボーナスの質問を考えると、それらが発生する可能性があります)。
  • その時点でのベクトルは使い捨てなので、ムーブ トリックも公正なゲームです。
  • サイズは通常小さいですが、まれではあるが違法ではないエッジケースでは、これらの一部またはすべてで数百万の int を超える可能性があります。
  • メモリはそれほど問題ではありません。通常、常に数 GB の連続したメモリが利用可能であり、これは重要なシステムではありません。
  • パフォーマンスは重要ではありません。これはフライト前のチェックですが、まだユーザーが直面しているため、アプリがハングしているようには見えません。エッジケースの種類のシナリオでは、ほんの数秒です。

私は現在、厳密なバイナリ要件を持つ 2 つの API の間でバインドされているため、これは GCC 4.1.x に制限されているため、利用可能な C++0x、Boost 1.44 が絶対的かつ狂ったように不足しています。

現時点では、これらの vect にはすべて一意のインデックスが含まれていますが、将来的には、重複を削除した単一のフィルター処理された配列を生成することも必要になる可能性があります (将来の使用には、インデックスが重複するフィードが含まれる可能性があります)。

C++11 ソリューションまたは関連するものは引き続き歓迎します。私は宿題をやってくれる人を探しているわけではありません。私は不格好ですが、とにかくうまくいく作品を持っています。私は啓蒙と料理本のインスピレーションを何よりも求めています。

前もって感謝します

4

1 に答える 1

1

あなたが何を望んでいるのかは100％明確ではありませんが、あなたが言ったことを最大限に活用して、私は次のようにします：

std::vector<std::vector<int>> v; // input, assume it's already filled
std::size_t size = 0;
for (std::vector<std::vector<int>>::const_iterator i = v.begin(); i != v.end(); ++i)
{
    size += i->size();
}

boost::scoped_array<int> array;
if (size != 0)
{
    array.reset(new int[size]);
    std::size_t offset = 0;
    for (std::vector<std::vector<int>>::const_iterator i = v.begin(); i != v.end(); ++i)
    {
        std::copy_n(&(*i)[0], i->size(), array + offset);
        offset += i->size();
    }
}

// ...use array...

array一意にしたい場合は、次のようにします。

std::sort(array.get(), array.get() + size);
std::size_t newSize = std::unique(array.get(), array.get() + size) - array.get();
// Now array is unique, assuming you only use elements [0, newSize)

おそらく、並べ替えて一意にするより効率的な方法があります（おそらく、各サブベクトルを並べ替えてから、それらを新しい配列にコピーするときにマージソートスタイルの操作を実行します（そして単に既存のアイテムをコピーしません））が、私は目指しています私の答えではシンプル+正しい。既知の正しい解があれば、最適化は後で行うことができます。

于 2013-09-07T00:09:42.227 に答える