首页 > 代码库 > 初识算法

初识算法

1.accumulate的用法:

 

int sum = accumulate(ivec.begin(), ivec.end(), 0 );

 


第三个参数时累加的初值,更重要的是accumulate对要累加元素的类型一无所知,所以容器内的类型要与第三个实参的类型匹配,或者可转换成第三个实参的类型。

 

 

2.find_first_of 的用法:

有两对迭代器参数来标记两段元素范围:在第一段范围内查找与第二段范围中任意元素匹配的元素,然后返回一个迭代器,指向第一个匹配的元素。如果找不到元素,则返回第一个范围的 end 迭代器。

 

// program for illustration purposes only:// there are much faster ways to solve this problemsize_t cnt = 0;list<string>::iterator it = roster1.begin();// look in roster1 for any name also in roster2while   ((it = find_first_of(it, roster1.end(),roster2.begin(), roster2.end()))                     != roster1.end()) {        ++cnt;        // we got a match, increment it to look in the rest of roster1        ++it;     }     cout << "Found " << cnt          << " names on both rosters" << endl;

 

 

 

这儿有点晕!@o@" 

while   ((it = find_first_of(it, roster1.end(),roster2.begin(), roster2.end())) != roster1.end())

 

 

在第一段范围内查找与第二段范围中任意元素匹配的元素,然后返回一个迭代器,指向第一个匹配的元素。如果找不到元素,则返回第一个范围的end ()迭代器。

 

调用 find_first_of 查找 roster2 中的每个元素是否与第一个范围内的元素匹配,也就是在 it 到 roster1.end() 范围内查找一个元素。

该函数返回此范围内第一个同时存在于第二个范围中的元素。

在 while 的第一次循环中,遍历整个 roster1 范围。第二次以及后续的循环迭代则只考虑 roster1 中尚未匹配的部分。

find_first_of(it, roster1.end(),roster2.begin(), roster2.end())

 

 

 

特别注意:

find_first_of 函数最容易出错的地方是和find函数搞混。它最大的区别就是如果在一个字符串str1中查找另一个字符串str2,如果str1中含有str2中的任何字符,则就会查找成功,而find则不同;

比如:

 string str1("I am change");string  str2("about");int k=str1.find_first_of(str2);    //k返回的值是about这5个字符中任何一个首次在str1中出现的位置;</span>

 

 

写容器元素的算法:

fill(vec.begin, vec.end, 10);

将由前两个参数确定的范围内的所有元素都设定为第三个形参给定的值。

fill_n(vec.begin, 10, 0);

由第一个参数起的范围内指定数目(第二个参数)内的所有元素都设定为第三个形参给定的值。(存在需写入的范围未定义情况,危险。)

 fill_n(back_inserter(vec), 10, 0);

 

 

vec调用back_inserter(),则fill_n每写入一个值,都会通过back_inserter()生成的插入迭代器实现。相当于在vec上调用push_back。

 

 

cope (ilst.begin(), ilst.end(), back_inserter(ivec));

 

//更好的方式是:
ivec(ilst.begin(), ilst.end());

 

copy从范围内读数据,再写入目标迭代器。

 


有些算法对输入序列元素做处理,但不该原来的元素,而是存储到新序列:

 

replace(ilst.begin(), ilst.end(), 0,42);

 

将指定范围内的指定的值(第三个参数)替换成指定值(第四个参数)

 

若不想改变原来的序列:

 

replace_copy (ilst.begin(), ilst.end(),back_inserter(ivec), 0, 42);

 

ilst没有改变,ivec存ilist的一份副本,ilist中所有0在ivec中都变成了42.

 

对容器元素重新排序的算法

待排序序列为:

the quick red fox jumps over the slow red turtle

 

sort(words.begin(), words.end());

 

sort算法两个迭代器实参指出了要排序的元素范围。这个算法使用<操作符比较元素。操作之后的序列为:

fox jumps over quick red red slow the the turtle

 

unique(words.begin(), words.end());

 

unique 算法带有两个指定元素范围的迭代器参数。该算法“删除”相邻的重复元素,然后重新排列输入范围内的元素,并且返回一个迭代器,表示无重复的值范围的结束。给“删除”加上引号是因为 unique 实际上并没有删除任何元素,而是将无重复的元素复制到序列的前端,从而覆盖相邻的重复元素。unique 返回的迭代器指向超出无重复的元素范围末端的下一位置。  

操作之后的序列为:

fox jumps over quick  red slow the turtle red the 

 

words.erase(end_unique,words.end());

 

若按照单词的长度排序:

 

stable_sort(words.begin(),words.end(),isShorter);

stable_sort的用法:

 

void stable_sort ( RandomAccessIterator first, RandomAccessIterator last,Compare comp );

 

 

 stable_sort 保存元素的相对顺序与等效值,在某个范围内依照comp的方法进行排序。

调用后,word中元素按长度大小排序,长度相同的单词仍保持字典顺序。

 

用于统计的函数:

 

vector<string>::size_type wc = count_if(words.begin(),words.end(),GT6);

 

第三个实参表示谓词函数,需要单个元素类型的实参,并返回一个可作条件检测的值。count_if返回的是使得谓词函数返回条件成立的元素个数。