设计软件排行榜_微信企业邮箱_北京搜索优化推广公司_免费开网店免费供货

1.使用list中的部分函数

assign

功能一：当前链表的节点全部销毁，替换成迭代区间的值
功能二：当前链表的节点全部销毁，替换成 n 个 val

list<int> l1 = { 1,2,3,4 };
list<int> l2 = { 100,200,300,400 };l1.assign(l2.begin(), l2.end());
for (auto e : l1)
{cout << e << ' ';
}
cout << endl;
l1.assign(5, 2);
for (auto e : l1)
{cout << e << ' ';
}
cout << endl;

splice

功能一：把整个链表接在 position 这个迭代器的前面
功能二：把链表中的某一个迭代器接在 position 前
功能三：把链表中的某一段区间接在 position 前

list<int> l1 = { 1,2,3,4,500 };
list<int> l2 = { 100,200,300,400 };
l1.splice(--l1.end(), l2);
for (const auto& e : l1)
{cout << e << ' ';
}
cout << endl;l1 = { 1,2,3,4,500 };
l1.splice(--l1.end(), l2, l2.begin(), l2.end());
for (const auto& e : l1)
{cout << e << ' ';
}
cout << endl;l1 = { 1,2,3,4,500 };
list<int>::iterator it1 = find(l1.begin(), l1.end(), 500);
l1.splice(l1.begin(), l1, it1);
for (const auto& e : l1)
{cout << e << ' ';
}
cout << endl;

remove

删除某个元素

list<int> l1 = { 1,2,3,4,1,1,3 };
l1.remove(1);
for (auto e : l1)
{cout << e << ' ';
}
cout << endl;

unique

功能一：删除重复项
共能二：删除满足某些条件的的项。
使用前提：数据得先排序，再使用，否则会出现以下错误。（1和3 没有被删干净）

正确使用：

list<int> l1 = { 1,2,3,4,1,1,3 };
l1.sort();
l1.unique();
for (auto e : l1)
{cout << e << ' ';
}
cout << endl;

注意:
学习vector和string的时候排序是使用的< algorithm >中的sort
但是链表中为什么有自己的排序？
链表的迭代器是双向迭代器，它不支持随机访问。
所以链表中写了自己的排序
但是链表的排序太慢了，数据多的情况下一般不使用链表的排序。
先把链表的值赋给 vector 然后再用< algorithm >中的 sort 排序，把排序好的数据拷贝回 list 中即可

list<int> l1 = { 1,2,3,4,1,1,3 };
vector<int> v1(l1.begin(), l1.end());
sort(v1.begin(), v1.end());
l1.assign(v1.begin(),v1.end());l1.unique();
for (auto e : l1)
{cout << e << ' ';
}
cout << endl;

meger

合并两个有序链表
前提条件：这两个链表必须有序。

list<int> l1 = { 5,4,3,2,1 };
list<int> l2 = { 1,2,3,4,5 };
l1.sort();
l2.sort();
l1.merge(l2);
for (auto e : l1)
{cout << e << ' ';
}
cout << endl;

2.list的部分功能实现（重点）

框架

链表的节点，遍历的链表的头节点，链表的尾插

namespace cx
{template<class T>struct ListNode{T _data;ListNode<T>* _prev;ListNode<T>* _next;ListNode(const T& data = T()):_data(data), _prev(nullptr), _next(nullptr){}};template<class T>class list{public:typedef ListNode<T> Node;void empty_init(){_head = new Node;_head->_prev = _head;_head->_next = _head;}list(){empty_init();}void push_back(const T& x){Node* newnode = BuyNode(x);Node* tail = _head->_prev;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;tail->_next = newnode;}private:Node* _head;};
}

迭代器的实现

我们要想使用迭代器输出链表就得先实现迭代器

for(auto e:l1)
{cout << e << endl;
}

对于vector与string的迭代器可以直接使用 T* ，是因为vector与list元素间的地址是连续的。
但是链表的地址是随机的，使用 T*，迭代器++，迭代器会跳过node大小的字节，指向下一块地址，会野指针。
需要封装一下 node 使迭代器的++，就是指向node的下一个元素。
迭代器的具体实现如下。

template<class T,class Ref,class Ptr>
struct ListIterator
{typedef ListNode<T> Node;typedef ListIterator<T,Ref,Ptr> Self;Node* _node;ListIterator(Node* node):_node(node){}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}Ref operator*() {return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}
};

Ref 就是 reference 引用的意思，Ptr 就是返回一个指针
这样写的好处是，如果使用的对象是const类型，那么传值的时候就使用const类型。Ref与Ptr接收的就是const类型，返回的 Ref 与 Ptr 也是 const 类型

然后这个运算符的重载还需要理解一下

Ptr operator->()
{return &_node->_data;
}

有了迭代器的类，我们就可以写begin，end函数了

typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;iterator begin()
{return iterator(_head->_next);
}iterator end()
{return iterator(_head);
}const_iterator begin() const
{return const_iterator(_head->_next);
}const_iterator end() const
{return const_iterator(_head);
}