C++中泛型算法详解1:只读算法、读写算法、重排容器元素的算法

简介

标准库提供了超过100个算法,这些算法有一致的结构。

理解这些算法的基本方法是了解他们是否读取元素、改变元素或者重排元素顺序。

泛型算法特点:

  • 算法不依赖容器所保存的元素类型。 只要有迭代器能够访问元素即可。
  • 大多数算法都会使用一个或多个元素上的操作,通常,我们可以使用自定义的操作来代替默认的运算符。
  • 算法本身永远不会执行容器上的操作,只是运行在迭代器上,执行迭代器的操作。

1. 只读算法

// find
    vector<int> vv{2,3,4,6,6,3,2,8,9,6,6,6,6,6};
    auto x = std::find(vv.cbegin(), vv.cend(), 6);
    
// count
    string ss{"asdfasdfasdfaasdfasdfs"};
    cout << count(ss.cbegin(), ss.cend(), 'a') << endl;
    
// accumulate
	cout << accumulate(vv.cbegin(), vv.cend(), 0) << endl;

// equal
	equal(vv2.cbegin(), vv2.cend(), vv.cbegin());

注意:

  1. accumulate的第三个参数类型决定函数使用哪个加法运算符以及返回值的类型。所以需要对应的数据类型定义了“+”运算符
  2. 对于只读算法,最好使用cbegin()cend()传入迭代器的范围
  3. equal接受三个迭代器,它假设第二的序列(第三个参数)要比第一个序列长。对应的元素类型需要可以用==符号做比较
  4. accumulate的头文件是numeric

2. 写容器的算法

// fill: 双迭代器 + 数值
    fill(vv.begin(), vv.begin() + vv.size()/2, 10);

// fill_n: 使用一个迭代器 + 长度 + 数值
	fill_n(vv.begin(), vv.size(), 2);

// copy: 接受三个迭代器
// 返回ret指向拷贝vv2到vv后的尾元素之后的位置
    auto ret = copy(vv2.begin(), vv2.begin()+vv2.size()/2, vv.begin());

// replace:双迭代器,被替换的数值,替换的值
	replace(vv2.begin(), vv2.end(), 2, 100);

// replace_copy:如果不想改变原来的容器, 将会把替换之后的v放在ivec容器中
    vector<int> ivec;
    replace_copy(vv2.begin(), vv2.end(), back_inserter(ivec), 100, 50);

注意

  1. 向目的位置迭代器写入数据的算法,比如fill,都是假定对应容器足够大,能够放下要写入的元素。
  2. 不要在空容器上调用fill_n(原因和1其实相同)

3. 重排容器元素的算法

// sort
    std::sort(vs.begin(), vs.end());

// unique: 如果希望每个元素只保存一次的话。 算法重排输入序列,将相邻的重复项消除,返回一个指向不重复范围末尾的迭代器。
    auto new_end = std::unique(vs.begin(), vs.end());

// 但是vs的大小没有改变,只是覆盖重复元素
// 想要真正删除的话:使用容器的erase函数
    vs.erase(new_end, vs.end());

注意:

  1. sort使用元素类型的<运算符实现排序
上一篇:于Kafka和Elasticsearch构建实时站内搜索功能的实践


下一篇:PAT 甲级 1006 Sign In and Sign Out 字符串