1、泛型,指的是他们可以操作在多种容器类型上-不但可作用于 vector 或 list这些标准库类型,还可用在内置数组类型、甚至其他类型的序列上。自定义的容器类型只要与标准库兼容,同样可以使用这些泛型算法。
2、在这里讨论的迭代器范围一般为[begin, end)这种左闭包形式。
3、算法基于迭代器实现及其操作实现。算法从不直接改变它所操作的序列的大小;如果算法的实参是插入迭代器,则该迭代器会添加新元素,但算法并不直接这么做;如果需要添加或删除元素,则必须使用容器操作。理解算法的最基本方法是了解该算法是否读元素,写元素,或者对元素进行重新排序。
4、初学者常犯的错误是:在没有元素的容器上调用fill_n函数。
5、谓词(Predicate)其返回类型可转换为bool值的函数,有一元谓词和二元谓词。
bool isShorter(const string &s1, const string &s2)
{
return s1.size() < s2.size();
}
6、C++提供了另外两种算法模式:一种模式由算法所带的形参定义,另一种模式则通过两种函数命名和重载的规范定义。
1)算法的形参模式
alg (beg, end, other parms); alg (beg, end, dest, other parms); alg (beg, end, beg2, other parms); alg (beg, end, beg2, end2, other parms);
调用这些算法时,必须确保输出容器有足够大的容量存储输出数据。如果dest 是容器上的迭代器,则算法将输出内容写到容器中已存在的元素上。更普遍的用法是,将 dest 与某个插入迭代器或者ostream_iterator 绑定在一起。插入迭代器在容器中添加元素,以确保容器有足够的空间存储输出。ostream_iterator 则实现写输出流的功能,无需要考虑所写的元素个数。
与写入 dest 的算法一样,只带有 beg2 的算法也假定以 beg2开始的序列与 beg 和 end 标记的序列一样大。
2)命名规范
有两种重要模式:一种是包括测试输入范围内元素的算法;二种算法则应用于对输入范围内元素重新排序的算法。
(1)区别带有一个值或一个谓词函数参数的算法版本
sort (beg, end); // use < operator to sort the elements sort (beg, end, comp); // use function named comp to sort the elements find(beg, end, val); // find first instance of val in the input range find_if(beg, end, pred); // find first instance for which pred is true
带有谓词函数形参的算法,其名字带有后缀_if。
(2)区别是否实现复制的算法版本
reverse(beg, end); reverse_copy(beg, end, dest);
7、因为string标准库为string对象与char*对象定义了相等(==)操作符。
8、容器特有的算法
由于list容器不支持随机访问,因此,在此容器上不能使用需要随机访问迭代器的算法。包括sort等。还有一些其他的泛型算法,如merge,remove,reverse, unique,虽然可以用有list上,但是却付出了性能上的代价。
标准库为list容器定义了更精细化的操作集合。使它不必只依赖于泛型操作。如下表示其中不包括要求支持双向或更弱的迭代器类型的泛型算法,这类泛型算法无论是用在list 容器上,还是用在其他容器上,都具有相同的效果。
lst.merge(lst2) lst.merge(lst2, comp) |
将 lst2 的元素合并到 lst 中。这两个 list 容器对象都必须排序。lst2 中的元素将被删除。合并后,lst2 为空。返回 void 类型。第一个版本使用 < 操作符,而第二个版本则使用 comp 指定的比较运算 |
lst.remove(val) lst.remove_if(unaryPred) |
调用 lst.erase 删除所有等于指定值或使指定的谓词函数返回非零值的元素。返回 void 类型 |
lst.reverse() |
反向排列 lst 中的元素 |
lst.sort |
对 lst 中的元素排序 |
lst.splice(iter, lst2) lst.splice(iter, lst2, iter2) lst.splice(iter, beg, end) |
将 lst2 的元素移到 lst 中迭代器 iter 指向的元素前面。在 lst2 中删除移出的元素。第一个版本将 lst2 的所有元素移到 lst 中;合并后,lst2 为空。lst 和 lst2 不能是同一个 list 对象。第二个版本只移动 iter2 所指向的元素,这个元素必须是 lst2 中的元素。在这种情况中,lst 和lst2 可以是同一个 list 对象。也就是说,可在一个 list对象中使用 splice 运算移动一个元素。第三个版本移动迭代器 beg 和 end 标记的范围内的元素。beg 和 end 照例必须指定一个有效的范围。这两个迭代器可标记任意 list 对象内的范围,包括 lst。当它们指定 lst 的一段范围时,如果 iter 也指向这个范围的一个元素,则该运算未定义。 |
lst.unique() lst.unique(binaryPred) |
调用 erase 删除同一个值的连续副本。第一个版本使用 ==操作符判断元素是否相等;第二个版本则使用指定的谓词函数实现判断 |
对于list对象,应该优先使用list容器特有的成员版本。与对应的泛型算法不同,list容器特有的操作能添加和删除元素。
参考:
[1] http://blog.163.com/zhoumhan_0351/blog/static/39954227201031310142987/
[2] http://blog.163.com/zhoumhan_0351/blog/static/39954227201031311555313/
[3] http://blog.163.com/zhoumhan_0351/blog/static/39954227201031403432544/
[4] 非变易算法
http://blog.163.com/zhoumhan_0351/blog/static/39954227201031222036600/
http://blog.163.com/zhoumhan_0351/blog/static/3995422720103123710779/
[5] 排序算法
http://blog.163.com/zhoumhan_0351/blog/static/39954227201031435744597/
http://blog.163.com/zhoumhan_0351/blog/static/39954227201031411838579/
http://blog.163.com/zhoumhan_0351/blog/static/3995422720103151446580/
[6] http://blog.163.com/zhoumhan_0351/blog/static/3995422720103174417603/
[7] http://blog.163.com/zhoumhan_0351/blog/static/399542272010315113015869/
[8] list容器
http://blog.163.com/zhoumhan_0351/blog/static/3995422720103671315851/