C++初学者指南-5.标准库(第一部分)--容器遍历

C++初学者指南-5.标准库(第一部分)–容器遍历

• 尝试只在你想做的事情没有经过良好测试的(标准)库函数/算法的情况下编写循环!
• 对于像std::vector这样的序列容器，首选非随机线性前向遍历，这得益于对缓存和预取的友好性
• 只有一些标准容器支持反向遍历

前向遍历

基于范围的循环

for (type variable : container)

• 适用于所有标准序列和关联式容器
• 与容器无关⇒易于更改容器类型
• 没有可能发生越界访问错误
• 无需担心有符号/无符号的索引类型问题
• 由于线性存取模式，使用序列容器时性能最佳 （缓存和预取友好）
• 可以用break实现早期退出；
• 不适合需要随机访问模式的算法

std::vector<Type> v { … };
// 只读，类型的复制成本较低或者需要复制：
for (Type x : v) { cout << x; }
for (auto x : v) { cout << x; }
// 只读，类型复制的成本很高时：
for (Type const& x : v) { cout << x; }
for (auto const& x : v) { cout << x; }
// 修改值时：
for (Type& x : v) { cin >> x; }
for (auto& x : v) { cin >> x; }

for_each / for_each_n

• 如果你已经有一个可以应用于每个元素的函数(对象)，那会比较方便。
• 适用于所有标准序列和关联容器。
• 与容器无关⇒易于更改容器类型。
• 无需担心有符号/无符号索引类型的麻烦。
• 自说明性名称。
• 使用迭代器范围可能存在越界访问错误。

不可能发生越界访问
cppreference

#include <algorithm>  // std::ranges::for_each
namespace ranges = std::ranges;  // alias
Container<Type> v; …
// 只读，类型的复制成本较低或者需要复制：
ranges::for_each(v, [](Type x){ cout << x; }); 
ranges::for_each(v, [](auto x){ cout << x; });
// 只读，类型复制的成本很高时：
ranges::for_each(v, [](Type const& x){ cout << x; });
ranges::for_each(v, [](auto const& x){ cout << x; });
// 修改值时:
ranges::for_each(v, [](Type& x){ cin >> x; });
ranges::for_each(v, [](auto& x){ cin >> x; });

• 可用于子范围
• 可能存在越界访问漏洞
  cppreference

#include <algorithm>  // std::for_each
Container<Type> v; …
// 只读，类型的复制成本较低或者需要复制：
for_each(begin(v), end(v),       [](Type x){ cout << x; });
for_each(begin(v)+2, begin(v)+5, [](auto x){ cout << x; });
// 只读，类型复制的成本很高时：
for_each(begin(v), end(v), [](Type const& x){ cout << x; });
for_each(begin(v), end(v), [](auto const& x){ cout << x; });
//修改值时:
for_each(begin(v), end(v), [](Type& x){ cin >> x; });
for_each(begin(v), end(v), [](auto& x){ cin >> x; });

• 可用于子范围
• 可能存在越界访问漏洞

迭代器的显式使用

• 不受容器限制 ⇒ 容器类型易更改
• 适用于所有标准序列容器
• 无需担心有符号/无符号索引类型的麻烦
• 可以跳过多个元素
• 可能存在越界访问错误
• 繁琐

std::vector<int> v {1, 2, 3, 4, 5, 6};
for (auto i = begin(v); i != end(v); ++i) { cout << *i; }
for (auto i = begin(v); i != end(v); ++i) { cin  >> *i; }
// 只读，使用常量迭代器
for (auto i = cbegin(v); i != cend(v); ++i { cout << *i; }

基于索引的循环

• 可以跳过多个元素
• 易受越界访问错误困扰
• 由于有符号/无符号索引类型转换，很容易出现难以察觉的bug
• 不适用于所有序列容器 ⇒ 不容易更改容器类型
• 确保循环不修改元素需要更多的约束
• 繁琐

std::vector<int> v {1, 2, 3, 4, 5, 6};
for (std::size_t i = 0; i < v.size(); ++i) { cout << v[i]; }
// 显式只读
const auto& cv = v;
for (std::size_t i = 0; i < cv.size(); ++i) { cout << cv[i]; }

逆向遍历

反向范围循环(C++20)

for (type variable : container | std::views::reverse)

• 适用于所有双向容器
• 不会出现越界访问错误
• 不需要担心有符号/无符号索引类型的麻烦
• 可以通过 break 实现提前退出

#include <ranges> //C++20
std::vector<int> v {1, 2, 3, 4, 5, 6};
for (int x : v | std::views::reverse) { cout << x << '\n'; }
// 只读，类型的复制成本较低或者需要复制：
for (auto x : v | std::views::reverse) { cout << x; }
// 只读，类型复制的成本很高时：
for (auto const& x : v | std::views::reverse) { cout << x; }
// 修改值时：
for (auto& x : v | std::views::reverse) { cin >> x; }

反向 for_each / for_each_n

• 如果你已经有一个可以应用到每个元素的函数（对象），那是非常方便的
• 适用于所有双向容器
• 容易更改容器类型
• 没有有符号/无符号索引类型的麻烦
• 有界限迭代器访问的错误可能会发生
• 具有自我说明的名称
  
  不会发生越界访问
  cppreference

#include <algorithm>  // std::ranges::for_each
#include <ranges>     // range views
namespace ranges = std::ranges;        // alias
namespace views = std::ranges::views;  // alias
Container<Type> v; …
// 只读，类型的复制成本较低或者需要复制：
ranges::for_each(views::reverse(v), [](Type x){ cout << x; }); 
ranges::for_each(views::reverse(v), [](auto x){ cout << x; });
// 只读，类型复制的成本很高时：
ranges::for_each(views::reverse(v), [](Type const& x){ cout << x; });
ranges::for_each(views::reverse(v), [](auto const& x){ cout << x; });
// 修改值时：
ranges::for_each(views::reverse(v), [](Type& x){ cin >> x; });
ranges::for_each(views::reverse(v), [](auto& x){ cin >> x; });

• 可用于子范围
• 可能存在越界访问漏洞
  cppreference

#include <algorithm>  // std::for_each
Container<Type> v; …
// 只读，类型的复制成本较低或者需要复制：
for_each(rbegin(v), rend(v),       [](Type x){ cout << x; });
for_each(rbegin(v)+2, rbegin(v)+5, [](auto x){ cout << x; });
// 只读，类型复制的成本很高时：
for_each(rbegin(v), rend(v), [](Type const& x){ cout << x; });
for_each(rbegin(v), rend(v), [](auto const& x){ cout << x; });
// 修改值时：
for_each(rbegin(v), rend(v), [](Type& x){ cin >> x; });
for_each(rbegin(v), rend(v), [](auto& x){ cin >> x; });

• 可用于子范围
• 可能存在越界访问漏洞

反向迭代器的显式使用

• 适用于所有双向容器
• 无需担心有符号/无符号索引类型问题
• 可以跳过多个元素
• 可能出现越界访问错误
• 繁琐

std::vector<int> v {1, 2, 3, 4, 5, 6};
for (auto i = rbegin(v); i != rend(v); ++i) { cout << *i; }
for (auto i = rbegin(v); i != rend(v); ++i) { cin  >> *i; }
// 只读，使用常量迭代器
for (auto i = crbegin(v); i != crend(v); ++i { cout << *i; }

基于索引的反向循环

• 容易出现越界访问漏洞
• 由于无符号大小类型而出现微妙错误容易编写：隐式转换为有符号整数，溢出/反转，…
• 确保循环不修改元素需要更多约束
• 繁琐

std::vector<int> v {1, 2, 3, 4, 5, 6};
// 标准容器使用无符号size类型
// ⇒ 注意不要减少无符号“0”
for (auto i = v.size(); i > 0; --i) { cout << v[i-1]; }
// 显式只读
const auto& cv = v;
for (auto i = cv.size(); i > 0; --i) { cout << cv[i-1]; }

工具

获取下一个/上一个迭代器

#include <iterator>
函数 std::prev 和 std::next 提供了一种通用的方式来递增/递减迭代器，即使迭代器类型不支持随机访问（例如，it += 5）。
然而，请注意，通过N步前进非随机访问迭代器（例如std::list中的迭代器）可能成本会很高，即涉及大约N个内存操作。

cppreference

相关内容

std::vector
标准库顺序容器
标准库关联容器
A Tour of C++: Containers and Algorithms

附上原文链接
如果文章对您有用，请随手点个赞，谢谢！^_^