C++ forward_list用法详解
forward_list 的单向链接性也意味着它会有一些其他的特性:
- 无法使用反向迭代器。只能从它得到const或non-const前向迭代器,这些迭代器都不能解引用,只能自增;
- 没有可以返回最后一个元素引用的成员函数back();只有成员函数front();
- 因为只能通过自增前面元素的迭代器来到达序列的终点,所以push_back()、pop_back()、emplace_back()也无法使用。
forward_list 的操作比 list 容器还要快,而且占用的内存更少,尽管它在使用上有很多限制,但仅这一点也足以让我们满意了。
forward_list 容器的构造函数的使用方式和 list 容器相同。forward_list 的迭代器都是前向迭代器。它没有成员函数 size(),因此不能用一个前向迭代器减去另一个前向迭代器,但是可以通过使用定义在头文件 iterator 中的 distance() 函数来得到元素的个数。例如:
std::forward_list<std::string> my_words {"three", "six", "eight"}; auto count = std::distance(std::begin(my_words),std::end(my_words)); // Result is 3distance() 的第一个参数是一个开始迭代器,第二个参数是一个结束迭代器,它们指定了元素范围。当需要将前向迭代器移动多个位置时,advance() 就派上了用场。例如:
std::forward_list<int> data {10, 21, 43, 87, 175, 351}; auto iter = std::begin(data); size_t n {3}; std::advance(iter, n); std::cout << "The " << n+1 << "th element is n << *iter << std::endl; // Outputs 87这并不神奇。advance() 函数会将前向迭代器自增需要的次数。这使我们不必去循环自增迭代器。需要记住的是这个函数自增的是作为第一个参数的迭代器,但是并不会返回它——advance() 的返回类型为 void。
因为 forward_list 正向链接元素,所以只能在元素的后面插入或粘接另一个容器的元素,这一点和 list 容器的操作不同,list 可以在元素前进行操作。因为这个,forward_list 包含成员函数splice_after() 和 insert_after(),用来代替 list 容器的 splice() 和 insert();顾名思义,元素会被粘接或插入到 list 中的一个特定位置。当需要在 forward_list 的开始处粘接或插入元素时,这些操作仍然会有问题。除了第一个元素,不能将它们粘接或插入到任何其他元素之前。
这个问题可以通过使用成员函数 cbefore_begin() 和 before_begin() 来解决。它们分别可以返回指向第一个元素之前位置的 const 和 non-const 迭代器。所以可以使用它们在开始位置插入或粘接元素。例如:
std::forward_list<std::string> my_words {"three", "six", "eight"} std::forward_list<std::string> your_words {"seven", "four", "nine"}; my_words.splice_after(my_words.before_begin(), your_words, ++std::begin(your_words));这个操作的效果是将 your_words 的最后一个元素粘接到 my_words 的开始位置,因此 my_words 会包含这些字符串对象:"ninef"、"three"、"six"、"eight"。这时 your_words 就只剩下两个字符串元素:"seven"和"four”。
还有另一个版本的 splice_afler(),它可以将 forward_list<T> 的一段元素粘接到另一个容器中:
my_words.splice_after (my_words . before_begin () , your_words,++std::begin(your_words), std::end(your_words));最后两个迭代器参数,指定了第三个参数所指定的 fbrward_list<T> 容器的元素范围。在这个范围内的元素,除了第一个,其他的都被移到第一个参数所指定容器的特定位置。 因此,如果在容器初始化后执行这条语句,my_words 会包含"four"、"nine"、"three"、"six"、 "eight",your_words 仅仅包含"seven”。
另一个版本的 splice_after() 会将一个 forward_list<T> 容器的全部元素粘接到另一个容器中:
my_words.splice_after(my_words.before_begin(), your_words);上面的代码会将 your_words 中的全部元素拼接到第一个元素指定的位置。
forward_list 和 list —样都有成员函数 sort() 和 merge(),它们也都有 remove()、remove_if() 和unique(),所有这些函数的用法都和 list 相同。我们可以尝试在一个示例中演示 forward_list 的操作。容器会包含一些代表矩形盒子的 Box 类对象。下面是 Box 类的头文件中的内容:
// Defines the Box class for Ex2_06 #ifndef BOX_H #define BOX_H #include <iostream> // For standard streams #include <utility> // For comparison operator templates using namespace std::rel_ops; // Comparison operator template namespace class Box { private: size_t length {}; size_t width {}; size_t height {}; public: explicit Box(size_t l = 1, size_t w = 1, size_t h = 1) : length {l}, width {w}, height {h} {} double volume() const { return length*width*height; } bool operator<(const Box& box) { return volume() < box.volume(); } bool operator==(const Box& box) { return length == box.length&& width == box.width&&height == box.height; } friend std::istream& operator>>(std::istream& in, Box& box); friend std::ostream& operator<<(std::ostream& out, const Box& box); }; inline std::istream& operator>>(std::istream& in, Box& box) { std::cout << "Enter box length, width, & height separated by spaces - Ctrl+Z to end: "; size_t value; in >> value; if (in.eof()) return in; box.length = value; in >> value; box.width = value; in >> value; box.height = value; return in; } inline std::ostream& operator<<(std::ostream& out, const Box& box) { out << "Box(" << box.length << "," << box.width << "," << box.height << ") "; return out; } #endifutility 头文件中的命名空间 std::relops 包含一些比较运算符的模板。如果一个类已经定义了 operator<() 和 operator==(),那么在需要时,这个模板会生成剩下的比较运算符函数。
Box 类有三个私有成员,它们定义了 Box 对象的整体尺寸。带默认值的构造函数提供了一个无参构造函数,当在容器中保存 Box 对象时,需要使用它;没有初始化的元素由这种元素默认的构造函数生成。内联的友元函数重载了流的提取和插入运算,这显然包含标准输入输出流。
每次以三个输入值为一组,在读入第一个输入值后,operator>>() 函数会通过调用流对象的 eof() 函数来检查是否读到 EOF。当输入 Ctrl+Z 或从文件输入流中读到文件结束符时,标准输入流会被设置为 EOF。当这些发生时会结束输入,然后返回一个流对象,EOF 状态会继续保持,因此调用程序可以检测到这个状态。
下面是一个在 forward_list 容器中保存 Box 对象的示例:
// Working with a forward list #include <algorithm> // For copy() #include <iostream> // For standard streams #include <forward_list> // For forward_list container #include <iterator> // For stream iterators #include "Box.h" // List a range of elements template<typename Iter> void list_elements(Iter begin, Iter end) { size_t perline {6}; // Maximum items per line size_t count {}; // Item count while (begin != end) { std::cout << *begin++; if (++count % perline == 0) { std::cout << "\n"; } } std::cout << std::endl; } int main() { std::forward_list<Box> boxes; std::copy(std::istream_iterator<Box>(std::cin), std::istream_iterator<Box>(), std::front_inserter(boxes)); boxes.sort(); // Sort the boxes std::cout << "\nAfter sorting the sequence is:\n"; // Just to show that we can with Box objects - use an ostream iterator std::copy(std::begin(boxes), std::end(boxes), std::ostream_iterator<Box>(std::cout, " ")); std::cout << std::endl; // Insert more boxes std::forward_list<Box> more_boxes {Box {3, 3, 3}, Box {5, 5, 5}, Box {4, 4, 4}, Box {2, 2, 2}}; boxes.insert_after(boxes.before_begin(), std::begin(more_boxes), std::end(more_boxes)); std::cout << "After inserting more boxes the sequence is:\n"; list_elements(std::begin(boxes), std::end(boxes)); boxes.sort(); // Sort the boxes std::cout << std::endl; std::cout << "The sorted sequence is now:\n"; list_elements(std::begin(boxes), std::end(boxes)); more_boxes.sort(); boxes.merge(more_boxes); // Merge more_boxes std::cout << "After merging more_boxes the sequence is:\n"; list_elements(std::begin(boxes), std::end(boxes)); boxes.unique(); std::cout << "After removing successive duplicates the sequence is:\n"; list_elements(std::begin(boxes), std::end(boxes)); // Eliminate the small ones const double max_v {30.0}; boxes.remove_if([max_v](const Box& box){ return box.volume() < max_v; }); std::cout << "After removing those with volume less than 30 the sorted sequence is:\n"; list_elements(std::begin(boxes), std::end(boxes)); }运行结果为:
Enter box length, width, & height separated by spaces - Ctrl+Z to end: 4 4 5
Enter box length, width, & height separated by spaces - Ctrl+Z to end: 6 5 7
Enter box length, width, & height separated by spaces - Ctrl+Z to end: 2 2 3
Enter box length, width, & height separated by spaces - Ctrl+Z to end: 12 3
Enter box length, width, & height separated by spaces - Ctrl+Z to end: 3 3 4
Enter box length, width, & height separated by spaces - Ctrl+Z to end: 3 3 3
Enter box length, width, & height separated by spaces - Ctrl+Z to end: ^Z
After sorting the sequence is:
Box(l,2,3) Box(2,2,3) Box(3,3,3) Box(3,3,4) Box(4,4,5) Box(6,5,7)
After inserting more boxes the sequence is:
Box(3,3,3) Box(5,5,5) Box(4,4,4) Box{2,2,2) Box(1,2,3) Box(2,2,3)
Box(3,3,3) Box(3,3,4) Box(4,4,5) Box(6,5,7)
The sorted sequence is now:
Box(l,2,3) Box(2,2,2) Box(2,2,3) Box(3,3,3) Box(3,3,3) Box(3,3,4)
Box (4,4,4) Box(4,4,5) Box(5,5,5) Box(6,5,7)
After merging more_boxes the sequence is:
Box(1,2,3) Box(2,2,2) Box(2,2,2) Box(2,2,3) Box(3,3,3) Box(3,3,3)
Box(3,3,3) Box(3,3,4) Box(4,4^4) Box(4,4,4) Box(4,4,5) Box(5,5,5)
Box(5,5,5) Box(6,5,7)
After removing successive duplicates the sequence is:
Box(1,2,3) Box(2,2,2) Box(2,2,3) Box (3,3,3) Box(3,3,4) Box(4,4,4)
Box(4,4,5) Box(5,5,5) Box(6,5,7)
After removing those with volume less than 30 the sorted sequence is:
Box(3,3,4) Box(4,4) Box(4,4,5) Box(5,5,5) Box(6,5,7)
front_inserter 会调用容器的成员函数 push_front(),这是为 forward_list 所做的工作。对 boxes 容器中的元素进行排序后,我们会通过copy() 算法将元素转移到 ostream_iterator<Box> 对象中,然后输出它们。这个迭代器会调用定义在 Box.h 中的函数 operator<<()。这里有一个限制,我们无法控制每行元素输出的个数。剩下的代码是用模板 list_elements() 输出的实例。
另一个 forward_list 容器 more_boxes 的内容被插入到 boxes 容器的头部。这是通过以函数 before_begin() 返回的迭代器作为插入位置,然后调用函数 insert_after() 来实现的。
下一步操作是对 boxes 中的元素进行排序,然后将 more_boxes 的内容合并到 boxes 中。这两个容器在调用merge()前都必须先排序,因为只有在两个容器都是升序时,这个操作才能正常进行。因为插入新元素,显然会使 boxes 中出现一些重复的元素。调用 boxes 的函数 unique() 就可以消除连续重复的元素。
最后一个操作是调用 boxes() 的函数 remove_if() 来 删除容器中的一些元素。由作为参数传入的一元断言来决定删除哪些元素。这里使用的是一个 lambda 表达式,如果元素体积小于 max_v,就返回 true。max_v 是从外部区域以值的方式捕获的,因此外部区域和表达式内部的值可能不同。由输出可以看出,所有的操作都符合预期。
所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频