c++ - STL 中的 remove_neighbors 就像时尚

Question

我正在尝试以 STL 方式实现具有以下功能的算法:

给定一个范围 [first,last)，一个邻域范围 nSpan 和一个(二进制)谓词 Pred，它删除该范围内的元素，因此 Pred 对于彼此相距至多 nSpan

的任何剩余元素都不成立

示例:

• nSpan=1 and Pred=Equality => 衰减到 std::unique 算法

• nSpan=2 和 Pred=PointEquality => 清理折线

               + P2
               | 
               v
               ^
  P0           |          P4               P0          P1          P4
  +---->-------+---->------+    becomes    +---->-------+---->------+
             P1  P3
  

• nSpan=2 and Pred=Equality: ['a', 'b', 'a', 'd', 'e', 'd', 'f'] -> ['a', 'd', 'f']

在最后一个例子中，很明显(为了防止算法变得模棱两可)我们从第一个迭代器开始扫描，然后继续扫描，同时检查 nSpan 距离以删除元素(否则会有多种删除元素的方法)。

到目前为止，我的尝试(下面的代码 list )存在以下缺点:

• 在第一次扫描之后，新范围可能包含无效的新元素，因此需要递归功能(再次从新开始扫描到结束)来重新扫描范围(或者可能模仿每次删除发生时递归)
• 它不是作为一个remove 函数实现的，而是作为一个erase 函数实现的(我需要一个 remove 函数，这似乎要困难得多)和强制提供整个容器作为参数而不是范围(理想情况下，算法应该与容器无关)

我列出了一个 first attempt

    template<typename Cont, typename It, class Pr>
    void erase_neighbors(Cont &cont, It first, It last, int nSpan, Pr Pred)
    {
        if (0 < nSpan && nSpan < std::distance(first, last)) for (It it2; (it2 = first), first != last; )
        {
            if (nSpan < std::distance(it2, last))
            {
                std::advance(it2, nSpan);
                if (Pred(*first, *it2))
                {
                    first = cont.erase(first, it2);
                    last = cont.end();
                    continue;
                }
            }
            ++first;
        }
    }

理想签名

template<typename It, class Pr>
It remove_neighbors(It first, It last, int nSpan, Pr Pred);

理想的实现:非 c++11 且没有 boost(即使有相关的 boost 算法我也很乐意知道)

Answer 1

就我对问题陈述的理解而言，这似乎可以满足您的要求。看吧in action :

template<typename It, class Pr>
It remove_neighbors(It first, It last, int nSpan, Pr Pred) {
  if (first == last || nSpan <= 0) return last;

  It lastGood = first;
  It cur = first;
  ++cur;
  for (; cur != last; ++cur) {
    bool found = false;
    It back = lastGood;
    for (int i = nSpan; i > 0; --i, --back) {
      if (Pred(*back, *cur)) {
        found = true;
        lastGood = back;
        break;
      }
      if (back == first) break;
    }

    if (!found) {
      ++lastGood;
      *lastGood = std::move(*cur);
    }
  }
  ++lastGood;
  return lastGood;
}

这不会超过 N 次移动/复制，并且不会超过 N * nSpan 次调用 Pred。