STL-List常用接口

List常用接口

insert

list<int>::iterator pos = find(lt.begin(), lt.end(), 3);
if (pos != lt.end())lt.insert(pos, 30);
for (auto e : lt)cout << e << " ";
cout << endl;

list的不会失效，而vector会失效。

erase后均会失效。

解决迭代器失效问题

list<int>::iterator it = lt.begin();
while (it != lt.end())
{if (*it % 2 == 0)it = lt.erase(it);elseit++;
}

核心 erase会返回以删除位置的下一个位置。

清空列表的两种方式

while (it != lt.end())
{lt.erase(it++);
}
lt.clear();

模拟实现list

模拟node节点

template<class T>
struct __list_node
{__list_node<T>* _next;__list_node<T>* _prev;T _data;__list_node(const T& x=T()):_data(x),_next(nullptr),_prev(nullptr){}
};

模拟构造迭代器

template<typename T>
struct __list_iterator
{typedef __list_node<T> Node;Node* _node;__list_iterator(Node* node):_node(node){}//*it;T& operator*(){return _node->_data;}//++it__list_iterator<T> operator++(){_node = _node->_next;return *this;}//it!=end()bool operator!=(__list_iterator<T>& it){return _node != it->_node;}
};

 按照STL原码模拟实现list的结构

template<class T>
class list
{typedef struct __list_node<T> Node;typedef __list_iterator<T> iterator;
public:iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}//带头双向循环列表list(){_head = new node;_head->_next = _head;_head->_prev = _head;}void push_back(const T& x){Node* tail = _head->_prev;Node* newnode = new Node(x);tail->_next = newnode;newnode->_prev = tail;_head->_prev = newnode;newnode->_next = _head;}
private:Node* _head;
};

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

有了迭代器就可以使用范围for 

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

struct Date
{int _year = 0;int _mouth = 1;int _day = 1;
};
void test_list()
{list<Date> lt;lt.push_back(Date());lt.push_back(Date());list<Date>::iterator it = lt.begin();while (it != lt.end()){cout << it->_year << it->_mouth << it->_day << endl;++it;}
}

while (it != lt.end())
{//cout << it->_year << it->_mouth << it->_day << endl;cout << (*it)._year << (*it)._mouth << (*it)._day << endl;++it;
}

前后置++ 

//++it
__list_iterator<T>& operator++()
{_node = _node->_next;return *this;
}
__list_iterator<T>& operator++()
{_node = _node->_prev;return *this;
}
//it++	 
__list_iterator<T> operator++(int)
{__list_iterator<T> tmp(*this);_node = _node->_next;return tmp;
}

//it++	 
__list_iterator<T> operator++(int)
{__list_iterator<T> tmp(*this);_node = _node->_next;//(*this)++;return tmp;
}