列表是序列容器,允许在序列中的任何位置进行恒定时间插入和擦除操作,以及双向迭代。该容器用双向链表实现。
构造函数 | 接口说明 |
---|---|
list(size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
list() | 构造空的list |
list(const list& x) | 拷贝构造函数 |
list(InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造 |
iterator
迭代器函数声明 | 接口说明 |
---|---|
begin | 返回第一个元素的迭代器 |
end | 返回最后一个元素下一个位置的迭代器 |
rbegin | 返回第一个元素的reverse_iterator,即end位置 |
begin
与end
为正向迭代器,对迭代器执行++
操作,迭代器向后移动rbegin(end)
与rend(begin)
为反向迭代器,对迭代器执行++
操作,迭代器向前移动capacity
函数声明 | 接口说明 |
---|---|
empty() | 检测list是否为空,如果是返回true,否则返回false |
size() | 返回list中有效节点的个数 |
函数声明 | 接口说明 |
---|---|
front() | 返回list的第一个节点中值的引用 |
back() | 返回list的最后一个节点中值的引用 |
函数声明 | 接口说明 |
---|---|
push_front(val) | 在list首元素前插入值为val的元素 |
pop_front() | 删除list中第一个元素 |
push_back(val) | 在list尾部插入值为val的元素 |
pop_back() | 删除list中最后一个元素 |
insert(position, val) | 在list的position位置插入值为val的元素 |
erase(position) | 删除list的position位置的元素 |
swap(list) | 交换两个list中的元素 |
clear() | 清空list中的有效元素 |
list
中的迭代器失效问题
list
的erase()
操作可能会使迭代器失效。
list
的底层结构是双向带头循环链表,所以在list
中进行insert
操作的时候不会导致迭代器失效,只有在删除的时候才会失效,而且失效的知识指向被删除节点的迭代器,其他迭代器不会受影响。// erase 模拟实现
iterator erase(iterator pos)
{
assert(pos != end());
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
--_size;
return next;
}
it = lt.begin();
while (it != lt.end())
{
if (*it % 2 == 0)
{
it = lt.erase(it);
}
else
{
++it;
}
}
根据官方文档所述,erase
会用迭代器作为返回值,返回删除的迭代器的下一个位置的迭代器。所以在删除后可以更新迭代器,保证迭代器不会失效。
std::forward_list
, std::unordered_map
, std::unordered_set
, std::unordered_multimap
, std::unordered_multiset
std::forward_list<int> fl = {1, 2, 3};
auto it = fl.begin(); // it 是单向迭代器
while (it != fl.end())
{
// 可以递增 it
++it;
}
std::list
, std::map
, std::set
, std::multimap
, std::multiset
std::list<int> lst = {1, 2, 3};
auto it = lst.begin();
// 可以递增和递减 it
++it; // 向前
--it; // 向后
std::vector
, std::string
, std::deque
, std::array
std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin() + 2; // 直接跳到第三个元素
--it; // 递减
vec.end() - 1; // 指向最后一个元素
const_iterator
类型。std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin(); // 随机访问迭代器
// 随机访问迭代器的操作
it += 2; // 跳到第三个元素
*it -= 1; // 修改元素
// 反向迭代器
auto rit = vec.rbegin(); // reverse_iterator
++rit; // 向前(实际上是向后元素的方向)
list
时的问题在实现iterator
和const_iterator
时,为了避免两个类模板代码的冗余和相似性高,可以通过控制模版的传参,利用按需实例化来进行书写该模拟实现部分。
list_iterator
模板有三个类型参数:
T&
或 const T&
。T*
或 const T*
。这些参数允许用户根据需要定制迭代器的行为,例如是否允许修改数据(通过 Ref
)或者返回常量或非常量指针(通过 Ptr
),由此可以实例化出list_iterator
和const_list_iterator
。
模板类或函数在实际使用时才被编译器实例化。这意味着只有当用户显式地创建一个特定类型的模板实例时,编译器才会生成相应的代码。
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
例如通过传递不同的参数来进行实例化出list_iterator
和const_list_iterator
。
list
的排序list
为双向链表,std::algorithm::sort()
排序要求的是随机迭代器,而list
为双向迭代器,所以无法直接使用算法库的sort()
进行排序。
[C++] vector入门&迭代器失效问题详解-CSDN博客
在以上文章里有提及关于对于排序效率低的容器的排序方法。
对于list
的排序可以使用vector
拷贝list
内的数据,排序后再重新数据按顺序拷贝会list
。
vector<int> v(lt2.begin(), lt2.end());
// 排序
sort(v.begin(), v.end());
// 拷贝回lt2
lt2.assign(v.begin(), v.end());
vector
的排序不仅解决了list
的排序问题,还使排序更加高效。
emplace_back
与push_back
emplace_back
和push_back
都是 C++ STL 容器(如vector
、deque
、list
等)中用来在容器的末尾添加元素的方法。它们的主要区别在于元素的构造方式和性能。
push_back
std::vector<int> vec;
vec.push_back(10); // 将10的副本添加到容器末尾
emplace_back
std::vector<std::pair<int, int>> vec;
vec.emplace_back(10, 20); // 直接在容器末尾构造一个pair<int, int>
int
、float
等),复制操作对性能的影响不大。但如果元素类型是复杂的类型(如自定义类),复制操作可能会影响性能。emplace_back
可以避免复制或移动操作,直接在容器末尾构造元素,从而提高性能。push_back
。emplace_back
。list<A> lt;
A aa1(1, 1);
lt.push_back(aa1);
lt.push_back(A(2, 2));
//lt.push_back(3, 3);
lt.emplace_back(aa1);
lt.emplace_back(A(2, 2));
cout << endl;
// 支持直接传构造A对象的参数emplace_back
lt.emplace_back(3, 3);
设置打印信息,运行如下:
可以发现,在使用emplace_back(3, 3)
的时候会直接进行构造,而不会像使用push_back
一样先构造出一个对象,再拷贝构造进行插入。
push_back()
执行的时候需要一个现有的元素或者隐式的构造一个元素再拷贝到插入的空间。
emplace_back
通常在需要构造复杂类型或避免不必要的复制和移动操作时更优,而 push_back
在添加简单类型或已经存在的元素时更为方便。
->
与.
->
与.
操作符都是用来访问对象的成员,但是使用的前提不同。
.
操作符.
操作符用于直接访问对象实例的成员。它需要一个对象实例或结构体,而不是指针。
struct MyStruct {
int x;
int y;
};
MyStruct obj;
obj.x = 10; // 通过 . 访问成员
obj
是一个结构体或类的对象,通过obj.x
直接访问其成员x
。
->
操作符->
操作符用于通过指针访问对象的成员。它的功能实际上是先解引用指针,然后访问成员。
struct MyStruct {
int x;
int y;
};
MyStruct* p = new MyStruct();
p->x = 10; // 通过 -> 访问成员
p
是一个指向结构体或类的指针,通过p->x
访问指针指向对象的成员x
。p->x
等同于(*p).x
,即先解引用指针,再访问成员。
.
操作符作用于对象的实例。->
操作符作用于对象的指针。.
来访问成员。->
来访问成员。.
直接访问对象的成员,不涉及解引用。**->**
** 隐式地解引用指针,然后访问成员。**operator*()
Ref operator*()
{
return _node->_data;
}
Ref
),即_node->_data
。*ita
时,它会调用operator*()
,返回迭代器指向的数据。operator->()
Ptr operator->()
{
return &_node->_data;
}
Ptr
),即&_node->_data
。ita->
时,它会调用operator->()
,返回数据的指针,从而访问数据的成员。operator->()
的实际使用while (ita != lta.end())
{
cout << ita->_a1 << ":" << ita->_a2 << endl;
cout << ita.operator->()->_a1 << ":" << ita.operator->()->_a2 << endl;
++ita;
}
**ita->_a1**
和**ita->_a2**
:operator->()
返回了指向_node->_data
的指针,所以ita->_a1
等价于(*ita)._a1
。operator->()
,用简化了的语法,使得ita->_a1
这种写法成为可能,而不需要显式地写成(*ita)._a1
或ita.operator->()->_a1
。这使得代码更具可读性和直观性,尤其是在访问嵌套结构或类成员时。**ita.operator->()->_a1**
和**ita.operator->()->_a2**
:operator->()
,获取指向数据的指针,然后访问其成员。list
框架整体模拟实现list
的框架如图,将迭代器与节点包装成类模板进行使用: