theme: smartblue
list
list文档
- list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
- list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向 其前一个元素和后一个元素。
- list与forward_list非常相似:最主要的不同在于forward_list是单链表,只能朝前迭代,已让其更简单高 效。
- 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率 更好。
5.与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,比如:要访问list 的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间 开销;list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这 可能是一个重要的因素)
list类的函数接口
namespace ding
{
//结点类
templateclass T>
struct _list_node
{
//构造函数
_list_node(const T& val = T());
T _data;
_list_nodeT>* _next;
_list_nodeT>* _prev;
};
//迭代器类
templateclass T, class Ref, class Ptr>
struct _list_iterator
{
typedef _list_nodeT> node;
typedef _list_iteratorT, Ref, Ptr> self;
//构造函数
_list_iterator(node* pnode);
self operator++();
self operator--();
self operator++(int);
self operator--(int);
bool operator==(const self& s) const;
bool operator!=(const self& s) const;
Ref operator*();
Ptr operator->();
//成员变量
node* _pnode;
};
//list类
templateclass T>
class list
{
public:
typedef _list_nodeT> node;
typedef _list_iteratorT, T&, T*> iterator;
typedef _list_iteratorT, const T&, const T*> const_iterator;
//Member functions
list();
list(const listT>& lt);
listT>& operator=(const listT>& lt);
~list();
//Iterators:
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
//Element access:
T& front();
T& back();
const T& front() const;
const T& back() const;
//Modifiers:
void insert(iterator pos, const T& x);
iterator erase(iterator pos);
void push_back(const T& x);
void pop_back();
void push_front(const T& x);
void pop_front();
//Capacity:
size_t size() const;
void resize(size_t n, const T& val = T());
void clear();
bool empty() const;
void swap(listT>& lt);
private:
node* _head;
};
}
结点类的实现
list底层采用了带头双向循环链表的结构实现。
在实现list前,需要定义出一个一个结点出来。直接定义一个结点类,让结点类完成结点的构造即可。
templateclass T>
struct _list_node
{
_list_node(const T& val = T())
:_data(val)
,_next(nullptr)
,_prev(nullptr)
{}
T _data;
_list_nodeT>* _next;
_list_nodeT>* _prev;
};
迭代器类的实现
- list底层物理空间不再连续,不再支持[]+下标的方式进行访问
- 只能用迭代器进行访问
- list迭代器的实现不能再像string或者vector那种底层物理空间连续的容器使用原生指针进行实现。
- 底层空间连续,使用原生指针实现,指针自增或者自减就可以访问到对应的元素,而list由于底层物理空间不来连续的原因,不能再使用原生指针
解决方法:
- 定义一个迭代器类,迭代器相关的操作(比如++,!=,*)等操作但都在迭代器类中重载
结合之前string类和vector类的实现得知迭代器要么就是原生指针,要么就是自定义类型对原生指针的一种封装,去模拟指针的行为。比如对结点指针自增就能指向下一个结点
构造函数
迭代器就是对结点指针进行封装,这里只需要一个结点指针成员变量即可。
_list_iterator(node* node)
{
_node = node;
}
++运算符重载
self operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
- 这里的self是经过typedef后的
typedef _list_iterator self
就是迭代器类类型 - 前置++与后置++重载语法规定后置++的形参必须为int。
- 后置++先记录一下当前结点,再让结点指向后一个,返回自增前的即可。
–运算符重载
self operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
*运算符重载
解引用操作符,是想拿到地址的内容,直接返回当前结点的数据内容即可。
Ref operator*()
{
return _node->_data;
}
注意:
这里的返回值是Ref,在定义迭代器类是时候定义了三个模板参数,T就是指定的类型,Ref则是指定类型的引用类型,也就是T&,Ptr则是指定类型的指针类型,也就是T*。
在list的实现中,
typedef _list_iteratorT, T&, T*> iterator;服务器托管网
typedef _list_iteratorT, const T&, const T*> const_iterator;
- STL底层源码就是这样设计的,主要就是为了解决const迭代器的问题,如果不用模板解决的话,可以在定义一个const iterator类也可以解决问题,但是在实现以一个const迭代器与普通迭代器的区别就仅仅只是*返回值类型不一样而已,利用模板参数解决更妙。
- 普通迭代器返回T&类型,const迭代器返回const T&类型。
- 这里返回引用类型,主要是因为解引用后可能需要对数据进行修改。
!= && ==
迭代器经常需要进行判断两个迭代器是否相等不相等的操作,这里这需要判断两个迭代器中的结点是否相等即可,不需要做其他操作,定义出成const更为合理。
bool operator==(const self& s) const
{
return _node == s._node;
}
bool operator!=(const self& s) const
{
return _node != s._node;
}
->操作符重载
这个操作符对于迭代器类型并不是很常用,但是为了模拟指针的行为,指针有->操作符,迭代器就模拟实现了。
运算符 -> 必须是一个成员函数。如果使用了 -> 运算符,返回类型必须是指针或者是类的对象。也就是这里返回值必须是Ptr 指定类型T*类型。
Ptr operator->()
{
return &(_node->_data);
}
使用->场景:
当list中存放的是自定义类型,
class Date
{
public:
Date(int year)
{
_year = year;
}
int _year = 0;
};
int main()
{
std::listDate>lt;
lt.push_back(2023);
lt.push_back(2024);
auto it = lt.begin();
cout it->_year endl;
return 0;
}
可以使用->访问类的成员变量。
list类的实现
Member functions
构造函数
list()
{
_head = new node;
_head->_prev = _head;
_head->_next = _head;
}
这里的node是经过typedef得。typedef _list_node node;
对结点类起的别名
构造一个链表即可,这里得空链表是需要一个头节点得。并且让自己指向自己。
拷贝构造
申请一个新的头结点,再将源容器中的数据依次尾插到新容器中即可
list(const listT>& lt)
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
for (auto val : lt)
{
push_back(val);
}
}
赋值运算符重载
- 将原来容器中的数据清空,在依次尾插新元素即可
- 注意要判断是否自己给自己赋值,不能自己给自己赋值,自己给自己赋值clear后数据丢失了
listT>& operator=(const listT>& lt)
{
if (this != <)
{
clear();
for (const auto e : lt)
{
push_back(e);
}
}
return *this;
}
迭代器构造
templateclass InputIterator>
list(InputIterator first, InputIterator last)
{
_head = new node;
_head->_prev = _head;
_head->_next = _head;
while (first != last)
{
push_back(*first);
++first;
}
}
析构函数
先清空容器在释放头节点即可
~list()
{
clear();
delete _head;
_head = nullptr;
}
clear函数
void clear()
{
auto it = begin();
while (it != end())
{
erase(it++);
}
}
Iterators
begin && end
begin函数返回的是第一个有效数据的迭代器,end函数返回的是最后一个有效数据的下一个位置的迭代器
底层是双向循环链表实现的,所以头结点的下一个就是gebin,头节点就是end。
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head->_prev);
}
const_iterator begin() const
{
return iterator(_head->_next);
}
const_iterator end() const
{
return iterator(_head->_prev);
}
Modifiers
insert
在pos位置前面插入一个结点
void insert(iterator pos, const T& x)
{
node* newnode = new node(x);//创建新结点
node* cur = pos._node;//pos位置的结点指针
node* prev = cur->_prev;//pos前一个
//连接关系
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
}
push_back && push_front
- 尾插 && 头插
- 在链表的尾部插入一个结点 && 在链表的头部插入一个结点
- 有了insert和迭代器,直接函数复用即可
//尾插
void push_back(const T& x)
{
insert(end(), x);
}
//头插
void push_front(const T& x)
{
insert(begin(), x);
}
eraser
删除pos位置的结点
iterator erase(iterator pos)
{
node* cur = pos._node;//当前结点指针
node* prev = cur->_prev;//pos位置前一个结点
node* next = cur->_next;//pops位置后一个结点
//连接关系
prev->_next = next;
next->_prev = prev;
//释放删除的结点
delete cur;
return iterator(next);//防止迭代器失效,返回pos位置下一个迭代器
}
pop_back && pop_front
- 尾删和头删
- 复用迭代器和rease即可
- end是头节点,尾删时需要–end() 才是尾部结点
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
Capacity
size
- 求容器元素个数
- 遍历容器求个数(效率太低不推荐)
size_t size() const
{
size_t size = 0;
auto it = begin();
while (it != end())
{
size++;
it++;
}
return size;
}
- 在定义一个成员变量统计元素个数(以空间换时间,更推荐)
clear
- 清空list中的结点,除了头结点。
- 利用迭代器遍历尾删即可
void clear()
{
auto it = begin();
while (it != end())
{
pop_back();
服务器托管网 }
}
empty
bool empty() const
{
return _head->_next;
}
resize
- 扩容加初始化函数
- resize规则
- 若当前容器的size小于所给n,则尾插结点,直到size等于n为止。
- 若当前容器的size大于所给n,则只保留前n个有效数据。
void resize(size_t n, const T& val = T())
{
size_t sz = size();
if (sz n)//扩容
{
for (; sz n; ++sz)
{
push_back(val);
}
}
else//不扩容
{
if (sz > n)//缩容
{
int len = sz - n;
cout len endl;
while (len--)
{
pop_back();
}
}
}
}
swap函数
交换两个容器的头指针即可
void swap(listT>& lt)
{
std::swap(_head, lt._head);
}
参考源码
- gitee 码云 – 开源中国
- 欢迎在评论区提出问题或留下你的观点
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
1.相关概念 物理卷:简称PV,逻辑卷管理中处于最底层,它可以是实际物理硬盘上的分区`,也可以是整个物理硬盘,一块硬盘,或多块硬盘,如/dev/sdb。 卷组:简称VG,建立在物理卷之上,一个卷组中至少要包括一个物理卷,在卷组建立之后可动态添加物理卷到卷组中。…