Effective STL - 04 - Algorithms

Algorithms

条款30：确保目标区间足够大

vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7};
cout << v << endl;

// 对于使用区间的函数, 注意预先分配空间
vector<int> v2;
v2.reserve(v.size());
transform(v.begin(), v.end(), back_inserter(v2), [] (int& a) {
    return a * 2;
});
cout << v2 << endl;

v2.reserve(v.size() * 2);
transform(v.begin(), v.end(), back_inserter(v2), 
    bind(multiplies<int>(), placeholders::_1, 2));
cout << v2 << endl;

注意：back_inserter 会调用 push_back ，所以只能用于标准序列容器，即 vector、list、deque、string。（array 的迭代器没有 insert 方法，因此不能使用）

无论何时你使用一个要求指定目的区间的算法，确保目的区间已经足够大或者在算法执行时可以增加大小（array就不能增加大小）。如果你选择增加大小，就使用插入迭代器，比如ostream_iterators或从back_inserter、front_inserter或inserter返回的迭代器。这是所有你需要记住的东西。

条款31：了解你的排序选择

我们总结一下你的排序选择：

如果你需要在vector、string、deque或数组上进行完全排序，你可以使用sort或stable_sort。
如果你有一个vector、string、deque或数组，你只需要排序前n个元素，应该用partial_sort。
如果你有一个vector、string、deque或数组，你需要鉴别出第n个元素或你需要鉴别出最前的n个元素，而不用知道它们的顺序，nth_element是你应该注意和调用的。
如果你需要把标准序列容器的元素或数组分隔为满足和不满足某个标准，你大概就要找partition或stable_partition。
如果你的数据是在list中，你可以直接使用partition和stable_partition，你可以使用list的sort来代替sort和stable_sort。如果你需要partial_sort或nth_element提供的效果，你就必须间接完成这个任务，但正如我在上面勾画的，会有很多选择。

下面是使用 partition 实现快排的算法：

void qsort(vector<int>& v, int begin, int end) {
  if (begin >= end - 1)  return;

  // partition 的任务: 找到 pivot 的 upperBound
  int pivot = v[begin];
  auto it = partition(v.begin() + begin, v.begin() + end, [&pivot] (int& i) {
      return i <= pivot;
  });

  // 更新 pivot 的位置
  swap(*(v.begin() + begin), *(--it));
  qsort(v, begin, it - v.begin());
  qsort(v, it - v.begin() + 1, end);
}

template <typename RndIt>
void qsort(const RndIt& begin, const RndIt& end) {
    if (begin >= end - 1)  return;

    auto it = partition(begin, end, 
        bind(less_equal<typename RndIt::value_type>(), placeholders::_1, *begin));
    swap(*begin, *(--it));
    qsort(begin, it);
    qsort(it + 1, end);
}

条款32：如果你真的想删除东西的话就在类似remove的算法后接上erase

remove并不“真的”删除东西，因为它做不到。只有容器成员函数可以除去容器元素，而那是本条款的整个要点：如果你真的要删除东西的话，你应该在remove后面接上erase。

remove移动指定区间中的元素直到所有“不删除的”元素在区间的开头（相对位置和原来它们的一样）。它返回一个指向最后一个的下一个“不删除的”元素的迭代器。返回值是区间的“新逻辑终点”。remove 不会保留所有值，因为那些值是不必要的了。（所以不能使用 remove_if 对数组进行排序）

你要记住的唯一其他的东西是remove不是唯一这种情况的算法。另外有两种“类似remove”的算法：remove_if和unique。remove和remove_if之间的相似性很直截了当。所以我不会细讲，但unique行为也像remove。它用来从一个区间删除东西（邻近的重复值）而不用访问持有区间元素的容器。unique 应该就类似 np.unique ，用于保留一份拷贝。

条款33：提防在指针的容器上使用类似remove的算法

因为一旦指针被替换，内存就泄露了。可以使用智能指针，能够实现自由释放内存。

vector<unique_ptr<int>> v;

const int size = 100'000;
v.reserve(size);
for (int i = 0; i < size; i++)  v.push_back(make_unique<int>(i));

v.erase(remove_if(v.begin(), v.end(), [] (auto& elm) {
    return *elm < 30;
}), v.end());

条款34：注意哪个算法需要有序区间

我知道你们中的一部分会用蛮力记忆，所以这里有一个只能操作有序数据的算法的表：

binary_search	lower_bound
upper_bound	equal_range
set_union	set_intersection
set_difference	set_symmetric_difference
merge	inplace_merge
includes

另外，下面的算法一般用于有序区间，虽然它们不要求：

unique	unique_copy

搜索算法binary_search、lower_bound、upper_bound和equal_range（参见条款45）需要有序区间，因为它们使用二分法查找来搜索值。像C库中的bsearch，这些算法保证了对数时间的查找，但作为交换的是，你必须给它们已经排过序的值。实际上，这些算法保证对数时间查找不是很正确。仅当传给它们的是随机访问迭代器时它们才能保证有那样的性能。如果给它们威力比较小的迭代器（比如双向迭代器），它们仍然进行对数次比较，但运行是线性时间的。那是因为，缺乏进行“迭代器算术（arithmetic）”的能力。它们在搜索的区间中需要花费线性时间来从一个地方移动到另一个地方。

算法set_union（交集）、set_intersection（并集）、set_difference（异或）和set_symmetric_difference（同或）的四人组提供了线性时间设置它们名字所提出的操作的性能。为什么它们需要有序区间？因为如果不是的话，它们不能以线性时间完成它们的工作。如果你开始发觉一个趋势——需要有序区间的算法为了比它们用于可能无序区间提供更好的性能而这么做，你是对的。

merge和inplace_merge执行了有效的单遍合并排序算法：它们读取两个有序区间，然后产生一个包含了两个源区间所有元素的新有序区间。它们以线性时间执行，如果它们不知道源区间已经有序就不能完成。

vector<int> mergeSort(vector<int>& v, int begin, int end) {
    if (begin >= end - 1)  return vector<int> {v.begin() + begin, v.begin() + end};

    int mid = begin + ((end - begin) >> 1);
    auto left = mergeSort(v, begin, mid);
    auto right = mergeSort(v, mid, end);

    vector<int> result;
    result.reserve(end - begin);
    merge(left.begin(), left.end(), right.begin(), right.end(), back_inserter(result));

    return result;
}

最后一个需要有序区间的算法是includes。它用来检测是否一个区间的所有对象也在另一个区间中。因为includes可能假设它的两个区间都已经有序，所以它保证了线性时间性能。没有那个保证，一般来说它会变慢。

条款35：通过mismatch或lexicographical比较实现简单的忽略大小写字符串比较

使用 tolower 可以将字符串全部变成小写。

int ciCharCompare(char c1, char c2) {
    c1 = tolower(static_cast<unsigned char>(c1));
    c2 = tolower(static_cast<unsigned char>(c2));

    return c1 > c2 ? 1 : c1 < c2 ? -1 : 0;
}

// 使用 mismatch 对字符串进行匹配
int ciMismatchCompareImpl(const string& s1, const string& s2) {
    // bind 修改  最后一个函数的意义, 当字符相等时返回 true, 不等时返回 false
    auto it = mismatch(s1.begin(), s1.end(), s2.begin(), s2.end(), 
        bind([] (auto& c1, auto& c2) {
            return ciCharCompare(c1, c2) == 0;
        }, placeholders::_1, placeholders::_2));
    if (it.first == s1.end()) {
        // s1 是短字符串, 因此当短字符串结束后, 长字符串还没有结束
        // 说明 s1 < s2, 否则二者相等
        if (it.second == s2.end())  return 0;
        else  return -1;
    } else {
        // 二者均没有到达结尾时, 由不相等字符决定
        return ciCharCompare(*it.first, *it.second);
    }
}

int ciMismatchCompare(const string& s1, const string& s2) {
    if (s1.size() >= s2.size())  return -ciMismatchCompareImpl(s2, s1);
    else  return ciMismatchCompareImpl(s1, s2);
}

bool ciLexicographicalCompare(const string& s1, const string& s2) {
    return lexicographical_compare(s1.begin(), s1.end(), 
        s2.begin(), s2.end(),
        [] (auto& c1, auto& c2) {
            return tolower(c1) < tolower(c2);
        });
}

条款36：了解copy_if的正确实现

目前 MSVC 已经有了 copy_if 的实现了：

template <class _InIt, class _OutIt, class _Pr>
_CONSTEXPR20 _OutIt copy_if(_InIt _First, _InIt _Last, _OutIt _Dest, _Pr _Pred) { // copy each satisfying _Pred
    _Adl_verify_range(_First, _Last);
    auto _UFirst      = _Get_unwrapped(_First);
    const auto _ULast = _Get_unwrapped(_Last);
    auto _UDest       = _Get_unwrapped_unverified(_Dest);
    for (; _UFirst != _ULast; ++_UFirst) {
        if (_Pred(*_UFirst)) {
            *_UDest = *_UFirst;
            ++_UDest;
        }
    }

    _Seek_wrapped(_Dest, _UDest);
    return _Dest;
}

STL有很多有趣的地方，其中一个是虽然有11个名字带“copy”的算法：

copy	copy_backward
replace_copy	reverse_copy
replace_copy_if	unique_copy
remove_copy	rotate_copy
remove_copy_if	partial_sort_copy
unintialized_copy

条款37：用accumulate或for_each来统计区间

cout << accumulate(v.begin(), v.end(), 0) << endl;

vector<Point<float>> vp = {{0.0f, 0.1f}, {1.3f, 4.2f}, {3.6f, 9.1f}};
cout << accumulate(vp.begin(), vp.end(), Point<float>{0.0f, 0.0f}, [] (auto& v, auto& res) {
    return Point<float>{v.x + res.x, v.y + res.y};
}) / float(vp.size()) << endl;

Point<float> startValue{0.0f, 0.0f};
for_each(vp.begin(), vp.end(), [&startValue] (auto& p) {
    startValue += p;
});
cout << startValue / float(vp.size()) << endl;

accumulate 返回的是容器的元素，for_each 返回的是 lambda 或者仿函数对象。

Effective STL

#C++ #STL #Algorithms

Effective STL - 04 - Algorithms

http://hebangwen.github.io/2024/03/17/Algorithms/

作者

何榜文

发布于

2024年3月17日

许可协议

Effective STL - 05 - Functor 上一篇

Effective STL - 03 - Iterator 下一篇