【C++】STL：list

阿巴阿巴，list的博客来喽！

[TOC]

1.list是嘛玩意？

之前的vector是一个顺序表。总所周知，学完顺序表肯定不能不学链表，所以list就来了！

list是一个可以在任何地方进行插入删除的序列式容器，可以进行前后双向迭代

说人话就是：list是一个双向带头循环链表

这不巧了嘛！之前我写过用C语言实现双向带头循环链表的博客

其优缺点也很明显

支持快速插入删除O(1)
支持前后双向迭代访问
不支持任意位置的随机访问

STL中的list也满足上面的这些优缺点

话不多说，来看看list的函数接口吧！

https://m.cplusplus.com/reference/list/list/

函数接口

大部分接口和前面所学的两个容器都是一样的啦，这里就不贴完整截图了（见上方链接）

这里还多了一个emplace_front，看完函数解释后可知它也是一个头插

2.简单了解使用

2.1构造

list支持的构造函数如下

这些函数和vector完全一致，这里就不过多介绍了

2.2迭代器

迭代器	说明
begin+end	获取第一个数据位置iterator/const_iterator，获取最后一个数据的下一个位置iterator/const_iterator
rbegin+rend	获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的 reverse_iterator

都是老样子，没有啥好说的

除了迭代器以外，一般的容器都会提供front和back两个参数来访问头部/尾部数据。但是我们并不常用这个，迭代器用的更多一些

2.3长度操作

库函数中给我们提供了两个和list长度相关的操作，因为是链表，所以也不存在扩容问题，每一个节点都是一个独立的空间

empty 判断是否为空，是空返回true
size 计算list中有效数据长度

关于插入和删除操作，list和vector/string基本都是一致的，学会一个基本都会用！

2.4迭代器失效问题

和vector一样，list也会遇到一定程度的迭代器失效问题。

因为list是一个链表，其在插入操作的时候是在迭代器所指节点前一个位置进行插入，不会影响该节点和这个节点之后的结构，也不会导致迭代器失效。

只有在删除的时候才会导致迭代器失效

解决办法也很简单，使用迭代器删除数据的时候，接收返回值更新一下迭代器即可！

基本了解了函数接口后，让我们来试试模拟实现吧！

3.模拟实现

模拟实现和STL-list源码见我的Gitee

下图是之前C语言版本链表博客里，我画的双向带头循环链表的结构图

list的结构和这个图片是一样的。但因为我们现在所使用的是C++中的类和对象，所以我们的操作都需要尊崇stl库的命名规则和使用方法，其结构的实现也会有所不同。

比如在STL源码中可以看到，list的主结构中只有一个node，即头节点。

3.1 节点结构

在list中，我们不直接在list主类中放入单个节点的结构，而是使用一个自定义类型作为节点。

复习：在struct中，成员默认是共有

template<class T>
   struct list_node
   {
       list_node<T>* _next;
       list_node<T>* _prev;
       T _data;

       list_node(const T& val = T())
           :_next(nullptr),
       	_prev(nullptr),
       	_data(val)
       {}
   };

这样后面的插入删除操作就可以直接new一个新的node，并调用构造函数完成_data的赋值。

在list的主类中，我们遵循库的方法，只用一个头节点的指针作为成员

1 2	private: Node* _head;//头节点指针

3.2 插入删除

因为之前写过C语言的代码，关于插入和删除操作相对较为熟练，代码如下👇

//在pos之前插入
iterator insert(iterator pos, const T& x)
{
    Node* newnode = new Node(x);
    Node* cur = pos._node;


    newnode->_next = cur;
    cur->_prev->_next = newnode;
    newnode->_prev = cur->_prev;
    cur->_prev = newnode;

    return iterator(newnode);
}
//删除pos位置
iterator erase(iterator pos)
{
    assert(_head->_next != _head && pos._node!=_head);
    Node* next = pos._node->_next;
    Node* prev = pos._node->_prev;

    prev->_next = next;
    next->_prev = prev;

    delete pos._node;

    return iterator(next);
}

而头插/头删/尾插/尾删这类方法，我们直接复用insert和earse即可！

3.3 迭代器（重要）

在上面的插入和删除代码中，我已经使用了迭代器作为参数和返回值。由于list的主类中并没有直接存放3.1节点结构，我们需要自己单独完成一个迭代器的类，来实现迭代器的相关操作

vector/string是顺序表，迭代器可以直接用指针替代，在本类中模拟实现
list是顺序表，迭代器的+和-操作其实是通过next和prev指针往后往前找内容，所以需要单独的模拟实现

在STL源码中的list也是单独重载了一个迭代器类

其基本结构如下

template<class T, class Ref, class Ptr>
struct __list_iterator
{
    typedef list_node<T> Node;//节点结构
    typedef __list_iterator<T, Ref, Ptr> self;//本类
    Node* _node;//存放节点指针
    
    __list_iterator(Node* node)
		:_node(node)
	{}
}

这里解释一下为何有3个模板参数：ref指代引用，ptr指代指针

因为在后续的操作中我们需要传入T的引用T&和指针T*，如果之传入一个T，编译器无法确认是否为const类型，也就无法阻止用户使用迭代器修改值，成员的数据就不够安全，且const的成员函数无法调用迭代器。

重载3个模板参数后，我们就可以用传入的模板参数来控制指针和引用是否为const类型

1 2	typedef __list_iterator<T, T&, T> iterator; typedef __list_iterator<T, const T&, const T> const_iterator;

基本的结构弄清楚之后，下面一起来看看，迭代器的++和--，解引用以及指针->分别对应了链表的什么操作呢？

3.3.1 加减

好吧，前面已经提到过了，我们需要用next/prev指针来完成加减操作

//前置++
self& operator++()
{
    _node = _node->_next;
    return *this;
}
//后置++
self operator++(int)
{
    //self是本类的别名，因为没有重载=操作符
    //所以不能使用相等，要用构造函数
    //self tmp = _node;
    self tmp(*this);
    _node = _node->_next;
    return tmp;
}
//前置--
self& operator--()
{
    _node = _node->_prev;
    return *this;
}
//后置--
self operator--(int)
{
    self tmp(*this);
    _node = _node->_prev;
    return tmp;
}

注意前置和后置的区别，后置加减需要先用一个tmp变量储存原本的迭代器位置，再让迭代器指向下一个节点

而当我们解引用迭代器的时候，想获取的其实是_data的值，而不是节点的地址（这里迭代器依旧是用指针模拟的）

3.3.2 解引用和指针操作

所以重载后的解引用操作如下

Ref operator*()
{
    return _node->_data;//返回值的引用
}
Ptr operator->()
{
    return &(_node->_data);//返回地址
}

3.3.3 判断相等/不相等

最后判断相等和不相等就很简单了，因为本身就是指针，我们直接调用原生的!=进行判断即可

bool operator!=(const self& it)
{
    return _node != it._node;
}
bool operator==(const self& it)
{
    return _node == it._node;
}

到这里，一个建议版本的正向迭代器我们就实现啦！

3.3.4 begin/end

这里我们需要在List的本类中获取迭代器的begin和end，这里我们是调用了迭代器的构造函数，构造出来一个迭代器并进行返回

const_iterator begin() const
{
    //return _head->_next;//不能直接返回指针！！
    return const_iterator(_head->_next);
}
const_iterator end() const
{
    return const_iterator(_head);
}

iterator begin()
{
    return iterator(_head->_next);
}
iterator end()
{
    return iterator(_head);
}

现在就可以愉快的用迭代器进行打印操作了！

3.4 构造函数

有了迭代器，现在就可以完成库函数里面的几个构造函数了（主要是迭代器区间的那个函数）

默认构造函数如下，先创建一个头节点，再让它的前后都指向自己。在C语言的初始化函数中，我们也是这么做的

list()
   	:_head(nullptr)
   {
       //_head = new Node;
       _head = new Node();
       _head->_next = _head;
       _head->_prev = _head;
   }

但其他的构造函数由于_head为空，所以我们需要单独实现一个空初始化函数来创建头节点

//当使用其他构造函数的时候，head还不存在，需要手动构造一个
void empty_init()
{
    _head = new Node();
    _head->_next = _head;
    _head->_prev = _head;
}

当然，上面那个空的构造函数list()也可以复用empty_init()，这样代码更整洁

迭代器区间构造和vector是一样的，其主要是解引用后直接将值进行头插（这里就用上了之前迭代器里重载的解引用操作）

template <class InputIterator>
list(InputIterator first, InputIterator last)
{
    empty_init();
    InputIterator cur = first;
    while (cur != last)
    {
        //push_back(cur._node->_data);
        push_back(*cur);
        cur++;
    }
}

而拷贝构造就可以直接复用迭代器区间构造，赋值重载就直接swap即可。这部分的实现和vector是一样的，有问题可以在评论区提出哦！

void swap(list<T>& lt)
{
    std::swap(_head, lt._head);
}

list(const list<T>& lt)
{
    empty_init();
    list tmp(lt.begin(), lt.end());
    swap(tmp);
}

list<T>& operator=(list<T> lt)
{
    //传参没有传引用，lt已经是拷贝构造之后的结果了
    //完全没必要再用tmp拷贝构造一次
    //list<T> tmp(lt);
    //clear();//因为tmp出了生命周期后会销毁，所以不需要手动clear
    swap(lt);

    return *this;
}

3.5 析构函数

因为链表需要我们一个一个去删除每一个节点的空间，这里需要单独实现一个clear函数供析构函数使用

void clear()
{
    //assert(_head->_next != _head);
    iterator it = begin();
    while (it != end())
    {
        //需要用一个临时变量储存该节点的迭代器，避免迭代器失效
        iterator its = it;
        it++;
        delete its._node;
    }
}

~list()
{
    clear();
    delete _head;
}

上面这个函数就有些麻烦，我们其实可以直接复用erase进行删除操作+更新迭代器！

void clear()
{
    iterator it = begin();
    while (it != end())
    {
        it = erase(it);
    }
}

到这里，一个基本的list就模拟实现完成了！

3.6 操作自定义类型

我们刚刚实现的list和STL库中的一样，都可以存放自定义类型

struct TA
{
	TA(int a1 = 0, int a2 = 0)
		:_a1(a1),
		_a2(a2)
	{}

	int _a1;
	int _a2;
};

void test03()
{
	list<TA> lt;
	lt.push_back(TA(1, 1));
	lt.push_back(TA(2, 2));
	lt.push_back(TA(3, 3));
	lt.push_back(TA(4, 4));

	//这里因为TA类的流插入没有重载，所以需要我们手动写
	list<TA>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << it->_a1 << "-" << it->_a2 << " ";
		++it;
	}
	cout << endl;
}

但在打印和访问自定义类型的时候，我们重载的解引用操作符就不能用了，这就是为啥要重载->操作符，此时我们还可以通过->获取到迭代器所指的对象的成员，这时候直接打印成员变量即可！

你可能觉得，这不对啊！之前重载的这个操作符不是返回的节点_data的地址吗？为啥可以直接访问_data的成员？

Ptr operator->()
{
    return &(_node->_data);//返回地址
}

实际上，这里应该是it->->_a1，但是编译器在处理的时候直接将两个访问箭头简化成了一个，即增加了代码可读性，也方便使用了！

3.7 反向迭代器（适配问题）

关于反向迭代器，这里牵扯到一个更深的适配问题。我用我的笨话稍微解释一下，有问题或者有啥错误的话欢迎在评论区提出！😂

我们知道，反向迭代器是从后往前走的，它的加减操作和正向迭代器相反。

那么比起单独实现一个反向迭代器的类，我们可否利用正向迭代器，直接适配出一个反向迭代器呢？毕竟看起来它们只有方向不同！

3.7.1 显式规定模板参数Ref和Ptr

template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
	Iterator _it;
	typedef Reverse_iterator<Iterator, Ref, Ptr> Self;
       
       Reverse_iterator(Iterator it)
		:_it(it)
	{}
   };

说上就上，这里我们先将反向迭代器设定为和正向相似的结构，不过它的模板参数变成了正向迭代器，而不是参数类型T，这在后续typdef的时候需要注意（不然会报错）

除了下面的解引用操作之外，其他只需要吧正向迭代器反过来用，就可以达到我们的目的！

Ref operator*()
{
    Iterator tmp = _it;
    return *(--tmp);//反向迭代器解引用访问的是前一个位置的数据
}

Ptr operator->()
{
    return &(operator*());
}

解引用访问前一个数据的原因是，我们判断结束是用!=rend()，而rend()指向的是列表的第一个有效数据，如果直接解引用当前内容，最后一个数据就无法访问到，出现了缺漏

//前置++
Self& operator++()
{
    --_it;
    return *this;
}
//前置--
Self& operator--()
{
    ++_it;
    return *this;
}
bool operator!=(const Self& s)
{
    return _it != s._it;
}

更加完整的源码可以去看我的Gitee仓库哦！

完成了上面的代码后，我们需要在list本类里面进行一波操作，让它能够支持反向迭代器

1
2
3

//支持反向迭代器
typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;

注意上面的模板参数，第一个模板参数需要传入正向迭代器，而不是T

//调用反向迭代器的构造函数
reverse_iterator rbegin()
{
    return reverse_iterator(end());
}
reverse_iterator rend()
{
    return reverse_iterator(begin());
}
const_reverse_iterator rbegin()const
{
    return const_reverse_iterator(end());
}
const_reverse_iterator rend()const
{
    return const_reverse_iterator(begin());
}

用一个打印代码便可以测试出我们的操作是否正确！

可以看到，完美逆向打印出了内容！

利用正向迭代器进行适配的最大好处，那就是其他模拟实现的容器也可以直接调用这个反向迭代器，只要在本类中加入上面的typedef和4个函数即可！

就以上篇博客的vector为例，加上上述代码后，她也能支持反向迭代器了！（源码也上传到仓库里面了）

3.7.2 调用正向迭代器中的类型

除了在反向迭代器的模板定义中直接定义反向迭代器中Ref/Ptr这两个参数类型，还可以从正向迭代器中去取出来这两个参数的类型；

首先需要在正向迭代器__list_iterator中新增如下两个typedef

1
2
3

// 为了让反向迭代器能统一获取到Ref和Ptr，标准库中的迭代器都定义了这两个typedef
typedef Ptr pointer;
typedef Ref reference;

能看到stl的list迭代器源码中同样存在这两个typedef

随后在反向迭代器中，可以按下下面的方式写来取出正向迭代器中的类型

template<class Iterator, class Ref, class Ptr>
struct Reverse_iterator
{
	Iterator _it;
	typedef Reverse_iterator<Iterator, Ref, Ptr> Self;

	Reverse_iterator(Iterator it)
		:_it(it)
	{}

	// 从正向迭代器里面取迭代器中Ref和Ptr的类型
	Iterator::reference operator*()
	{
		Iterator tmp = _it;
		return *(--tmp);//反向迭代器解引用访问的是前一个位置的数据
	}

	Iterator::pointer operator->()
	{
		return &(operator*());
	}
}

在list的主体中，还需要将反向迭代器的定义修改为如下形式

1
2
3

//支持反向迭代器
typedef Reverse_iterator<iterator> reverse_iterator;
typedef Reverse_iterator<const_iterator> const_reverse_iterator;

此时直接执行g++进行编译，会报错如下内容，说让我们在类型前面添加一个typename；

这是我们第二次遇到typename关键字，上一次遇见是在模板中的模板参数声明。

在这里typename的作用是告诉编译器Iterator::reference是一个类型，需要等正向迭代器Iterator的这个模板类成功实例化了之后，再去查看这个参数的类型是什么。如果不加上这个关键字，编译器会立马去康这个参数的类型，结果发现这玩意是个模板参数，压根没办法知道类型是什么，那就只能给你报错了。

typename Iterator::reference operator*()
{
	Iterator tmp = _it;
	return *(--tmp);//反向迭代器解引用访问的是前一个位置的数据
}

typename Iterator::pointer operator->()
{
	return &(operator*());
}

加上typename后重新编译，此时就没有出现报错了。

//通过迭代器打印链表
	void print_list(list<int>& s)
	{
		list<int>::iterator it = s.begin();
		while (it != s.end())
		{
			//*it = 10;//使用非const迭代器的时候可以修改值
			cout << *it << " ";
			it++;
		}
		cout << endl;
	}

	void R_print_list(list<int>& s)
	{
		list<int>::reverse_iterator it = s.rbegin();
		while (it != s.rend())
		{
			cout << *it << " ";
			it++;
		}
		cout << endl;
	}

	void test01()
	{
		list<int> s1;
		s1.push_back(1);
		s1.push_back(2);
		s1.push_back(3);
		s1.push_back(4);

		print_list(s1);
		R_print_list(s1);
    }

执行一下测试代码，能看到其成功实现了正向迭代器和反向迭代器的使用操作。

1
2
3

$ ./test
1 2 3 4 
4 3 2 1

我们还可以在反向迭代器中再进行一层typedef，将正向迭代器中的类型改个名字。在typedef中同样需要加上typename

template<class Iterator>
struct Reverse_iterator
{
	Iterator _it;
	//typedef Reverse_iterator<Iterator, Ref, Ptr> Self;
	typedef Reverse_iterator<Iterator> Self;

	// 再进行一层typedef（同样需要带上typename）
	typedef typename Iterator::reference reference;
	typedef typename Iterator::pointer pointer;


	Reverse_iterator(Iterator it)
		:_it(it)
	{}

	// 可以查看下面这个截图里面的说明
	// https://img.musnow.top/i/2023/12/65785f40a03b4.png
	// 从正向迭代器里面取迭代器中Ref和Ptr的类型
	reference operator*()
	{
		Iterator tmp = _it;
		return *(--tmp);//反向迭代器解引用访问的是前一个位置的数据
	}

	pointer operator->()
	{
		return &(operator*());
	}
       // 其他部分和3.7.1是相同的
   }

编译成功，无报错

3.7.1中的方式vector同样可以使用，但vector是不能使用3.7.2里面的这种方式来进行反向迭代器的适配的。

这是因为在自主实现vector的操作中，我们使用了原生的类型指针来作为迭代器；此时我们是没有办法在指针（内置类型）里面定义typedef Ptr pointer的，也就没有办法获取到这个迭代器的指针和引用的类型，自然也就没有办法使用typename的方式让编译器来帮我们推测反向迭代器中Ptr/Ref的类型了。

template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		//支持反向迭代器
		typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;
		typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
    	//...
    }

要想解决这个问题，有三种解决办法

和list的自主实现一样，不使用内置类型，而是再制作一个自定义类型作为vector的迭代器
而STL中使用了一个较为复杂的解决办法，即特化和萃取（这两个有点难理解，会在模板的进阶博客中说明）
参考3.7.1，在反向迭代器的模板参数填入Ref/Ptr这两个模板参数

3.7.3 typename

上文中提到，typename是用于告知编译器该参数名是一个类型，需要在模板实例化之后再去查看具体的类型是什么。下面是一个简单的测试用例来复现这个场景

#include<iostream>
#include<list>
#include<string>
using namespace std;

template<class T>
void print_list(const list<T>& lt)
{
	list<T>::const_iterator cit = lt.begin();
	while (cit != lt.end())
	{
		cout << (*cit) << " ";
		cit++;
	}
	cout << endl;
}

template<class Container>
void print_container(const Container& lt)
{
	Container::const_iterator cit = lt.begin();
	while (cit != lt.end())
	{
		cout << (*cit) << " ";
		cit++;
	}
	cout << endl;
}

void test_print_list()
{
	list<int> lt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);
	lt1.push_back(4);

	print_list(lt1);
	print_container(lt1);

	list<string> lt2;
	lt2.push_back("a");
	lt2.push_back("b");
	lt2.push_back("c");
	lt2.push_back("d");

	print_list(lt2);
	print_container(lt2);
}

上面代码中的两个函数，都尝试直接获取了模板类型中的const_iterator迭代器作为cit参数的类型，直接编译会出现如下的报错

$ g++ test.cpp -o test -std=c++11
test.cpp: In function ‘void print_list(const std::__cxx11::list<T>&)’:
test.cpp:11:2: error: need ‘typename’ before ‘std::__cxx11::list<T>::const_iterator’ because ‘std::__cxx11::list<T>’ is a dependent scope
  list<T>::const_iterator cit = lt.begin();
  ^~~~~~~
test.cpp:11:25: error: expected ‘;’ before ‘cit’
  list<T>::const_iterator cit = lt.begin();
                         ^~~~
                         ;
test.cpp:12:9: error: ‘cit’ was not declared in this scope
  while (cit != lt.end())
         ^~~
test.cpp: In function ‘void print_container(const Container&)’:
test.cpp:23:2: error: need ‘typename’ before ‘Container::const_iterator’ because ‘Container’ is a dependent scope
  Container::const_iterator cit = lt.begin();
  ^~~~~~~~~
test.cpp:23:27: error: expected ‘;’ before ‘cit’
  Container::const_iterator cit = lt.begin();
                           ^~~~
                           ;
test.cpp:24:9: error: ‘cit’ was not declared in this scope
  while (cit != lt.end())
         ^~~
test.cpp: In instantiation of ‘void print_list(const std::__cxx11::list<T>&) [with T = int]’:
test.cpp:40:16:   required from here
test.cpp:11:2: error: dependent-name ‘std::__cxx11::list<T>::const_iterator’ is parsed as a non-type, but instantiation yields a type
  list<T>::const_iterator cit = lt.begin();
  ^~~~
test.cpp:11:2: note: say ‘typename std::__cxx11::list<T>::const_iterator’ if a type is meant
test.cpp: In instantiation of ‘void print_container(const Container&) [with Container = std::__cxx11::list<int>]’:
test.cpp:41:21:   required from here
test.cpp:23:2: error: dependent-name ‘Container::const_iterator’ is parsed as a non-type, but instantiation yields a type
  Container::const_iterator cit = lt.begin();
  ^~~~~~~~~
test.cpp:23:2: note: say ‘typename Container::const_iterator’ if a type is meant
test.cpp: In instantiation of ‘void print_list(const std::__cxx11::list<T>&) [with T = std::__cxx11::basic_string<char>]’:
test.cpp:49:16:   required from here
test.cpp:11:2: error: dependent-name ‘std::__cxx11::list<T>::const_iterator’ is parsed as a non-type, but instantiation yields a type
  list<T>::const_iterator cit = lt.begin();
  ^~~~
test.cpp:11:2: note: say ‘typename std::__cxx11::list<T>::const_iterator’ if a type is meant
test.cpp: In instantiation of ‘void print_container(const Container&) [with Container = std::__cxx11::list<std::__cxx11::basic_string<char> >]’:
test.cpp:50:21:   required from here
test.cpp:23:2: error: dependent-name ‘Container::const_iterator’ is parsed as a non-type, but instantiation yields a type
  Container::const_iterator cit = lt.begin();
  ^~~~~~~~~
test.cpp:23:2: note: say ‘typename Container::const_iterator’ if a type is meant

取其精华，能看到最主要的报错是 ‘cit’ was not declared in this scope，意思是cit这个变量在当前作用域中没有声明。

这不就很奇怪了，明明我已经声明了这个参数了呀，还给他赋值了！

原因前面便提到过了，这是因为编译器没有办法推测出这两个模板参数在未实例化之前的变量类型，此时可以理解为这个模板中的类型是一个虚拟类型，并非真实确定了的参数类型。最终就导致cit参数看似实例化了，实际上并没有。

1
2
3

// cit 变量到底是什么类型？不知道！
Container::const_iterator cit = lt.begin();
list<T>::const_iterator cit = lt.begin();

我们要做的就是给这两个变量的声明都加上typename的关键字

template<class T>
void print_list(const list<T>& lt)
{
	typename list<T>::const_iterator cit = lt.begin();
	while (cit != lt.end())
	{
		cout << (*cit) << " ";
		cit++;
	}
	cout << endl;
}

template<class Container>
void print_container(const Container& lt)
{
	typename Container::const_iterator cit = lt.begin();
	while (cit != lt.end())
	{
		cout << (*cit) << " ";
		cit++;
	}
	cout << endl;
}

此时编译和运行都成功了。

[muxue:~/code/c/c_cpp/cpp/22-07-14 list/reverse_iterator]$ g++ test.cpp -o test -std=c++11
[muxue:~/code/c/c_cpp/cpp/22-07-14 list/reverse_iterator]$ ./test
1 2 3 4 
1 2 3 4 
a b c d 
a b c d

当然，如果我们类模板的参数类型的确定的，那就不需要有typename关键字；比如下方list已经确定是int类型了，那么迭代器的类型自然也是可以被确定下来的。

void print_list_int(const list<int>& lt)
{
	list<int>::const_iterator cit = lt.begin();
	while (cit != lt.end())
	{
		cout << (*cit) << " ";
		cit++;
	}
	cout << endl;
}

编译无报错

1 2	[muxue:~/code/c/c_cpp/cpp/22-07-14 list/reverse_iterator]$ g++ test.cpp -o test -std=c++11 [muxue:~/code/c/c_cpp/cpp/22-07-14 list/reverse_iterator]$

当然，使用auto关键字也是可以的的，不会报错，也不需要带上typename；这是因为auto已经告诉了编译器这里是一个参数类型，只需要在lt.begin()返回的时候，根据返回值的参数来取cit变量的参数类型就可以了。

template<class T>
void print_list_auto(const list<T>& lt)
{
	auto cit = lt.begin();
	while (cit != lt.end())
	{
		cout << (*cit) << " ";
		cit++;
	}
	cout << endl;
}

测试一下

void test_print_list()
{
	list<int> lt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);
	lt1.push_back(4);

	print_list(lt1);
	print_list_int(lt1);
	print_list_auto(lt1);
	print_container(lt1);
}

结果

[muxue:~/code/c/c_cpp/cpp/22-07-14 list/reverse_iterator]$ g++ test.cpp -o test -std=c++11
[muxue:~/code/c/c_cpp/cpp/22-07-14 list/reverse_iterator]$ ./test
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4

我们要记住的是：只要从未实例化的类模板中取参数类型，都需要加上typename关键字来指定！