2

順次コンテナーがあり、そのコンテナー内に現在「アクティブ」な要素の範囲 (イテレーターのペア) があるとします。ある時点で、アクティブにする必要がある要素の新しい範囲を計算しますが、これは前の範囲と重なる可能性があります。次に、古いアクティブな範囲にあったが、新しいアクティブな範囲にない要素を繰り返して「非アクティブ化」します（同様に、新しい範囲にあるが古い範囲にはない要素を繰り返して「アクティブ化します」 ' 彼ら）。

これは可能ですか？

新しいアクティブな範囲の開始が、古いアクティブな範囲の開始よりもコンテナ内で常に後になることを知っていれば、作業は簡単になりますか?

質問の目的のために、コンテナがベクトルであると仮定します。

4

4 に答える 4

2

最後のアクティブ範囲に2つのセットを使用し、現在のアクティブ範囲にもう1つのセットを使用できます。アルゴリズムを使用して、set_differenceアクティブ化/非アクティブ化するオブジェクトを取得します。

于 2009-05-13T10:01:29.773 に答える
2

必要なのはrange_difference関数です。私は Boost.Range がこのようなものを提供すると思っていましたが、彼らのドキュメントには何も見つかりませんでした (まあ、私はあまり徹底的に検索しませんでした...)。

次の関数は、(first1,last1) で示される範囲と (first2,last2) で示される範囲の差の結果を含む範囲のペアを返します。前提条件として、first1 は first2 の前または同じ位置に配置する必要があります。

template <typename InputIterator>
std::pair<
    std::pair<InputIterator, InputIterator>, 
    std::pair<InputIterator, InputIterator> >
range_difference(InputIterator first1, InputIterator last1,
                 InputIterator first2, InputIterator last2)
{
    typedef std::pair<InputIterator, InputIterator> Range;

    InputIterator it;

    // first1 must be <= first2
    for (it = first1 ; it != last1 && it != first2 ; ++it);

    Range left_range = std::make_pair(first1, it); // Left range

    if (it == last1) 
        return std::make_pair(left_range, std::make_pair(first2, first2));

    // it == first2
    while (it != last1 && it != last2) ++it;

    return std::make_pair(left_range, std::make_pair(it, last1)); // Right range
}

range2 が range1 に完全に含まれている場合、差の結果は 2 つの部分で構成されます。左の範囲と右の範囲になります。

  |_____________________|__________________|________________________|    
first1                first2             last2                    last1

この場合、関数は (first1, first2),(last2, last1) を返します。

この別の構成では、

  |_____________________|                 |________________________|    
first1                last1             first2                    last2

関数は (first1, last1),(first2, first2) を返します。他にも多くの可能な構成があります。ただし、知っておくべき重要なことの 1 つは、右側の範囲が空の場合、max(first2, last1)に配置されるということです。この例で、これがどのように必要であるかがわかります。

最後に、first1 と first2 が同じ位置にある場合、返される左側の範囲は空の id (first1,first1) になります。

では、この関数を使用して問題を解決するにはどうすればよいでしょうか。「非アクティブ化」範囲ではかなり簡単ですが、「アクティブ化」範囲では少しトリッキーです。

typedef std::vector<Activable>::iterator Iterator;

Iterator old_beg, old_end, new_beg, new_end; // Old and new ranges

typedef std::pair<Iterator, Iterator> Range;
typedef std::pair<Range, Range> SplitRange;

SplitRange deactivate = range_difference(old_beg, old_end, new_beg, new_end);

// Left range
for (Iterator it = deactivate.first.first;
     it != deactivate.first.second;
     ++it)
    it->deactivate();

// Right range
for (Iterator it = deactivate.second.first;
     it != deactivate.second.second;
     ++it)
    it->deactivate();


SplitRange activate = 
    range_difference(new_beg, new_end, new_beg, deactivate.second.first);
// Note the use of the previously returned right range -------^

for (Iterator it = activate.second.first;
     it != activate.second.second;
     ++it)
    it->activate();

そして、そこに行きます。たぶん、この解決策はあなたの問題に対して少しやり過ぎかもしれませんが、このrange_difference機能は多くの場所で役立つと思います.

于 2009-05-13T16:13:23.707 に答える
1

簡単な解決策は次のとおりです。

typedef std::pair<std::vector<T>::iterator, std::vector<T>::iterator> Range;
void Update(std::vector<T>& v, Range oldActive, Range newActive)
{
    int op = 0;
    for (std::vector<T>::iterator i = v.begin(), end = v.end(); i != end; ++i)
    {
        if (i == oldActive.first) op += 1;
        if (i == oldActive.second) op -= 1;
        if (i == newActive.first) op += 2;
        if (i == newActive.second) op -= 2;
        if (op == 1) i->Deactivate();
        if (op == 2) i->Activate();
    }
}

これは、ベクトル全体をスキャンするため、出発点として効率よりも単純さを意図的に優先します。一方、これはシングル パスであり、コピーは行いません。

于 2009-05-13T11:32:22.153 に答える
1

私はそれを簡単に保つと思います：

// Iterators denoting the old and new ranges (might be cleaner to use some kind
// of typedef like James Hopkin's did, but that's not the most important)
std::vector<Activable>::iterator old_beg,
                                 old_end,
                                 new_beg,
                                 new_end;

std::vector<Activable>::iterator it;

// Deactivate
for (it = old_beg ;                   // go from the beginning of the old range
     it != old_end && it != new_beg ; // to either the end of the old one or the
     ++it)                            // beginning of the new one
    it->deactivate();

// "Jump" to the correct position
if (it == old_end) it = new_beg; // no overlap
else               it = old_end; // overlap

// Activate
for (; it != new_end ; ++it)
    it->activate();

新しい範囲を古い範囲に完全に含めることはできないと仮定したことに注意してください (たとえば、古い範囲をインデックス 4 から 10 に変更し、新しい範囲を 5 から 7 に変更することはできません)。この場合、アルゴリズムを少し変更する必要があります。

于 2009-05-13T13:46:14.337 に答える