河北平台网站建设价位,门户类网站费用,网站后台上传新闻,上海网站建设开1.list
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器#xff0c;并且该容器可以前后双向迭代。 2. list的底层是双向链表结构#xff0c;双向链表中每个元素存储在互不相关的独立节点中#xff0c;在节点中通过指针指向其前一个元素和后一个元素。 3. l…1.list
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。 2. list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。 3. list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高效。 4. 与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。 5. 与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素) 2.list的使用
2.1 构造函数 void test1()
{//无参构造listint l1;//有参构造listint l2(10, 1);//10个1listint l3(10);//使用迭代器范围构造listint l4(l2.begin(), l2.end());//双向迭代器不支持加减法vectorint v { 1,2,3,4,5 };listint l5(v.begin() 2, v.end());//拷贝构造listint l6(l5);//使用initializer_list初始化listint l7 { 1,2,3,4,5,6,7,8 };
}2.2operator() 赋值运算符重载进行深拷贝
//int类型
void PrintList(const listint l)
{for (auto e : l){cout e ;}cout endl;
}void test2()
{//operatorlistint l1 { 1,2,3 };listint l2;//深拷贝l2 l1;PrintList(l1);PrintList(l2);
} 2.3begin() 和 end() begin()返回第一个元素的双向迭代器如果容器为空则返回的迭代器值不能被解引用。 end()返回最后一个元素的下一位双向迭代器如果容器为空返回的迭代器与begin()返回的迭代器相同。 双向迭代器不支持加减法支持 、 -- 、 * 、 、 ! 、 等操作。
void test3()
{//begin() and end()listint l { 1,2,3,4,5,6,7,8 };listint::iterator it l.begin();//返回双向迭代器while (it ! l.end()){cout *(it) ;}cout endl;
}
2.4 rbegin() 和 rend() rbegin()返回最后一个元素的反向双向迭代器 rend()返回第一个元素前一位的反向双向迭代器 使用是向前迭代--是向后迭代
void test4()
{listintl { 1,2,3,4,5,6,7,8 };listint::reverse_iterator it l.rbegin();while (it ! l.rend()){cout *(it) ;}cout endl;
}
2.5 cbegin()、cend()、crbegin()、 crend() 无论调用对象是否const修饰这四个函数返回const迭代器不能通过迭代器修改指向内容但迭代器本身可以改变。
2.6 empty()
判断容器是否为空空返回true非空返回false
void test5()
{listintl { 1,2,3,4,5,6,7,8 };while (!l.empty()){cout l.front() ;l.pop_front();}
}
2.7 size() 用于返回有效元素个数 2.8 front() 返回容器第一个元素的引用对空容器使用front是未定义行为 2.9 back() 返回容器最后一位元素的引用对空容器使用back是未定义行为 2.10 assign() 将新内容替换原本的全部内容
void test8()
{//assignlistint l1 { 1,2,3,4,5 };listint l2 { 11,22 };vectorint v { 121,23,43,54,54,5,454 };//范围替换l1.assign(v.begin(), v.begin() 3);l2.assign(l1.begin(), l1.end());PrintList(l1);PrintList(l2);//n个val替换l1.assign(10, 2);l2.assign(2, 0);PrintList(l1);PrintList(l2);
}
2.11 emplace_front 在开头构造并插入元素 在列表的开头插入一个新元素就在它当前的第一个元素之前。这个新元素是使用args作为其构造的参数来就地构造的。 这有效地将容器大小增加了1。 该元素是通过调用allocator_traits::construct来就地构造的并将参数转发。 存在一个类似的成员函数push_front它复制或移动一个现有对象到容器中。 class A
{
public:A(int a, int b):_a(a), _b(b){cout 构造 endl;}A(const A a){cout 拷贝构造 endl;}void Print(){cout _a _b endl;}
private:int _a;int _b;
};
void test10()
{listA l1;listA l2;l1.emplace_front(1,2);//直接构造并成为l1的元素//l2.push_front(1, 2);//errorl2.push_front({ 2,3 });//先隐式类型转换构造再拷贝构造成l2的元素(*l1.begin()).Print();(*l2.begin()).Print();
} 2.12 push_front() 在容器第一个元素前插入一个元素 val的内容被拷贝(或移动)到插入的元素。 push_back()执行拷贝行为还是移动行为取决于传递给它的参数类型传递左值触发拷贝构造函数执行拷贝行为传递右值触发移动构造函数执行移动操作。 (在 C 中左值lvalue和 右值rvalue是用来区分表达式的值在内存中的存在方式和生命周期的术语。) 移动构造函数是 C11 引入的一种特殊构造函数旨在高效地转移资源的所有权而不是进行昂贵的复制。它通过移动语义来减少不必要的拷贝提高程序性能。
移动构造函数通常在以下情况下被调用
对象临时生命周期结束后当你通过一个临时对象右值初始化另一个对象时移动构造函数会被调用。使用 std::move当你显式调用 std::move 函数将一个对象转换为右值引用时会触发移动构造函数。 2.13 pop_front()
用于删除第一个元素
2.14 emplace_back() 在末尾构造并插入元素 2.15 push_back() 在最后一个元素之后插入一个元素val的内容被拷贝(或移动)到新元素。 2.16 pop_back() 删除最后一个元素 2.17 emplace() 在pos位置的元素之前构造并插入一个元素 2.18 insert() 在指定位置的元素之前插入新元素一个或多个
void test13()
{listint l1 {1,2,3};vectorint v { 444,555,666,777 };auto it l1.begin();//iterator insert (const_iterator position, const value_type val);l1.insert(it, 0);PrintList(l1);//iterator insert (const_iterator position, size_type n, const value_type val);it;l1.insert(it, 3, 6);PrintList(l1);//template class InputIterator//iterator insert(const_iterator position, InputIterator first, InputIterator last);l1.insert(l1.begin(), v.begin() 2, v.end());PrintList(l1);//iterator insert (const_iterator position, value_type val);//右值引用l1.insert(it, 9);PrintList(l1);//iterator insert(const_iterator position, initializer_listvalue_type il);l1.insert(it, { 11,12,13,14,15 });PrintList(l1);
} 2.19 erase()
从容器中删除一个或者范围内的元素 2.20 swap() 交换两个容器的内容 2.21 resize() 调整容器的有效元素的个数使其包含n个元素 n小于当前个数元素将减少到前n个超出部分删除并销毁 n大于当前个数元素将尾插至n个如果指定了val则新元素初始化为val的副本
class A
{
public:A(){cout 无参构造 endl;}A(int a, int b):_a(a), _b(b){cout 有参构造 endl;}A(const A a){cout 拷贝构造 endl;}void Print(){cout _a _b endl;}
private:int _a;int _b;
};void test14()
{listA l1;l1.resize(2, {1,1});cout ------ endl;l1.resize(5);//3个无参构造
} 2.22 clear()
删除容器的所有内容
2.23 splice()
用于将元素从一个list转移到另一个list转移将元素从原来的list移除原封不动转移到另一个list 2.24 remove() 从容器中删除所有与val相同的元素 2.25 remove_if() 用于从容器中移除满足特定条件的元素 remove_if()传入一个谓语函数返回bool值的函数
2.26 unique() 删除相邻val值重复的元素 需要给整个容器去重先排序再unique
2.27 merge() 用于将两个已排序的列表合并成一个排序后的列表。需要注意的是两个列表必须都是按顺序排列的。合并操作会通过移动节点来达成而不需要额外分配内存。 两个列表的排序方式需要与合并成一个列表后的排序方式保持一致即两个升序列表合并成一个升序列表两个降序列表合并成一个降序列表 2.28 sort() sort() 函数会对列表中的元素进行升序排序。默认情况下它使用元素的 运算符进行比较, 也可以提供一个自定义的比较函数。 list的sort()底层是基于归并排序实现的归并排序在处理链表时的性能非常优越因为它可以高效地操作节点而不需要额外的空间消耗。归并排序通过分割链表和合并已排序的部分能够快速地处理链表的节点。 2.29 reverse() 用于反转list
2.30 关系运算符重载非成员函数 3.operator-() 为了可读性强制剩下一个-
4. 部分模拟实现
#pragma once
#includeassert.hnamespace myList
{templateclass Tstruct ListNode{ListNodeT* _next;ListNodeT* _prev;T _data;ListNode(const T data T()):_next(nullptr),_prev(nullptr),_data(data){}};templateclass T, class Ref, class Ptrstruct ListIterator{typedef ListNodeT Node;typedef ListIteratorT, Ref, Ptr Self;Node* _node;ListIterator(Node* node):_node(node){}// it;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;}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const Self it){return _node ! it._node;}bool operator(const Self it){return _node it._node;}};//templateclass T//class ListConstIterator//{// typedef ListNodeT Node;// typedef ListConstIteratorT Self;// Node* _node;//public:// ListConstIterator(Node* node)// :_node(node)// {}// // it;// 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;// }// //*it// const T operator*()// {// return _node-_data;// }// const T* operator-()// {// return _node-_data;// }// bool operator!(const Self it)// {// return _node ! it._node;// }// bool operator(const Self it)// {// return _node it._node;// }//};templateclass Tclass list{typedef ListNodeT Node;public:// 不符合迭代器的行为无法遍历//typedef Node* iterator;//typedef ListIteratorT iterator;//typedef ListConstIteratorT const_iterator;typedef ListIteratorT, T, T* iterator;typedef ListIteratorT, const T, const T* const_iterator;iterator begin(){//iterator it(_head-_next);//return it;return iterator(_head-_next);}const_iterator begin() const{return const_iterator(_head-_next);}iterator end(){return iterator(_head);}const_iterator end() const{return const_iterator(_head);}void empty_init(){_head new Node();_head-_next _head;_head-_prev _head;}list(){empty_init();}list(initializer_listT il){empty_init();for (const auto e : il){push_back(e);}}// lt2(lt1)list(const listT lt){empty_init();for (const auto e : lt){push_back(e);}}// lt1 lt3listT operator(listT lt){swap(_head, lt._head);return *this;}~list(){clear();delete _head;_head nullptr;}void clear(){auto it begin();while (it ! end()){it erase(it);}}void push_back(const T x){/*Node* newnode new Node(x);Node* tail _head-_prev;tail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;*/insert(end(), x);}void pop_back(){erase(--end());}void push_front(const T x){insert(begin(), x);}void pop_front(){erase(begin());}// 没有iterator失效iterator insert(iterator pos, const T x){Node* cur pos._node;Node* newnode new Node(x);Node* prev cur-_prev;// prev newnode curprev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;return iterator(newnode);}// erase 后 pos失效了pos指向节点被释放了iterator erase(iterator pos){assert(pos ! end());Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;return iterator(next);}private:Node* _head;};
}
