2

假设我有一个顺序容器，以及该容器中当前“活动”的元素的范围（一对迭代器）。在某个时候，我计算了一个新的应该处于活动状态的元素范围，它可能与之前的范围重叠。然后，我想迭代旧活动范围内但不在新活动范围内的元素以“停用”它们（并类似地迭代新范围内但不是旧范围内的元素以“激活” ' 他们）。

这可能吗？

如果我知道新活动范围的开始在容器中总是比旧活动范围的开始晚，是否会变得更容易？

出于问题的目的，假设容器是一个向量。

4

4 回答 4

2

您可以将两组用于最后一个活动范围，另一个用于当前活动范围。使用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 中，则差异的结果可以由两部分组成。你最终得到一个左范围和一个右范围：

  |_____________________|__________________|________________________|    
first1                first2             last2                    last1

在这种情况下，函数返回 (first1, first2),(last2, last1)。

在这个其他配置中，

  |_____________________|                 |________________________|    
first1                last1             first2                    last2

函数返回 (first1, last1),(first2, first2)。还有许多其他可能的配置。但是，要知道的重要一点是，在正确范围为空的情况下，它将位于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 回答