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

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

给定一个范围[first,last)，一个邻域跨度nSpan和一个(二进制)谓词Pred，它将删除该范围内的元素，因此对于彼此之间距离最大的任何剩余元素Pred都不正确nSpan

示例:

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

nSpan = 2和Pred = PointEquality =>清除折线

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

nSpan = 2和Pred = Equality:['a'，'b'，'a'，'d'，'e'，'d'，'f']-> ['a'，'d'，' f']

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

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

第一次扫描后，新范围可能包含无效的新元素，因此需要递归功能(再次从新起点到末尾进行扫描)以重新扫描范围(或可能在每次删除操作时模仿递归)

它不是作为remove函数实现的，而是作为erase函数实现的(我需要删除一个，这似乎要困难得多)，并且强制提供整个容器作为参数而不是范围(理想情况下，算法应为容器不可知)

我正在列出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算法，我也很高兴知道)

最佳答案

在我理解问题陈述的范围内，这似乎可以满足您的要求。看到它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调用。