List
- list简介
- list基本框架
- list构造函数
- list_node结构体的默认构造
- list类的默认构造
- push_back()
- iteartor迭代器
- 迭代器里面的其他接口
- const迭代器
- 通过模板参数实现复用
- operator->()
- insert()
- erase()
- clear()
- 析构函数
- 迭代器区间构造
- 拷贝构造
- operator=()
list简介
- list可以在常数范围内在任意位置进行插入和删除的序列式容器,并且容器可以双向迭代。
- list底层是一个带头双向链表结构,通过指针连接前一个和后一个元素。
- list支持在任意位置进行插入、删除元素,效率更好。
- list不支持随机访问
list基本框架
namespace xty
{//带头双向循环链表template<class T>struct list_node{list_node<T>* _prev;list_node<T>* _next;T _data;};template<class T>class list{typedef list_node<T> node;private:node* _head;//头指针};
}
list构造函数
我们实现一个无参构造函数,但是在这之前我们需要做一些准备工作,先实现一个申请list_node的构造函数,在struct类里面实现。
list_node结构体的默认构造
//带头双向循环链表template<class T>struct list_node{list_node<T>* _prev;list_node<T>* _next;T _data;//在创建list_node变量时,自动调用构造list_node(const T& val = T()):_prev(nullptr),_next(nullptr),_data(val){}};
为什么不使用class,而使用struct呢?
因为我们想达到这样一个目的:想要让别人自由的访问自己的成员函数,不做任何限制,就用struct。而list_node,list是要经常使用的,因此使用struct修饰list_node比较方便。
list类的默认构造
仅仅申请一个空的头结点,next都指向头
list(){//两种申请方法都可以//_head = new list_node<T>_head = new node;_head->next = _head;_head->prev = _head;//_head->_data已经在new的时候调用构造了}
push_back()
先记录一下尾结点,插入更简单。
void push_back(const T& x){//留记录尾结点node* tail = _head->_prev;node* new_node = new node(x);//传入x值tail->_next = new_node;new_node->_next = _head;_head->_prev = new_node;new_node->_prev = tail;}
iteartor迭代器
整体框架:
//iteartortemplate<class T>struct __list_iterator{typedef list_node<T> node;node* _node;//成员变量//构造函数__list_iterator(node* x):_node(x){}T& operator*(){return _node->_data;}//++返回相应的迭代器__list_iterator<T> operator++(){_node = _node->_next;return *this;}//是位置是否相等,不是内容是否相等。bool operator!=(__list_iterator<T> x){return _node != x._node;}};template<class T>class list{typedef list_node<T> node;public://迭代器重命名typedef __list_iterator<T> iterator;public://仅仅申请一个空的头结点,next都指向头list(){//两种申请方法都可以//_head = new list_node<T>_head = new node;_head->_next = _head;_head->_prev = _head;//_head->_data已经在new的时候调用构造了了}iterator begin(){iterator it(_head->_next);return it;}iterator end(){return iterator(_head);}
语法细节理解:
- 为什么把iterator和list进行单独封装?写一块不好吗?
首先list只会用到迭代器的begin()和end()函数。其他的像++,其实都是通过迭代器的对象调用的(并不是list的对象调用的)。把iterator从list中抽离出来,不仅可以减少list的复杂性,还能让人更加清楚,迭代器其实也是一个模板,它能被抽离出来,用以实现各种数据结构的迭代!而list内部的begin和end接口,千篇一律。这样就达到的封装的目的!所以,还是分开写的好,逻辑更清晰,更容易维护。 - struct __list_iterator结构体里面为什么要写构造函数呢?
在c++里struct也被当做是类!类里有构造函数很正常,还可以有拷贝构造呢!只不过struct默认是public的。这样我们在声明该类型的变量时,函数会自动调用构造函数,使该结构体的数据自动是被初始化过的。
xty::list<int>::iterator it = lt.begin(); //调用对象需要用list//xty::list<int>::iterator it(lt.begin()); //调用对象需要用listwhile (it != lt.end()){cout << *it << endl;++it;}
写了构造函数之后,第二种声明方式也是可以的。而第一种方式其实调用的是拷贝构造函数,但是编译器给优化成了拷贝构造,我们没有写拷贝构造,编译器会调用默认的拷贝构造,是一个浅拷贝。但是我们不是经常说浅拷贝会造成析构问题?这里为什么不会?因为我们没有写析构函数,而且析构函数。为什么不写析构函数呢?因为没有什么可以析构的,函数的结点是list里的内容,不需要迭代器的析构函数管,因此我们不写析构函数。
- 迭代器++返回的是迭代器的类型。
- 注意:_list_iterator是类名,_list_iterator才是类型!
- list里面的begin要返回迭代器类型,然而怎么由指针转化成迭代器类型呢?要利用迭代器的构造函数来返回。
迭代器里面的其他接口
bool operator==(const __list_iterator<T>& x){return _node == x._node;}//i++__list_iterator<T> operator++(int){__list_iterator<T> tem(*this);_node = _node->_next;return tem;}__list_iterator<T> operator--(){_node = _node->_prev;return *this;}__list_iterator<T> operator--(int){__list_iterator<T> tem(*this);_node = _node->_prev;return tem;}
语法细节理解:
- 注意迭代器传进来的参数基本上都是迭代器,如果不更改,最好加上const和&。
- 如果命名空间冲突,注意在函数声明和定义的时候也要加上空间名。
void Print(xty::list<int>& lt);
- 我们发现__list_iterator 有点长,我们重命名一下。
//iteartortemplate<class T>struct __list_iterator{typedef list_node<T> node;typedef __list_iterator<T> self;node* _node;//成员变量//构造函数__list_iterator(node* x):_node(x){}T& operator*(){return _node->_data;}//++返回相应的迭代器self operator++(){_node = _node->_next;return *this;}//是位置是否相等,不是内容是否相等。bool operator!=(const __list_iterator<T>& x){return _node != x._node;}bool operator==(const __list_iterator<T>& x){return _node == x._node;}//i++self operator++(int){self tem(*this);_node = _node->_next;return tem;}self operator--(){_node = _node->_prev;return *this;}self operator--(int){self tem(*this);_node = _node->_prev;return tem;}};
const迭代器
要实现const迭代器只需要再写一个const类即可。
记住是指针可以修改,但是内容不可以修改,因此不能在this那加const。
//迭代器重命名typedef __list_iterator<T> iterator;typedef const__list_iterator<T> const_iterator;public:const_iterator begin()const{const_iterator it(_head->_next);return it;}const_iterator end()const{return const_iterator(_head);}
list里面的迭代器修改仅仅需要,typedef一下,然后将构造函数改成所需要的const类型即可。
而我们需要再实现一个const类型的iterator
template<class T>struct const__list_iterator{typedef list_node<T> node;typedef const__list_iterator<T> self;node* _node;//成员变量//构造函数const__list_iterator(node* x):_node(x){}const T& operator*() //值不仅可以修改!!{return _node->_data;}//++返回相应的迭代器self operator++() //指针可以修改!!{_node = _node->_next;return *this;}//是位置是否相等,不是内容是否相等。bool operator!=(const self& x)const{return _node != x._node;}bool operator==(const self& x)const{return _node == x._node;}//i++self operator++(int) //指针可以修改!!!{self tem(*this);_node = _node->_next;return tem;}self operator--() //指针可以修改!!!{_node = _node->_prev;return *this;}self operator--(int) //指针可以修改!!!{self tem(*this);_node = _node->_prev;return tem;}};
问题:代码写完之后,我们发现实际上只有operator*()的返回值加了const,其他的地方没有改,因此,我们利用模板参数赋用解决问题。
通过模板参数实现复用
template<class T,class Ref>struct __list_iterator{typedef list_node<T> node;typedef __list_iterator<T,Ref> self;node* _node;//成员变量//构造函数__list_iterator(node* x):_node(x){}Ref operator*(){return _node->_data;}...}template<class T>class list{typedef list_node<T> node;public://迭代器重命名typedef __list_iterator<T, T&> iterator;typedef __list_iterator<T,const T&> const_iterator;public://仅仅申请一个空的头结点,next都指向头list(){//两种申请方法都可以//_head = new list_node<T>_head = new node;_head->_next = _head;_head->_prev = _head;//_head->_data已经在new的时候调用构造了了}}
通过增加类模板参数,这种问题被很巧妙的解决了。请好好体会!
operator->()
当我们遇到自定义类型数据链表时,访问数据就会比较麻烦。
struct AA{int _a1;int _a2;AA(int a1 = 0, int a2 = 0):_a1(a1), _a2(a2){}};void test_aa(){xty::list<AA> lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));lt.push_back(AA(4, 4));xty::list<AA>::iterator it = lt.begin();while (it != lt.end()){cout << (*it)._a1 << ":" << (*it)._a2 << endl;++it;}}
如上例子所示,cout方式,在这里很是别扭,因为it是迭代器,我们能不能通过重载->来访问这样的数据呢?
显然是可以的!如下:
T* operator->(){return &(_node->_data);}
所以我们通过如下方式打印链表的数据:
xty::list<AA>::iterator it = lt.begin();while (it != lt.end()){//cout << (*it)._a1 << ":" << (*it)._a2 << endl;cout << it->_a1 << ":" << it->_a2 << endl;++it;}
但是这个代码是不是有一点别扭?没看出来的话,我再打印一次:
//两种打印方式一样!!!cout << it->_a1 << ":" << it->_a2 << endl;cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl;
==解释:==之所以出现这样的原因,是因为编译器自动把两个连续的->优化成一个->,防止观感上的差异,这样设计能让人立马看出这个其实是在访问AA的数据。
为了适应const和非const两种迭代器,我们再设计一个模板参数。如下实例:
//iteartortemplate<class T,class Ref, class Ptr>struct __list_iterator{typedef list_node<T> node;typedef __list_iterator<T,Ref,Ptr> self;node* _node;//成员变量Ptr operator->(){return &(_node->_data);}
...................}
template<class T>class list{typedef list_node<T> node;public://迭代器重命名typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T,const T&,const T*> const_iterator;public:
insert()
//在pos位置前插入,返回插入位置的迭代器iterator insert(iterator pos, const T& x){node* new_node = new node(x);node* cur = pos._node;node* prev = cur->_prev;prev->_next = new_node;new_node->_prev = prev;new_node->_next = cur;cur->_prev = new_node;return iterator(cur);}
erase()
返回删除元素的下一个位置的迭代器。
iterator erase(iterator pos){//不能删头assert(pos._node!=_head);node* cur = pos._node;node* prev = cur->_prev;prev->_next = cur->_next;cur->_next->_prev = prev;delete cur;return iterator(prev->_next)}
注意:删除元素后,pos位置的数据就被删除了,会产生迭代器失效问题,如果再使用pos需要重新赋值。
clear()
清空list的内容,可以借助迭代器和erase()来删除。
void clear(){iterator it = begin();while (it != end()){it = erase(it);//erase(it++);}}
析构函数
结合clear()来编写。
~list(){clear();delete _head;_head = nullptr;}
迭代器区间构造
因为迭代器区间构造,也需要一个头结点,所以,我们方便复用,又定义了一个初始化函数,具体改动如下:
list(){empty_init();//两种申请方法都可以//_head = new list_node<T>//_head = new node;//_head->_next = _head;//_head->_prev = _head;//_head->_data已经在new的时候调用构造了了}void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}template<class Iterator>list(Iterator first, Iterator last){empty_init();while (first != last){push_back(*first);++first;}}
拷贝构造
提供了两种方法,第一种方法效率较低,第二种利用swap提高了效率。
lt2(lt)//list(const list<T>& lt)//{// empty_init();// for (auto e : lt)// {// push_back(e);// }//}void swap(list<T>& tem){std::swap(_head, tem._head);}list(const list<T>& lt){empty_init();//初始化thislist<T> tem(lt.begin(), lt.end());swap(tem);}
operator=()
实现较为简单。
//注意这里不能传引用list<T>& operator=(list<T> lt){swap(lt);return *this;}
最后一个问题:
const list<int> lt;
这行代码能调用构造函数吗?
答案是肯定的,因为变量在最开始是没有const属性的,定义好了以后,才有const属性。否则const都没法定义出来了。