在 C++ 中移除序列中连续重复的特定值

栏目: C++ · 发布时间: 5年前

内容简介:最近在写 YTL 中的字符串相关辅助函数。实现到If——

最近在写 YTL 中的字符串相关辅助函数。实现到 split 函数时,希望能够实现类似 Python 当中的 str.split 方法的功能。

If sep is not specified or is None , a different splitting algorithm is applied: runs of consecutive whitespace are regarded as a single separator, and the result will contain no empty strings at the start or end if the string has leading or trailing whitespace.

—— https://docs.python.org/3/library/stdtypes.html#str.split

也就是说,在最基本的 split 的基础上,要添加两个功能:

  • 删除输入字符串首尾的空白;
  • 将字符串中的连续分隔符当成一个分隔符看待。

前一个功能很好实现。将空白符保存在 const char* trim_chars = " \t\n\r\v\f" 当中,然后使用 std::string::find_first_not_of 以及 std::string::find_last_not_of 即可找到有效内容的起止位置,最后再 std::string::erase 一下就好了。

后一个功能也不复杂。但要写得优雅——最好是能利用上标准库的设施——就不那么容易了。

std::unique 的基本用法

std::unique 是定义在 algorithm 头文件内的容器算法。它有两种基本形式:

template< class ForwardIt >
ForwardIt unique( ForwardIt first, ForwardIt last );
template< class ForwardIt, class BinaryPredicate >
ForwardIt unique( ForwardIt first, ForwardIt last, BinaryPredicate p );

其中,第一种形式是第二种形式的特例,它等价于 BinaryPredicate p 为连续两元素相等性判断时的第二种形式:

template< class ForwardIt,
          class BinaryPredicate =
            std::function<bool(const typename std::iterator_traits<ForwardIt>::value_type&,
              const typename std::iterator_traits<ForwardIt>::value_type&)>
ForwardIt unique( ForwardIt first, ForwardIt last,
            BinaryPredicate p = [](const typename std::iterator_traits<ForwardIt>::value_type& lhs,
                                   const typename std::iterator_traits<ForwardIt>::value_type& rhs) {
                                        return lhs == rhs; });

这也就是说,第一种形式的 std::unique 会找到每个连续重复的区间,而后保留这些区间的首个元素,最后返回新序列逻辑上的尾后迭代器。例如, aabbccaa 经过 std::unique 处理之后得到:

abca????
    ↑

这里用箭头标出的位置,即是 std::unique 的返回值所指向的位置。需要注意的是,经过 std::unique 处理之后,容器的实际大小没有发生改变,甚至逻辑尾后迭代器到容器实际尾后迭代器之间的左闭右开区间内的迭代器仍然是可解引用的(dereferenceable)。但这部分区间内的元素的值是不确定的。因此,在使用 std::unqiue 之后,往往会调用容器的 erase 函数成员,删除逻辑尾后迭代器开始的所有元素。例如:

// #include <string>
// #include <algorithm>
std::string source("aabbccaa");
source.erase(std::unique(source.begin(), source.end()), source.end());
std::cout << source << std::endl;  // expect result: abca

只对特定内容进行 std::unique 操作

回到最开始的问题。我们需要的功能,是针对分隔符 sep 进行操作,将连续出现的 sep 压缩成一个。 std::unique 的默认行为则不然,它会将所有连续出现的元素都压缩成一个——不光是 sep 。为此,我们需要实现自己的 BinaryPredicate 。首先,由于我们要指定具体需要被 std::unique 压缩的元素,我们必然要将其作为函数参数传入函数。于是我们有以下实现:

// #include <functional>
template <typename T>
bool AreConsecutiveElements(const T& target, const T& lhs, const T& rhs) {
  return (lhs == rhs) and (lhs == target);
}

std::unique 要求一个二元谓词( BinaryPredicate ),但此处我们实现的是三元谓词。于是,好在 target 总是应当预先给出的,所以我们可以利用 std::bindtarget 绑定在 AreConsecutiveElements 的第一个参数上,产生一个二元谓词。

// #include <functional>
// using namespace std::placeholders;
// #include <string>
// #include <algorithm>
const char target = 'b'
auto binp = std::bind(AreConsecutiveElements, target, _1, _2);
std::string source("aabbccaa");
source.erase(std::unique(source.begin(), source.end(), binp), source.end());
std::cout << source << std::endl;  // expect result: aabccaa

这里,我们将 'b' 作为压缩目标,并将其与 AreConsecutiveElements 绑定在一起,产生一个新的二元谓词。最终输出期待的结果。

附: std::unique 的一个可能实现

template<class ForwardIt, class BinaryPredicate>
ForwardIt unique(ForwardIt first, ForwardIt last, BinaryPredicate p) {
  if (first == last) {
    return last;
  }

  ForwardIt result = first;
  while (++first != last) {
    if (!p(*result, *first) && ++result != first) {
      *result = std::move(*first);
    }
  }
  return ++result;
}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

SNS浪潮

SNS浪潮

李翔昊 / 人民邮电出版社 / 2010 / 35.00元

内容提要: 本书通过互联网行业与社会生活中的案例内容,向读者介绍了一些互联网技术和新型网站的发展,揭示了社交网站兴起的因素。在探讨社交网站发展和网络开放平台的同时,也介绍、描述了其对社会信息传播、行业组织、广告营销等方面的影响。最后通过新技术和产品应用,展望了未来社会化网络的趋势走向。 本书适合从事信息技术、社会传播、市场营销相关工作,以及广大互联网用户,或对IT行业有兴趣的人士阅读。......一起来看看 《SNS浪潮》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换