网站建设与营销经验,微信小程序商店怎么开,漫画网站开发说明,做网站 花时间list介绍
list是STL容器中的容器#xff0c;且元素在容器中的位置是分散的并与大小无关。list的底层是双向链表#xff0c;其优势是在任意位置插入和删除元素的时间复杂度为O(1)#xff0c;但无法通过“下标[ ]”直接访问元素#xff0c;需要通过从头#xff08;尾#…list介绍
list是STL容器中的容器且元素在容器中的位置是分散的并与大小无关。list的底层是双向链表其优势是在任意位置插入和删除元素的时间复杂度为O(1)但无法通过“下标[ ]”直接访问元素需要通过从头尾遍历元素找到元素多用于需要大量数据的插入和删除且对数据的随机访问比较少。 list使用
一、list的构造
构造函数接口说明 list (size_type n, const value_type val value_type()) 构造的 list 中包含 n 个值为 val 的 元素 list() 构造空的 list list (const list x) 拷贝构造函数 list (InputIterator first, InputIterator last) 用 [first, last) 区间中的元素构造 list // list的构造listint l1; // 构造空的l1listint l2(4, 100); // l2中放4个值为100的元素listint l3(l2.begin(), l2.end()); // 用l2的[begin(), end()左闭右开的区间构造l3listint l4(l3); // 用l3拷贝构造l4// 以数组为迭代器区间构造l5int array[] { 16,2,77,29 };listint l5(array, array sizeof(array) / sizeof(int));// 列表格式初始化C11listint l6{ 1,2,3,4,5 };
二、list 的iterator的使用 接口说明 begin end 返回第一个元素的迭代器 返回最后一个元素下一个位置的迭代器 rbegin rend 返回第一个元素的 reverse_iterator, 即 end 位置 返回最后一个元素下一个位 置的 reverse_iterator, 即 begin 位置 // list迭代器的使用
// 注意遍历链表只能用迭代器和范围for
void PrintList(const listint l)
{// 注意这里调用的是list的 begin() const返回list的const_iterator对象for (listint::const_iterator it l.begin(); it ! l.end(); it){cout *it ;// *it 10; 编译不通过}cout endl;
}void TestList2()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, array sizeof(array) / sizeof(array[0]));// 使用正向迭代器正向list中的元素// listint::iterator it l.begin(); // C98中语法auto it l.begin(); // C11之后推荐写法while (it ! l.end()){cout *it ;it;}cout endl;// 使用反向迭代器逆向打印list中的元素// listint::reverse_iterator rit l.rbegin();auto rit l.rbegin();while (rit ! l.rend()){cout *rit ;rit;}cout endl;
}三、list capacity
接口说明empty 检测 list 是否为空是返回 true 否则返回 false size 返回 list 中有效节点的个数 四、list element access
接口说明front 返回 list 的第一个节点中值的引用 back 返回 list 的最后一个节点中值的引用
五、list modifiers
接口说明push_front 在 list 首元素前插入值为 val 的元素 pop_front 删除 list 中第一个元素 push_back 在 list 尾部插入值为 val 的元素 pop_back 删除 list 中最后一个元素 insert 在 list position 位置中插入值为 val 的元素 erase 删除 list position 位置的元素 swap 交换两个 list 中的元素 clear 清空 list 中的有效元素
// list插入和删除
// push_back/pop_back/push_front/pop_front
void TestList3()
{int array[] { 1, 2, 3 };listint L(array, array sizeof(array) / sizeof(array[0]));// 在list的尾部插入4头部插入0L.push_back(4);L.push_front(0);PrintList(L);// 删除list尾部节点和头部节点L.pop_back();L.pop_front();PrintList(L);
}// insert /erase
void TestList4()
{int array1[] { 1, 2, 3 };listint L(array1, array1 sizeof(array1) / sizeof(array1[0]));// 获取链表中第二个节点auto pos L.begin();cout *pos endl;// 在pos前插入值为4的元素L.insert(pos, 4);PrintList(L);// 在pos前插入5个值为5的元素L.insert(pos, 5, 5);PrintList(L);// 在pos前插入[v.begin(), v.end)区间中的元素vectorint v{ 7, 8, 9 };L.insert(pos, v.begin(), v.end());PrintList(L);// 删除pos位置上的元素L.erase(pos);PrintList(L);// 删除list中[begin, end)区间中的元素即删除list中的所有元素L.erase(L.begin(), L.end());PrintList(L);// 交换l1和l2中的元素listint l2;l1.swap(l2);PrintList(l1);PrintList(l2);// 将l2中的元素清空l2.clear();cout l2.size() endl;
} 六、list的迭代器失效 可将迭代器暂时理解成类似于指针迭代器失效即迭代器所指向的节点的无 效即该节点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list中进行插入 时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭 代器其他迭代器不会受到影响。 void TestListIterator1()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, arraysizeof(array)/sizeof(array[0]));auto it l.begin();while (it ! l.end()){// erase()函数执行后it所指向的节点已被删除因此it无效在下一次使用it时必须先给其赋值l.erase(it);it;}
}
// 改正
void TestListIterator()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, arraysizeof(array)/sizeof(array[0]));auto it l.begin();while (it ! l.end()){l.erase(it); // it l.erase(it);}
} 模拟实现
一、节点
templateclass Tstruct list_node{T _data;list_nodeT* _next;list_nodeT* _prev;list_node(const T x T()):_data(x), _next(nullptr), _prev(nullptr){}};
二、构造 void empty_init(){_head new Node();_head-_next _head;_head-_prev _head;_size 0;}//无参构造list(){empty_init();}//拷贝构造// lt2(lt1)list(const listT lt){empty_init();for (auto e : lt){push_back(e);}}//n个val构造list(size_t n, const T val T()){empty_init();for (size_t i 0; i n; i){push_back(val);}}
三、迭代器
迭代器类封装节点指针重载运算符模拟指针的行为 templateclass T, class Ref, class Ptrstruct list_iterator{typedef list_nodeT Node;typedef list_iteratorT, Ref, Ptr Self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}Self operator(){_node _node-_next;return *this;}Self operator--(){_node _node-_prev;return *this;}Self operator(int){Self tmp(*this);_node _node-_next;return tmp;}Self operator--(int){Self tmp(*this);_node _node-_prev;return tmp;}bool operator!(const Self s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}};typedef list_iteratorT, T, T* iterator;typedef list_iteratorT, const T, const T* const_iterator;iterator begin(){return iterator(_head-_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head-_next);}const_iterator end() const{return const_iterator(_head);}
四、insert iterator insert(iterator pos, const T val){Node* cur pos._node;Node* newnode new Node(val);Node* prev cur-_prev;// prev newnode curprev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;_size;return iterator(newnode);}
五、erase iterator erase(iterator pos){assert(pos ! end());Node* del pos._node;Node* prev del-_prev;Node* next del-_next;prev-_next next;next-_prev prev;delete del;--_size;return iterator(next);}六、头尾插删 void push_back(const T x){/*Node* new_node new Node(x);Node* tail _head-_prev;tail-_next new_node;new_node-_prev tail;new_node-_next _head;_head-_prev new_node;*/insert(end(), x);}void push_front(const T x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}
七、析构 ~list(){clear();delete _head;_head nullptr;}
八、赋值运算符重载 // lt2 lt3//list operator(list lt)listT operator(listT lt){swap(lt);return *this;}
九、clear void clear(){auto it begin();while (it ! end()){it erase(it);}}
