植物大战 List——C++

vector和stirng的细节

复习vector的深浅拷贝。

下图是vector<vector< int>> 的底层模型
实际和动态二维数组的图一样。

vv[i][j] 表示什么意思？
vv[ i]表示访问第几个vector,
vv[i][ j]表示访问第i个vector的第j个下表的元素。

对于string

class string
{
private:char _buf[16];char* _ptr;size_t _size;size_t _capacity;
}

string设计如下，string在设计时用了一个buf的数组，buf大小是16，最后一个空间是给\0的。

这样设计的目的是小于16byte的字符串，存在buf数组中。大于等于16的字符串存在_ptr指向的空间。

list的使用

概念：list是一个容器，允许在常数O(1)时间，在任意位置进行insert和erase。他的迭代器是双向的。

链表在使用上和vector和string差不多。

因为支持O（1）的时间，所以它是双向循环链表的数据结构。

如图

对于迭代器的位置，begin()是第一个元素的位置，end()是最后一个元素的下一个位置，也就是哨兵位头结点。

list的迭代器

对于list为什么要学迭代器？
对于string和vector来说，使用的是原生指针，所以迭代器是原生的，对于list，我们也要封装迭代器，因为list底层是地址，不是连续的地址。为了方便用户操作，比如for循环遍历，范围for等。

小细节：因为list的结构，所以while循环内不能用小于<,因为都是地址，地址不能比大小，迭代器的条件都是不等于!=

 void test1()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;
}

反向迭代器

rbegin()就是最后一个元素的下一个位置。

auto rit = lt.rbegin();while (rit != lt.rend()){cout << *rit << " ";++rit;}

构造函数

四个：无参的构造，n个value的构造，迭代器区间构造，拷贝构造。

和vector非常相似不说，查文档。

关于list::sort的排序

如果大量的排序不建议用list自带的。可以用vector进行排序。
对于std算法库里面的sort，需要传随机迭代器才可以使用。

但是list不支持随机访问，list的迭代器是双向迭代器。

list lt;
lt.sort();

对于迭代器实际上分为三类。
1.单向。++ forward_list
2.双向。致辞 ++ – list
3.随机。支持++ – + - vector

所以要求传双向迭代器的，也可以传随机迭代器。

总结：list不支持随机迭代器，他是双向迭代器，不能用库的sort的原因是因为，库里的sort用的快排，快排用的是随机访问，所以一般不用链表进行排序。

解决方法：可以先把数据转移到vector中排序后，再转移到list中。

unique

这个函数的作用是用来去重。

但是去重是有条件的，他只能对排序的list进行去重

list的底层模拟实现

结点类的实现

	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){}};

迭代器模拟实现

因为底层空间不连续，地址不连续，所以需要封装迭代器

用模板T的原因是迭代器里封装了结点的指针。

版本1

template <class T>
struct _list_iterator
{typedef list_node<T> Node;Node* _node;T& operator*(){return _node->_data;}}

const迭代器，一般写法就是再定义一个const迭代器的类。这样复用性很差。达不到软件工程复用的思想。

大神写法就是用模板参数 来控制。

这里不用管第一个参数T，第一个参数是数据类型，比如int，只用控制解引用和箭头访问数值的就行。也就是控制Ref和 Ptr

const迭代器第一个位置不加const的原因是因为：需要保持一致的类型。因为在begin()函数中用结点的指针构造迭代器时，传递的是int的类型。但是模板传递过去是cosnt int类型。这时候类型不匹配。

//迭代器实现

	// typedef __list_iterator<T, T&, T*> iterator;// typedef __list_iterator<T, const T&, const T*> const_iterator;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){}// 析构函数  -- 节点不属于迭代器，不需要迭代器释放// 拷贝构造和赋值重载 -- 默认生成的浅拷贝就可以// *itRef operator*(){return _node->_data;}Ptr operator->(){ //return &(operator*());return &_node->_data;}self& operator++(){_node = _node->_next;return *this;}self operator++(int){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;}bool operator!=(const self& it){return _node != it._node;}bool operator==(const self& it){return _node == it._node;}};

list实现

	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;const_iterator begin() const{// list_node<int>*return const_iterator(_head->_next);}const_iterator end() const{return const_iterator(_head);}iterator begin(){return iterator(_head->_next);//return _head->_next;}iterator end(){return iterator(_head);}list(){_head = new Node();_head->_next = _head;_head->_prev = _head;}// lt2(lt1)/*list(const list<T>& lt){_head = new Node();_head->_next = _head;_head->_prev = _head;for (auto e : lt){push_back(e);}}*/void empty_init(){_head = new Node();_head->_next = _head;_head->_prev = _head;}template <class InputIterator>list(InputIterator first, InputIterator last){empty_init();while (first != last){push_back(*first);++first;}}// 17:00 继续void swap(list<T>& lt){std::swap(_head, lt._head);}// lt2(lt1) -- 现代写法list(const list<T>& lt){empty_init();list<T> tmp(lt.begin(), lt.end());swap(tmp);}// lt2 = lt1list<T>& operator=(list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}void push_back(const T& x){//Node* tail = _head->_prev;//Node* newnode = new Node(x); _head       tail  newnode//tail->_next = newnode;//newnode->_prev = tail;//newnode->_next = _head;//_head->_prev = newnode;insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}// 插入在pos位置之前iterator insert(iterator pos, const T& x){Node* newNode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;// prev  newnode  curprev->_next = newNode;newNode->_prev = prev;newNode->_next = cur;cur->_prev = newNode;return iterator(newNode);}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;// prev  nextprev->_next = next;next->_prev = prev;delete cur;return iterator(next);}private:Node* _head;};void print_list(const list<int>& lt){list<int>::const_iterator it = lt.begin();while (it != lt.end()){//*it = 10; // 不允许修改cout << *it << " ";++it;}cout << endl;}

插入的实现

只用实现insert就好，头插尾插复用即可。

这个很简单，轻松实现

迭代器失效

insert

list的insert不存在迭代器失效的问题。因为list不需要像vector一样挪动数据，也不像vector一样扩容出现野指针。lsit的每个结点都是独立的。

erase

erase删掉一个结点时，已经delete了，空间已经被释放了。所以会导致迭代器失效。经典野指针失效

所以erase返回删除位置的下一个位置的迭代器。所以需要重新接收迭代器。

析构函数

析构函数内部直接调用clear()，因为析构时指这个结构不要了，所以直接delete哨兵位结点。

void clear()
{iterator it = begin();while(it != end()){it = erase(it);}
}~list()
{clear();delete _head;_head = nullptr;
}

拷贝构造

拷贝构造函数的规则：我们不写，完成浅拷贝。所以_head被拷贝了一份，指向了同一块空间。

浅拷贝不一定有问题，看对应场合，比如在迭代器中，浅拷贝没有错。因为不用析构。

lsit中我们要完成深拷贝。这里需要析构。

这里先用迭代器区间进行拷贝构造

void empty_init()
{_head = new Node();_head ->_next = _head;_head->_prev = _head;
}template <class InputIterator>
list(InputIterator first, InputIterator last)
{//哨兵位结点必须有empty_init();while(first != last){push_pack(*first);++first;}
}

void swap(list<T>& lt)
{std::swap(_head, lt._head);
}
//lt2(lt1)
//现代写法
list(const list<T>& lt)
{empty_init();list<T> tmp(lt.begin(), lt.end());swap(tmp);
}

赋值构造函数

赋值构造函数返回引用，减少拷贝。返回list的原因是支持连续赋值。

//lt2 = lt1;
list<T>& operator=(list<T> lt)
{swap(lt);return *this;
}