2

構造体の配列があります。配列のサイズは N です。

配列から重複を削除したい。つまり、インプレース変更を行い、配列を変換して各構造体の外観を 1 つにします。さらに、新しいサイズ M (削減された配列の最大インデックス) を知りたいです。

構造体にはプリミティブが含まれているため、それらを比較するのは簡単です。

C ++で効率的に行うにはどうすればよいですか?

次の演算子を実装しました。

bool operator==(const A &rhs1, const A &rhs2) 
{       
    return ( ( rhs1.x== rhs2.x )  &&
             ( rhs1.y == rhs2.y ) );
}

bool operator<(const A &rhs1, const A &rhs2) 
{       
    if ( rhs1.x == rhs2.x )  
             return ( rhs1.y < rhs2.y );

    return ( rhs1.x < rhs2.x );
}

ただし、実行時にエラーが発生します。

std::sort(array, array+ numTotalAvailable);

 * array will have all elements here valid.

std::unique_copy(
        array, 
        array+ numTotalAvailable, 
        back_inserter(uniqueElements)); 

 * uniqueElements will have non-valid elements.

ここで何が問題なのですか？

4

4 に答える 4

6

std::sortとのstd::uniqueアルゴリズムの組み合わせを使用して、これを実現できます。

std::sort(elems.begin(), elems.end());                  // Now in sorted order.
iterator itr = std::unique(elems.begin(), elems.end()); // Duplicates overwritten
elems.erase(itr, elems.end());                          // Space reclaimed

生の配列 (たとえば、 a ではないstd::vector) を使用している場合、要素を新しい範囲にコピーしない限り、実際にスペースを再利用することはできません。ただし、生の配列から始めてstd::vectororstd::dequeのようなもので終わっても問題ない場合は、 と イテレータ アダプターを使用unique_copyして、一意の要素だけをコピーできます。

std::sort(array, array + size); // Now in sorted order

std::vector<T> uniqueElements;
std::unique_copy(array, array + size,
                 back_inserter(uniqueElements)); // Append unique elements

この時点で、uniqueElementsすべての固有の要素が保持されます。

最後に、最初の質問にもっと直接的に対処します。これをその場で行いたい場合は、からの戻り値を使用して、unique残っている要素の数を判断することで答えを得ることができます。

std::sort(elems, elems + N);                // Now in sorted order.
T* endpoint = std::unique(elems, elems + N);// Duplicates overwritten
ptrdiff_t M = endpoint - elems;             // Find number of elements left

お役に立てれば！

于 2011-08-24T17:59:20.203 に答える
1 
std::set<T>  uniqueItems(v.begin(), v.end());

uniqueItemsユニークなアイテムのみが含まれるようになりました。あなたがそれでやりたいことは何でもしてください。vおそらく、すべてのユニークなアイテムを含めたいと思うでしょう。その場合は、次のようにします。

//assuming v is std::vector<T>
std::vector<T>(uniqueItems.begin(), uniqueItems.end()).swap(v);

vすべてのユニークなアイテムが含まれるようになりました。またv、最小サイズに縮小します。Shrink-to-fitイディオムを活用しています。

于 2011-08-24T18:07:27.813 に答える
0

配列にアルゴリズムを適用する別の方法は、その要素をstd::set. このようにすることが合理的かどうかは、アイテムをどのように使用する予定かによって異なります。

于 2011-08-24T18:07:46.763 に答える
0

flyweight パターンを使用できます。これを行う最も簡単な方法は、Boost Flyweight ライブラリを使用することです。

編集:Boost flyweight 実装によって格納されているオブジェクトの数を確認する方法があるかどうかはわかりません。ある場合、ドキュメントで見つけることができないようです。

于 2011-08-24T17:56:43.247 に答える