Learning boost 3 -- string algorithm 1

王朝other·作者佚名 2006-01-09

宽屏版字体: 小|中|大|超大

Learning boost 3

string algorithm 1

简介

string algorithm是boost中提供字符串算法的类库。在这里，字符串不一定是std::basic_string，也可以是其它的stl容器或是c++中的零结尾字符串char*。

例：

std::string str("Hello");

std::vector<char> vstr(str.begin(), str.end());

char *cstr=new char(str.size());

std::copy(str.begin(), str.end(), cstr);

boost::to_upper(str); //string

boost::to_upper(vstr); //vector<char>

boost::to_upper(cstr); //char*

另外，在string algorithm中的很多算法都分为mutable 和copy，mutable算法直接修改输入的字符串，而copy算法返回一个新的字符串或通过一个迭代器输出。

在string algorithm中碰到一个IteratorRange的概念，这是boost::range中的一个类，我也不会使用，不过可以使用make_iterator_range(iterator, iterator)来构造。iterator_range通过两个开始和结束迭代器表示一段范围，一般通过查找算法的返回来得到。

例：

std::string str1("Hello");

std::string str2("Hello");

boost::to_upper(str1);//mutable algorithm，现在str1==”HELLO”

std::string str3=boost::to_upper_copy(str2);//copy algorithm, str3==”HELLO”

char * p =boost::to_upper_copy("Hello");

这是错的。因为to_upper_copy不会去申请一段内存保存"Hello"的拷贝。

char str[]={"Hello"};

to_upper(str);这样这就可以了。

std::string str4;

boost::to_upper_copy(std::back_inserter(str4),

std::make_pair(str2.begin(), str2.end())

);//使用迭代器的copy algorithm, str4==”HELLO”

//这里注意，这里和stl不同的是输出迭代器在输入迭代器的前面

boost::to_upper_copy(std::back_inserter(str4), "Hello");str4==”HELLOHELLO”

//这也是可以的，前面说过了IteratorRange相当于一个容器，

//stl标准容器，std::basic_string 和char*都可以作为string_algorithm中的容器

Case Conversion Algorithm 大小写转换算法

void to_lower(MutableCollection&, std::local&=std::local());

void to_upper(MutableCollection&, std::local&=std::local());

Sequence to_lower_copy(const Sequence&, std::local&=std::local());

Sequence to_upper_copy(const Sequence&, std::local&=std::local());

OutputIterator to_lower_copy(OutputIterator, const Collection&, std::local&=std::local());

在string algorithm中，Collection指：

l stl标准类型

l 内建数组(如：int[])

l 零结尾字符串(char*或wchar *)

l pair<iterator, iterator>

MutableCollection当然是指非const 的collection。

Sequence好像只能是标准容器。

Trim Algorithm Trim算法

void trim (Sequence&, std::local&=std::local());

void trim_left (Sequence&, std::local&=std::local());

void trim_right (Sequence&, std::local&=std::local());

Sequence trim_copy (const Sequence&, std::local&=std::local());

Sequence trim_left_copy (const Sequence&, std::local&=std::local());

Sequence trim_right_copy (const Sequence&, std::local&=std::local());

上述算法删除字符串中左右（或是其中之一）的空格。

void trim_if (Sequence&, Predicate);

void trim_left_if (Sequence&, Predicate);

void trim_right_if(Sequence&, Predicate);

Sequence trim_copy_if (const Sequence&, Predicate);

Sequence trim_left_copy_if (const Sequence&, Predicate);

Sequence trim_right_copy_if(const Sequence&, Predicate);

OutputIterator trim_copy_if (OutputIterator, const Collection&, Predicate);

OutputIterator trim_left_copy_if (OutputIterator, const Collection&, Predicate);

OutputIterator trim_right_copy_if(OutputIterator, const Collection&, Predicate);

上述算法删除字符串左右（或是其中之一）满足Predicate的字符。

Predicate是一个一元判断式。

例：

string str(“---Hello---”);

boost::trim_if(str, bind2nd(equal_to<char>(), ’-‘));//str==”Hello”

Predicate 判断式

string algorithm中提供了一些与字符串相关的判断式。

bool starts_with (Input, Test);

bool starts_with (Input, Test, Comp)

bool istarts_with(Input, Test, Local)

判断Input是否以Test开头。Comp是比较字符的二元判断式。Local是std::local。

bool ends_with (Input, Test);

bool ends_with (Input, Test, Comp)

bool iends_with(Input, Test, Local)

判断Input是否以Test结尾。Comp是比较字符的二元判断式。Local是std::local。

bool contains (Input, Test);

bool contains (Input, Test, Comp)

bool icontains(Input, Test, Local)

判断Input是否包含Test。Comp是比较字符的二元判断式。Local是std::local。

bool equals (Input, Test);

bool equals (Input, Test, Comp)

bool iequals(Input, Test, Local)

判断Input是否和Test相同。Comp是比较字符的二元判断式。Local是std::local。

bool all(Input, Pred);

判断Input的每一个字符是否满足Pred判断式。

Classfication 类别判断式

classfication也是判断式，它们是对std::isspace等函数的泛型化封装。

unspecified is_classified(std::ctype_base::mask, const std::locale & = std::locale());

unspecified is_space (const std::locale & = std::locale());

unspecified is_alnum (const std::locale & = std::locale());

unspecified is_alpha (const std::locale & = std::locale());

unspecified is_cntrl (const std::locale & = std::locale());

unspecified is_digit (const std::locale & = std::locale());

unspecified is_graph (const std::locale & = std::locale());

unspecified is_lower (const std::locale & = std::locale());

unspecified is_print (const std::locale & = std::locale());

unspecified is_punct (const std::locale & = std::locale());

unspecified is_upper (const std::locale & = std::locale());

unspecified is_xdigit (const std::locale & = std::locale());

判断字符是否是某个类型，返回判断式。

例：

trim_copy_if(string(“123Hello890”, is_digit()));//return “Hello”

unspecified is_any_of(Set);

判断字符是否是Set中的一个，返回判断式。

unspecified is_from_range(From, To);

判断字符是否是否处在From和To之间(From<=Ch<=To)。

unspecified operator&&(Pred1, Pred2);

unspecified operator||(Pred1, Pred2);

unspecified operator!(Pred);

classfication判断式的与或非运算。注意：只能对上述的classfication判断式使用。

例：

trim_copy_if(string(“123Hello890”), is_digit()||is_upper());//return “ello”

iterator_range Class 迭代器范围类

iterator_range是对一组迭代器的封装。一般用于find算法的返回值。

iterator_range有类似于stl容器的begin(), end(), empty(), size(), swap(), bool operator()成员函数。

一般使用make_iterator_range()来构造iterator_rang，make_iterator_range使用两个迭代器或者是pair<iterator, iterator>作为参数。

还可以使用流来输出iterator_range。

例：

string str(“Hello”);

cout<<make_iterator_range(str.begin()+1, str.end()-1);//output “ell”

对于iterator_range的ostream输出类似于 copy(it.begin(),it.end(),ostream_iterator<char>(“”));

无空格的连续输出。

Erase Algorithm 删除算法

OutputIterator erase_range_copy (OutputIterator, Input, SearchRange);

Sequence erase_range_copy (Input, SearchRange);

void erase_range (Input, SearchRange);

删除输入字符串中SearchRange那部分。SearchRange是一个iterator_range对象。

例：

std::string str1("Hello");

std::string str2;

boost::erase_range(str1, boost::make_iterator_range(str1.begin()+1, str1.end()-1));

cout<<str1<<endl;//输出”Ho”

erase_range_copy(back_inserter(str2),

str1,

boost::make_iterator_range(str1.begin()+1, str1.end()-1));

cout<<str2<<endl;//输出”Ho”

OutputIterator erase_first_copy(OutputIterator, Input, Search);

Sequence erase_first_copy(Input, Search);

void erase_first (Input, Search);

OutputIterator ierase_first_copy(OutputIterator, Input, Search, Local);

Sequence ierase_first_copy(Input, Search, Local);

void ierase_first (Input, Search, Local);

删除从Input中查找到的第一个Search。

例：

std::string str1("Hello");

std::string str2;

boost::erase_first(str1, "ll");

str2=boost::erase_first_copy(string("Hello"), "l");

cout<<str1<<endl;//输出”Heo”

cout<<str2<<endl;//输出”Helo”

OutputIterator erase_last_copy(OutputIterator, Input, Search);

Sequence erase_last_copy(Input, Search);

void erase_last (Input, Search);

OutputIterator ierase_last_copy(OutputIterator, Input, Search, Local);

Sequence ierase_last_copy(Input, Search, Local);

void ierase_last (Input, Search, Local);

删除从Input中查找到的最后一个Search。

OutputIterator erase_nth_copy(OutputIterator, Input, Search, n);

Sequence erase_nth_copy(Input, Search, n);

void erase_nth (Input, Search, n);

OutputIterator ierase_nth_copy(OutputIterator, Input, Search, n, Local);

Sequence ierase_nth_copy(Input, Search, n, Local);

void ierase_nth (Input, Search, n, Local);

删除从Input中查找到的第n个Search。（n是基于0的）

OutputIterator erase_all_copy(OutputIterator, Input, Search);

Sequence erase_all_copy(Input, Search);

void erase_all (Input, Search);

OutputIterator ierase_all_copy(OutputIterator, Input, Search, Local);

Sequence ierase_all_copy(Input, Search, Local);

void ierase_all (Input, Search, Local);

删除从Input中查找到的所有Search。

OutputIterator erase_head_copy (OutputIterator, Input, n);

Sequence erase_head_copy (Input, n);

void erase_head (Input, n)

删除Input的前n个字符。如果n大于输入字符串长度，那么整个字符串会被删除。

OutputIterator erase_tail_copy (OutputIterator, Input, n);

Sequence erase_tail_copy (Input, n);

void erase_tail (Input, n);

删除Input的最后n个字符。如果n大于输入字符串长度，那么整个字符串会被删除。

Replace Algorithm 替换算法

OutputIterator replace_range_copy (OutputIterator, Input, SearchRange, Format);

Sequence replace_range_copy (Input, SearchRange, Format);

void replace_range (Input, SearchRange, Format);

把Input中的SearchRange部分替换成Format。

OutputIterator replace_first_copy (OutputIterator, Input, Search, Format);

Sequence replace_first_copy (Input, Search, Format);

void replace_first (Input, Search, Format);

OutputIterator ireplace_first_copy (OutputIterator, Input, Search, Format, Local);

Sequence ireplace_first_copy (Input, Search, Format, Local);

void ireplace_first (Input, Search, Format, Local);

把Input中搜索到的第一个Search替换成Format。

OutputIterator replace_last_copy (OutputIterator, Input, Search, Format);

Sequence replace_last_copy (Input, Search, Format);

void replace_last (Input, Search, Format);

OutputIterator ireplace_last_copy (OutputIterator, Input, Search, Format, Local);

Sequence ireplace_last_copy (Input, Search, Format, Local);

void ireplace_last (Input, Search, Format, Local);

把Input中搜索到的最后一个Search替换成Format。

OutputIterator replace_nth_copy (OutputIterator, Input, Search, Format, n);

Sequence replace_nth_copy (Input, Search, Format, n);

void replace_nth (Input, Search, Format, n);

OutputIterator ireplace_nth_copy (OutputIterator, Input, Search, Format, n, Local);

Sequence ireplace_nth_copy (Input, Search, Format, n, Local);

void ireplace_nth (Input, Search, Format, n, Local);

把Input中搜索到的第n个Search替换成Format。

OutputIterator replace_all_copy (OutputIterator, Input, Search, Format);

Sequence replace_all_copy (Input, Search, Format);

void replace_all (Input, Search, Format);

OutputIterator ireplace_all_copy (OutputIterator, Input, Search, Format, Local);

Sequence ireplace_all_copy (Input, Search, Format, Local);

void ireplace_all (Input, Search, Format, Local);

把Input中所有的Search替换成Format。

OutputIterator replace_head_copy(OutputIterator, Input, n, Format);

Sequence replace_head_copy(Input, n, Format);

void replace_head (Input, n, Format);

把Input中前n个字符替换成Format。

OutputIterator replace_tail_copy(OutputIterator, Input, n, Format);

Sequence replace_tail_copy(Input, n, Format);

void replace_tail (Input, n, Format);

把Input中最后n个字符替换成Format。

Finder Object Finder仿函数

Finder Object是一个仿函数，它用来决定在find算法中的匹配策略。可以在find_iterator中使用。

Finder first_finder(Search);

Finder first_finder(Search, Comp);

返回在输入中查找第一个Search的Finder对象。

Finder last_finder(Search);

Finder last_finder(Search, Comp);

返回在输入中查找最后一个Search的Finder对象。

Finder nth_finder(Search, n);

Finder nth_finder(Search, n, Comp);

返回在输入中查找第一个Search的Finder对象。

Finder head_finder(n);

Finder tail_finder(n);

返回在输入中查找最前（后）n个字符的Finder对象。（n是基于0的）

Finder token_finder(Pred, Compress= token_compress_off);

返回满足Pred判断式的字符的查找的Finder对象。

Pred 是类似于bool pred(char c);这样的函数或仿函数。

Compress可以取值为：

token_compress_on :将相邻的满足Pred的字符合并作为查找结果。

token_compress_off:不合并相邻的字符。

例如：对于bind2nd(equal_to<char>,’c’)这样的判断式，用token_finder查找”aabbcc”，对于token_compress_on结果是”cc”，对于token_compress_off是分别查找到两个”c”。

Finder range_finder(beg, end);

Finder range_finder(iterator_range);

返回查找特定范围的Finder对象。

Find算法

Find算法是在字符串中查找子串的算法，算法返回iterator_range类型。

iterator_range find(Input, Finder);

iterator_range find_first(Input, Search);

iterator_range ifind_first(Input, Search,Local=std::local());

iterator_range find_last(Input, Search);

iterator_range ifind_last(Input, Search, Local=std::local());

iterator_range find_nth(Input, Search, n);

iterator_range ifind_nth(Input, Search, n, Local=std::local());

iterator_range find_head(Input, n);

iterator_range find_tail(Input, n);

iterator_range find_token(Input, Pred, Compress= token_compress_off);

上述的算法都很简单，我就不多说了。

我来分析一下find_first，find_first的源代码是这样的：

template<typename Collection1T, typename Collection2T>

inline iterator_range<

BOOST_STRING_TYPENAME result_iterator_of<Collection1T>::type>

find_first(

Collection1T& Input,

const Collection2T& Search)

{

return first_finder(Search)(

begin(Input),end(Input));

}

result_iterator_of<Collection1T>::type是Collection1T::iterator

begin(Input)是Input.begin()

end(Input)是Input.end()

first_finder(Search)返回一个first_finder对象，然后调用这个Finder.operator()(beg,end)，并且以iterator_range作为查找结果返回。其实对于每一个Finder都重载了operator()函数，使用这个函数就可以对字符串直接查找。

Find Iterator 查找迭代器

find算法只能查找到一个结果，而通过find_iterator可以查找所有的结果。

template<typename Iterator> class find_iterator;

find_iterator make_find_iterator(Input, Finder);

find_iterator的成员函数：

find_iterator()默认构造函数

find_iterator(beg, end, Finder)在beg和end之间查找

find_iterator(Input, Finder)查找Input

bool eof()是否查找结束

例：

std::string str1("ten 10 nine 9 and eight 8");

boost::find_iterator<string::iterator> it;

for (it = make_find_iterator(str1,

token_finder(boost::is_digit(),

boost::token_compress_on)//查找连续数字的token_finder

)

;!it.eof();++it)//注意是it.eof()，it->意味着(*it). 而*it是一个iterator_range对象

cout<<*it<<endl;//*it返回查找结果：一个iterator_range对象，而一个iterator_range是可以直接输出的。

//输出：

//10

//9

//8

在使用find_iterator的过程中，不能修改字符串的长度，例如：erase_range(str1,*it)如果是replace就可以。

另外，find_iterator是Forward迭代器，不能--it。

template<typename Iterator> class split_iterator;

find_iterator make_split_iterator(Input, Finder);

split_iterator使用查找到的字串来分隔字符串，例如对于上述例子，用split替换find，结果是：

ten

nine

and eight

splite_iterator的其它用法和find_iterator一样。