7

2 つのマルチセットがあるとします。各要素が各 multiset に出現する回数を考慮して、最初の multiset から 2 番目の multiset に出現するすべての要素を削除したいと考えています。たとえば、multisetaに15 回含まれ、multisetにb2 回含まれている場合、 を計算するa -= bと、 から のインスタンスを 2 つだけ1削除する必要がありますa。

これを実現するコードを次に示します。

 multiset<int> a;
 multiset<int> b;

 // remove all items that occur in b from a, respecting count ("a -= b")
 for (multiset<int>::iterator i = b.begin(); i != b.end(); i++) {
    if (a.count(*i) < 1) {
       // error 
    }
    // a.erase(*i) would remove ALL elements equal to *i from a, but we 
    // only want to remove one.  a.find(*i) gives an iterator to the first
    // occurrence of *i in a.
    a.erase(a.find(*i));
  }

確かに、より良い/より慣用的な方法がありますか?

4

3 に答える 3

14

要素をstd::set_difference新しいセットに入れる必要がありますが、要素を元のセットから新しいセットに移動し、後で両方を交換するだけで最適化できます (int移動は必要ありませんが、この方法ではアルゴリズムは柔軟性と汎用性を維持します)。

std::multiset<int> c;
std::set_difference(std::make_move_iterator(a.begin()), 
                    std::make_move_iterator(a.end()), 
                    b.begin(), b.end(), 
                    std::inserter(c, c.begin()));
a.swap(c);

完全にインプレースではありませんが、複雑さは直線的でありながら、ほぼstd::insert_iterator慣用的です (は常に に適切なヒントを提供するためstd::multiset::insert)。

于 2013-04-18T09:57:04.647 に答える
2

std::set_differenceを参照してください

マルチセットでも機能します。

最新のドラフトn3485 25.4.5.4 [set.difference]から

Remarks: If [first1,last1) contains m elements that are equivalent to each other and
[first2, last2) contains n elements that are equivalent to them, the last max(m−n,0)
elements from [first1, last1) shall be copied to the output range.
于 2013-04-18T09:43:32.797 に答える
2

コンテナーは順序付けされているため、1 つのセットにのみ含まれる値をスキップして、両方を一度に繰り返すことができます。何かのようなもの：

for (auto i = a.begin, j = b.begin(); i != a.end() && j != b.end();) {
    if (*i < *j) {
        ++i;
    } else if (*j < *i) {
        ++j;
    } else {
        i = a.erase(i);
        ++j;
    }
}

これは、 および の対数時間呼び出しを回避して、線形の複雑さをcount持ちfindます。

または、保持したい要素を新しいマップに移動してもかまわない場合は、 を使用できますstd::set_difference。ただし、各要素を出力マップに挿入する必要があるため、おそらく線形時間ではありません。

std::set_difference更新：適切なヒントが与えられた場合、挿入は線形である必要がありinsert_iterator、正しいヒントを提供するため、さらに調査すると、線形になるようです。したがって、新しいマルチセットを構築するために余分なメモリを使用することを気にしないのであれば、それはより慣用的なものと見なされるかもしれません。

于 2013-04-18T09:44:59.817 に答える