【C++强基篇】学习C++就看这篇---＞STL之list使用及实现

#include <list>  // 必须包含的头文件
using namespace std; // 或显式使用 std::list

std::list<int> lst1;             // 空链表
std::list<int> lst2(5, 100);     // 5个值为100的元素
std::list<int> lst3 = {1, 2, 3}; // 初始化列表 (C++11)
std::list<int> lst4(lst3);       // 拷贝构造
std::list<int> lst5(arr, arr+3); // 从数组构造 [C风格]

// 双向迭代器
for (auto it = lst1.begin(); it != lst1.end(); ++it) {
    // 前向遍历
}

for (auto rit = lst1.rbegin(); rit != lst1.rend(); ++rit) {
    // 反向遍历
}

// C++11 范围for循环
for (int val : lst1) {
    // 顺序访问
}

bool empty = lst1.empty();  // 是否为空
size_t size = lst1.size();  // 元素数量
lst1.resize(10);           // 调整大小 (增/删尾部元素)

int front = lst2.front();  // 首元素 (不检查空)
int back = lst2.back();    // 尾元素 (不检查空)

// 迭代器访问 (无随机访问操作符 [])
auto it = lst3.begin();    // 指向第一个元素
std::advance(it, 2);       // 移动迭代器 (O(n))
int val = *it;             // 获取值

// 添加元素
lst1.push_front(10);      // 头部插入
lst1.push_back(20);       // 尾部插入
auto pos = lst1.begin();
lst1.insert(pos, 15);     // 指定位置插入

// 删除元素
lst1.pop_front();         // 删除头部
lst1.pop_back();          // 删除尾部
lst1.erase(pos);          // 删除指定位置
lst1.remove(100);         // 删除所有值为100的元素
lst1.clear();             // 清空链表

// 链表专有操作
lst1.splice(lst1.end(), lst2);  // 将lst2所有元素移动到lst1尾部
lst1.merge(lst3);        // 合并有序链表 (需先排序)
lst1.sort();             // 排序 (成员函数)
lst1.reverse();          // 反转链表

    template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		//const迭代器就是不能修改，但是如果要写的话就必须重新再写一个类型，这样代码复用率不高，因此下面就有一个很巧妙的写法
		typedef __list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> Self;
		Node* _node;

		__list_iterator(Node* node)
			:_node(node)
		{}
		Ref operator*()
		{
			return _node->_data;
		}
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		Self& operator++(int)
		{
			Self tmp(*this);
			//_node = _node->_next;
			++(*this);
			return tmp;
		}
		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		Self& operator--(int)
		{
			Self tmp(*this);
			//_node = _node->_next;
			--(*this);
			return tmp;
		}
		bool operator!=(const Self& it)
		{
			return _node != it._node;
		}
	};

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

        void insert(iterator pos, const T& x)
      	{
			Node* newnode = new Node(x);
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
		}
		iterator erase(iterator pos)
		{
			assert(pos != end());
			Node* cur = pos._node;
			Node* next = cur->_next;
			Node* prev = cur->_prev;
			prev->_next = next;
			next->_prev = prev;
			delete cur;
			cur = nullptr;
			return iterator(next);
		}
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

int a = 10;       // a 是左值
int* p = &a;      // 可以对左值取地址

42;               // 字面量是右值
a + 5;            // 表达式结果是右值
func();           // 函数返回的临时对象是右值

int x = 10;
int& ref1 = x;    // 正确：绑定到左值

int& ref2 = 42;   // 错误！不能绑定到右值
int& ref3 = x+5;  // 错误！不能绑定到右值