node.js可以做网站,常州网站建设方案优化,跨境电商平台规则,wordpress后台加站点图标theme: smartblue
list list文档
list是可以在常数范围内在任意位置进行插入和删除的序列式容器#xff0c;并且该容器可以前后双向迭代。list的底层是双向链表结构#xff0c;双向链表中每个元素存储在互不相关的独立节点中#xff0c;在节点中通过指针指向 其前一个元素…
theme: smartblue
list list文档
list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向 其前一个元素和后一个元素。list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高 效。与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率 更好。 5.与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list 的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间 开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这 可能是一个重要的因素)
list类的函数接口
namespace ding
{//结点类templateclass Tstruct _list_node{//构造函数_list_node(const T val T());T _data; _list_nodeT* _next; _list_nodeT* _prev; };//迭代器类templateclass T, class Ref, class Ptrstruct _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 Tclass list{public:typedef _list_nodeT node;typedef _list_iteratorT, T, T* iterator;typedef _list_iteratorT, const T, const T* const_iterator;//Member functionslist();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_iteratorT, Ref, Ptr 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则是指定类型的引用类型也就是TPtr则是指定类型的指针类型也就是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::listDatelt;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_nodeT 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 ! lt){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 码云 - 开源中国欢迎在评论区提出问题或留下你的观点
