13、C++ Primer 4th 笔记,泛型算法

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();
}

6C++提供了另外两种算法模式:一种模式由算法所带的形参定义,另一种模式则通过两种函数命名和重载的规范定义。

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/

上一篇:Kubernetes集群安全通信


下一篇:Java转行之路—《深入理解JAVA虚拟机总结》(一)