C++ forward_list使用
forward_list
- C++ forward_list使用
-
- 概述
- 创建forward_list
-
- 构造函数
- opertor=
- assign
- 元素访问
-
- front
- 迭代器
-
- begin\cbegin
- end\cend
- before_begin, cbefore_begin
- 容量
-
- empty
- max_size
- 修改器
-
- clear
- insert_after
- emplace_after
- erase_after
- push_front
- emplace_front
- pop_front
- resize
- swap
- 操作
-
- merge
- splice_after
- remove,remove_if
- reverse
- unique
- sort
- 非成员函数
-
- operator==
- std::swap
- erase(std::forward_list)
- erase_if(std::forward_list)
概述
定义于头文件<forward_list>,std::forward_list 是支持从容器中的任何位置快速插入和移除元素的容器。不支持快速随机访问。它实现为单链表,且实质上与其在 C 中实现相比无任何开销。与 std::list 相比,此容器在不需要双向迭代时提供更有效地利用空间的存储。
在链表内或跨数个链表添加、移除和移动元素,不会非法化当前指代链表中其他元素的迭代器。然而,在从链表移除元素(通过 erase_after )时,指代对应元素的迭代器或引用会被非法化。
类模板:
template<
class T,
class Allocator = std::allocator<T>
> class forward_list;
模板形参:
T - 元素的类型;
Allocator - 用于获取/释放内存及构造/析构内存中元素的分配器。
创建forward_list
构造函数
从各种数据源构造新容器,可选地使用用户提供的分配器 alloc 。
与 vector、deque、list 构造函数一样。
定义:
// 1、默认构造函数
forward_list();
// 2、构造拥有给定分配器 alloc 的空容器。
explicit forward_list( const Allocator& alloc );
// 3、构造拥有 count 个有值 value 的元素的容器。
forward_list( size_type count,
const T& value,
const Allocator& alloc = Allocator());
// 4、构造拥有个 count 默认插入的 T 实例的容器。不进行复制。
explicit forward_list( size_type count, const Allocator& alloc = Allocator() );
// 5、构造拥有范围 [first, last) 内容的容器。
template< class InputIt >
forward_list( InputIt first, InputIt last,
const Allocator& alloc = Allocator() );
// 6、复制构造函数
forward_list( const forward_list& other );
// 7、构造拥有 other 内容的容器,以 alloc 为分配器。
forward_list( const forward_list& other, const Allocator& alloc );
// 8、移动构造函数
forward_list( forward_list&& other );
// 9、有分配器扩展的移动构造函数。
forward_list( forward_list&& other, const Allocator& alloc );
// 10、构造拥有 initializer_list init 内容的容器。
forward_list( std::initializer_list<T> init,
const Allocator& alloc = Allocator() );
用法:
// 1、默认构造函数
std::forward_list<std::string> words1;
// 3、构造拥有 count 个有值 value 的元素的容器
std::forward_list<std::string> words3(5, "Mo"); //words2 为 {"Mo", "Mo", "Mo", "Mo", "Mo"}
// 5、构造拥有范围 [first, last) 内容的容器
std::forward_list<std::string> words5(words3.begin(), words3.end());
// 6、复制构造函数
std::forward_list<std::string> words6(words5);
// 8、移动构造函数
std::forward_list<std::string> words8(std::move(words6));
// 10、C++ 11 初始化器列表语法:
std::forward_list<std::string> words10 {"the", "frogurt", "is", "also", "cursed"};
opertor=
替换容器的内容。
定义:
forward_list& operator=( const forward_list& other ); // 复制赋值运算符。
forward_list& operator=( forward_list&& other ); // 移动赋值运算符。
forward_list& operator=( std::initializer_list<T> ilist ); // 以 initializer_list ilist 所标识者替换内容。
用法:
std::forward_list<int> nums1 {3, 1, 4, 6, 5, 9};
std::forward_list<int> nums2;
std::forward_list<int> nums3;
// 从 nums1 复制赋值数据到 nums2
nums2 = nums1;
// 从 nums1 移动赋值数据到 nums3,
nums3 = std::move(nums1);
// initializer_list 的复制赋值复制数据给 nums3
nums3 = {1, 2, 3};
assign
替换容器的内容。
定义:
void assign( size_type count, const T& value ); // 1、以 count 份 value 的副本替换内容。
template< class InputIt > // 2、以范围 [first, last) 中元素的副本替换内容。
void assign( InputIt first, InputIt last );
void assign( std::initializer_list<T> ilist ); // 3、以来自 initializer_list ilist 的元素替换内容。
用法:
// 以 count 份 value 的副本替换内容
std::forward_list<char> characters;
characters.assign(5, 'a');
// 以范围 [first, last) 中元素的副本替换内容
std::forward_list<char> vchar;
vchar.assign(characters.begin(), characters.end());
// 以来自 initializer_list ilist 的元素替换内容
characters.assign({'\n', 'C', '+', '+', '1', '1', '\n'});
元素访问
front
返回到容器首元素的引用。
对于容器 c ,表达式 c.front() 等价于 *c.begin() 。
定义:
reference front();
const_reference front() const;
用法:
std::forward_list<char> letters {'o', 'm', 'g', 'w', 't', 'f'};
if (!letters.empty()) {
std::cout << letters.front() << std::out; // 输出 o
}
迭代器
begin\cbegin
返回指向 forward_list 首元素的迭代器。 cbegin中的c表示const,即返回const_iterator,不允许通过迭代器修改元素。
若 forward_list 为空,则返回的迭代器将等于 end() 。
定义:
iterator begin();
const_iterator cbegin() const noexcept;
用法:
std::forward_list<int> vi = {1, 2, 3, 4, 5, 6};
std::cout << *(vi.begin()) << std::endl; // 输出 1
*(vi.begin()) = 0;
std::cout << *(vi.cbegin()) << std::endl; // 输出 0
end\cend
指向后随最后元素的迭代器。
定义:
iterator end();
const_iterator cend() const noexcept;
用法:
std::forward_list<char> vc;
if (vc.begin() == vc.end())
{
std::cout << "forward_list is empty." << std::endl;
}
before_begin, cbefore_begin
返回指向首元素前一元素的迭代器。
定义:
iterator before_begin() noexcept; // (C++11 起)
const_iterator before_begin() const noexcept; // (C++11 起)
const_iterator cbefore_begin() const noexcept; // (C++11 起)
容量
empty
检查容器是否无元素,即是否 begin() == end() 。
定义:
用法:
forward_list<int> v;
bool flag = v.empty(); // 输出 true
max_size
返回根据系统或库实现限制的容器可保有的元素最大数量,即对于最大容器的 std::distance(begin(), end()) 。
定义:
用法:
std::forward_list<int> vi;
std::cout << vi.max_size() << std::endl; // 可能输出 4611686018427387903
std::forward_list<char> vc;
std::cout << vc.max_size() << std::endl; // 可能输出 18446744073709551615
修改器
clear
从容器擦除所有元素。此调用后 size() 返回零。
非法化任何指代所含元素的引用、指针或迭代器。任何尾后迭代器亦被非法化。
定义:
用法:
std::forward_list<int> container{1, 2, 3};
container.clear();
std::cout << container.size() << std::endl; // 输出 0
insert_after
在容器中的指定位置后插入元素。
定义:
// 1、在 pos 后插入 value
iterator insert_after( const_iterator pos, const T& value );
// 2、在 pos 后插入 value
iterator insert_after( const_iterator pos, T&& value );
// 3、在 pos 后插入 value 的 count 个副本
void insert_after( const_iterator pos, size_type count, const T& value );
// 4、在 pos 后插入来自范围 [first, last) 的元素
template< class InputIt >
void insert_after( const_iterator pos, InputIt first, InputIt last);
// 5、在 pos 前插入来自 initializer_list ilist 的元素
iterator insert_after( const_iterator pos, std::initializer_list<T> ilist );
用法:
std::forward_list<int> vec(3,100);
// 1,2、在 pos 前插入 value
auto it = vec.begin();
it = vec.insert_after(it, 200); // 100 200 100 100
// 3、插入多个value
vec.insert_after(it,2,300); // 100 200 300 300 100 100
// 4、在 pos 前插入来自范围 [first, last) 的元素
std::forward_list<int> vec2(2,400);
vec.insert_after(vec.begin(), vec2.begin(), vec2.end()); // 100 400 400 200 300 300 100 100
// 5、在 pos 前插入来自 initializer_list ilist 的元素
int arr[] = { 501,502,503 };
vec.insert_after(vec.begin(), arr, arr+3); // 100 501 502 503 400 400 200 300 300 100 100
emplace_after
在容器中的指定位置后插入新元素。
定义:
template< class... Args >
iterator emplace_after( const_iterator pos, Args&&... args );
用法:
std::forward_list<int> v {1, 2, 3};
v.emplace(v.begin(), 4); // v : 1, 4, 2, 3
erase_after
从容器擦除指定的元素。
定义:
// 1、移除位于 pos 的元素。
iterator erase_after( const_iterator pos );
// 2、移除范围 [first; last) 中的元素。
iterator erase_after( const_iterator first, iterator last );
用法:
std::forward_list<int> c {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
c.erase_after(c.begin()); // 1 2 3 4 5 6 7 8 9
c.erase_after(c.begin(), c.end());
push_front
前附给定元素 value 到容器起始。 所有迭代器,包含尾后迭代器,都被非法化
定义:
void push_front( const T& value );
void push_front( T&& value );
用法:
std::forward_list<int> numbers {1, 2};
numbers.push_front(0); // {0, 1, 2}
emplace_front
插入新元素到容器起始。
定义:
// C++ 11
template< class... Args >
void emplace_front( Args&&... args );
// C++ 17
template< class... Args >
reference emplace_front( Args&&... args );
pop_front
移除容器首元素。 指向被擦除元素的迭代器和引用被非法化。
定义:
用法:
std::forward_list<int> c = {1, 2, 3};
c.pop_front(); // c : 2, 3
resize
重设容器大小以容纳 count 个元素。 若当前大小大于 count ,则减小容器为其首 count 个元素。若当前大小小于 count ,1) 则后附额外的默认插入的元素,2) 则后附额外的 value 的副本。
定义:
void resize( size_type count );
void resize( size_type count, const value_type& value );
用法:
std::forward_list<int> c = {1, 2, 3};
c.resize(5); // c : 1, 2, 3, 0, 0
c.resize(2); // c : 1, 2
swap
将内容与 other 的交换。 不在单独的元素上调用任何移动、复制或交换操作。
定义:
用法:
std::forward_list<int> a1{1, 2, 3}, a2{4, 5};
a1.swap(a2);
操作
merge
归并二个已排序链表为一个。 链表应以升序排序。
定义:
void merge( forward_list& other );
void merge( forward_list&& other );
template <class Compare>
void merge( forward_list& other, Compare comp );
template <class Compare>
void merge( forward_list&& other, Compare comp );
用法:
std::forward_list<int> list1 = { 5,9,0,1,3 };
std::forward_list<int> list2 = { 8,7,2,6,4 };
list1.sort();
list2.sort();
list1.merge(list2); // list1 : 0 1 2 3 4 5 6 7 8 9
list2.empty(); // list2为空
splice_after
从一个 forward_list 转移元素给另一个。 不复制或移动元素,仅重指向链表结点的内部指针。
定义:
void splice_after( const_iterator pos, forward_list& other );
// 1、从 other 转移所有元素到 *this 中。元素被插入到 pos 所指向的元素之前。操作后容器 other 变为空。若 other 与 *this 指代同一对象则行为未定义。
void splice_after( const_iterator pos, forward_list&& other );
void splice_after( const_iterator pos, forward_list& other, const_iterator it );
// 2、从 other 转移 it 所指向的元素到 *this 。元素被插入到 pos 所指向的元素之前。
void splice_after( const_iterator pos, forward_list&& other, const_iterator it );
void splice_after( const_iterator pos, forward_list& other, const_iterator first, const_iterator last );
// 3、从 other 转移范围 [first, last) 中的元素到 *this 。元素被插入到 pos 所指向的元素之前。若 pos 是范围 (first,last) 中的迭代器则行为未定义。
void splice_after( const_iterator pos, forward_list&& other, const_iterator first, const_iterator last );
用法:
std::forward_list<int> l1 = {1, 2, 3, 4, 5};
std::forward_list<int> l2 = {10, 11, 12};
l2.splice_after(l2.cbegin(), l1, l1.cbegin(), l1.cend());
// 不等价于 l2.splice_after(l2.cbegin(), l1);
// l1 : 1
// l2 : 10 2 3 4 5 11 12
remove,remove_if
移除所有满足特定标准的元素。 第一版本移除所有等于 value 的元素,第二版本移除所有谓词 p 对它返回 true 的元素。
定义:
void remove( const T& value ); // (C++20 前)
size_type remove( const T& value ); // (C++20 起)
template< class UnaryPredicate > // (C++20 前)
void remove_if( UnaryPredicate p );
template< class UnaryPredicate > // (C++20 起)
size_type remove_if( UnaryPredicate p );
用法:
std::forward_list<int> l = { 1,100,2,3,10,1,11,-1,12 };
// 移除两个等于 1 的元素
l.remove(1); // 100, 2, 3, 10, 11, -1, 12
// 移除全部大于 10 的元素
l.remove_if([](int n){ return n > 10; }); // 2, 3, 10, -1
reverse
逆转容器中的元素顺序。 不非法化任何引用或迭代器。
定义:
用法:
std::forward_list<int> list = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
list.reverse(); // 9 8 7 6 5 4 3 2 1 0
unique
**从容器移除所有连续的重复元素。只留下相等元素组中的第一个元素。 **第一版本用 operator== 比较元素,第二版本用二元谓词 p 比较元素
定义:
void unique(); // (C++20 前)
size_type unique(); // (C++20 后)
template< class BinaryPredicate >
void unique( BinaryPredicate p ); // (C++20 前)
template< class BinaryPredicate >
size_type unique( BinaryPredicate p ); // (C++20 起)
用法:
std::forward_list<int> x = {1, 2, 2, 3, 3, 2, 1, 1, 2};
x.unique();
for (auto val : x)
{
std::cout << ' ' << val; // 1 2 3 2 1 2
}
sort
以升序排序元素。保持相等元素的顺序。 第一版本用 operator< 比较元素,第二版本用给定的比较函数 comp 。
定义:
void sort();
template< class Compare >
void sort( Compare comp );
用法:
std::forward_list<int> list = { 8,7,5,9,0,1,3,2,6,4 };
list.sort();
std::cout << "ascending: " << list << "\n"; // 0 1 2 3 4 5 6 7 8 9
list.sort(std::greater<int>());
std::cout << "descending: " << list << "\n"; // 9 8 7 6 5 4 3 2 1 0
非成员函数
operator==
检查 lhs 与 rhs 的内容是否相等,即它们是否拥有相同数量的元素且 lhs 中每个元素与 rhs 的同位置元素比较相等。
定义:
template< class T, class Alloc >
bool operator==( const std::forward_list<T,Alloc>& lhs,
const std::forward_list<T,Alloc>& rhs );
用法:
std::forward_list<int> alice{1, 2, 3};
std::forward_list<int> bob{7, 8, 9, 10};
std::forward_list<int> eve{1, 2, 3};
// 比较不相等的容器
std::cout << "alice == bob returns " << (alice == bob) << std::endl; //输出 false
// 比较相等的容器
std::cout << "alice == eve returns " << (alice == eve) << std::endl; //输出 true
std::swap
为 std::forward_list 特化 std::swap 算法。交换 lhs 与 rhs 的内容。调用 lhs.swap(rhs) 。
定义:
template< class T, class Alloc >
void swap( std::forward_list<T,Alloc>& lhs,
std::forward_list<T,Alloc>& rhs );
用法:
std::forward_list<int> alice{1, 2, 3};
std::forward_list<int> bob{7, 8, 9, 10};
//交换容器
std::swap(alice,bob);
//交换后:alice : 7 8 9 10 bob : 1 2 3
erase(std::forward_list)
从容器中擦除所有比较等于 value 的元素。(C++ 20)
定义:
template< class T, class Alloc, class U >
constexpr typename std::forward_list<T,Alloc>::size_type
erase(std::forward_list<T,Alloc>& c, const U& value);
用法:
std::forward_list<char> cnt {'1', '2', '3', '5', '6'};
auto erased = std::erase(cnt, '3');
erase_if(std::forward_list)
从容器中擦除所有满足 pred 的元素。(C++ 20)
定义:
template< class T, class Alloc, class U >
constexpr typename std::forward_list<T,Alloc>::size_type
erase_if(std::forward_list<T,Alloc>& c, Pred pred);
用法:
std::forward_list<char> cnt {'1', '2', '3', '5', '6'};
std::erase_if(cnt,
[](char x) { return (x - '0') % 2 == 0; }
);