泉州seo网站建设费用,怎么样子做网站,安徽省建设工程协会网站,浙江中立建设网站1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器#xff0c;并且该容器可以前后双向迭代。 2. list的底层是双向链表结构#xff0c;双向链表中每个元素存储在互不相关的独立节点中#xff0c;在节点中通过指针指向其前一个元素和后一个元素。 3. list与for…1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。 2. list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。 3. list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高效。 4. 与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。 5. 与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)。
STL中list容器的各种接口演示
#includeiostream
#includelist
#includefunctional
using namespace std;//构造方法
void test01()
{int arr[] { 1,2,3,4,5,6,7,8,9,10 };listint list1;//空链表listint list2(10);//10个0listint list3(10, 5);//10个5listint list4(arr, arr 10);//1到10listint list5(list4);//拷贝构造listint list6(list5.begin(), list5.end());//迭代器范围构造for (auto e : list6){cout e ;}
}//迭代器的使用
//STL不成文的规定1.STL的区间都是左闭右开区间
//begin()对应第一个元素
//end()对应最后一个元素的下一个元素
//2.带下划线的成员都是在底层内部调用的不是外部对象调用的
//3.STL插入数据时插入位置一般是在迭代器所指位置前面插入
void test02()
{int arr[] { 1,2,3,4,5,6,7,8,9,10 };//listint list1(arr[0], arr[9]);//左闭右开不包含10listint list1(arr, arr 10);for (auto e : list1){cout e ;}cout endl;auto it list1.begin();cout typeid(it).name() endl;while (it ! list1.end()){cout *it ;it;}cout endl;for (listint::iterator it list1.begin(); it ! list1.end(); it){cout *it ;}cout endl;listint::reverse_iterator rit list1.rbegin();//反向迭代器整套使用while (rit ! list1.rend()){cout *rit ;rit;//这里还是}cout endl;}//常链表对应常迭代器
void test03()
{int arr[] { 1,2,3,4,5,6,7,8,9,10 };const listint list1(arr, arr 10);for (listint::const_iterator it list1.begin(); it ! list1.end(); it){cout *it ;}cout endl;listint::const_reverse_iterator rit list1.rbegin();//反向迭代器整套使用while (rit ! list1.rend()){cout *rit ;rit;//这里还是}cout endl;
}void test04()
{int arr[] { 1,2,3,4,5,6,7,8,9,10 };const listint list1(arr, arr 10);cout empty list1.empty() endl;cout size list1.size() endl;cout front list1.front() endl;cout back list1.back() endl;//push_back() push_front() pop_back() pop_front()
}void test05()
{int arr[] { 1,2,3,4,5,6,7,8,9,10 };listint list1(arr, arr 10);listint list2;list2.push_back(20);list2.push_back(25);list2.push_front(30);listint::iterator pos list1.begin();//list1.insert(pos, 100);//插一个数//list1.insert(pos, 10, 2);//插10个数//list1.insert(pos, list2.begin(), list2.end());//插入迭代器区间list1.insert(pos, arr, arr 10);//插入指针区间for (auto e : list1){cout e ;}
}void test06()
{int arr[] { 1,2,3,4,5,6,7,8,9,10 };listint list1(arr, arr 10);listint list2;list2.push_back(20);list2.push_back(25);list2.push_front(30);auto pos find(list1.begin(),list1.end(),5);//find算法//list1.insert(pos, list2.begin(), list2.end());list1.erase(pos);//按位置删除list1.erase(list1.begin(), list1.end());//按区间删除list1.swap(list2);//交换操作//list1.clear();//清除操作for (auto e : list1){cout e ;}
}void test07()
{int arr[] { 1,2,3,4,5,6,7,8,9,10 };listint list1(arr, arr 10);//list1.resize(20);扩大补零list1.resize(20, 13);//扩大补指定值list1.resize(5, 15);//截断并保留原来值指定的值不起作用for (auto e : list1){cout e ;}
}void test08()
{int arr[] { 1,2,3,4,5,6,7,8,9,10 };listint list1(arr, arr 10);for (auto e : list1){cout e ;}cout endl;list1.assign(5, 0);for (auto e : list1){cout e ;}
}//拼接这里是l2移到l1后面l2就空了
void test09()
{int arr[] { 1,2,3,4,5,6,7,8,9,10 };int brr[] { 10,20,30,40,50 };listint l1(arr,arr10);listint l2(brr,brr5);for (auto e : l1){cout e ;}cout endl;l1.splice(l1.end(), l2);for (auto e : l1){cout e ;}cout endl;for (auto e : l2){cout e ;}
}//删除等于某个值的所有元素
void test10()
{int arr[] { 1,2,3,4,5,6,7,8,9,10 };listint list1(arr, arr 10);for (auto e : list1){cout e ;}cout endl;list1.remove(4);for (auto e : list1){cout e ;}
}//unique连续重复值只保留一个
void test11()
{int arr[] { 1,2,3,4,5,5,5,5,5,5,6,7,8,9,10,3,3,2,5,6 };int n sizeof(arr) / sizeof(arr[0]);listint list1(arr, arr n);for (auto e : list1){cout e ;}cout endl;list1.unique();for (auto e : list1){cout e ;}cout endl;
}class myCompare
{
public:bool operator()(int v1, int v2) const{return v1 v2;}
};void test12()
{int arr[] { 1,2,3,4,5,5,5,5,5,5,6,7,8,9,10,3,3,2,5,6 };int n sizeof(arr) / sizeof(arr[0]);listint list1(arr, arr n);//list1.sort(myCompare());//仿函数由升序变降序自己写的谓词list1.sort(greaterint());//使用内建函数对象for (auto e : list1){cout e ;}cout endl;list1.reverse();//反转for (auto e : list1){cout e ;}cout endl;
}void main()
{test12();system(pause);
}
list的迭代器失效前面说过此处大家可将迭代器暂时理解成类似于指针迭代器失效即迭代器所指向的节点的无效即该节点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。
删除it后空间已经释放t无法正常指向下一个节点出现段错误。
也就是说在删除某迭代器的对应结点后就不能对这个迭代器进行操作了因为它已经失效。
#includeiostream
#includelist
using namespace std;void test01()
{listint l1;int arr[] { 1,2,3,4,5,6,7,8,9,10 };l1.assign(arr, arr 10);auto it l1.begin();while (it ! l1.end()){l1.erase(it);it;}
}void main()
{test01();system(pause);
}
其他节点不受影响
void test02()
{listint l1;int arr[] { 1,2,3,4,5,6,7,8,9,10 };l1.assign(arr, arr 10);auto it l1.begin();auto it1 find(l1.begin(), l1.end(), 5);l1.erase(it);it1;
}
防止迭代器失效删除接口删除时会返回删除位置的下一个迭代器。
void test03()
{listint l1;int arr[] { 1,2,3,4,5,6,7,8,9,10 };l1.assign(arr, arr 10);auto it l1.begin();while (it ! l1.end()){it l1.erase(it);//删除时会返回删除位置的下一个迭代器} for (auto e : l1){cout e ;}
}list和vector的区别
1.vector底层是动态顺序表存储在一段连续空间shi是带头结点的双向循环链表。
2.vector支持随机访问访问某元素效率为O(1)list不支持随机访问访问某个元素的效率为O(n)。
3.vector任意位置插入和删除效率低需要搬移元素时间复杂度为O(N)插入时有可能需要增容增容开辟新空间拷贝元素释放旧空间导致效率更低list任意位置插入和删除效率高不需要搬移元素时间复杂度为O(1)。
4.vector的迭代器为原生态指针 list的迭代器是对原生态指针结点指针进行封装。
5.vector在插入元素时要给所有的迭代器重新赋值因为插入元素有可能会导致重新扩容致使原来迭代器失效删除时当前迭代器需要重新赋值否则会失效。list插入元素不会导致迭代器失效删除元素时只会导致当前迭代器失效其他迭代器不受影响。
6.vector需要高效存储支持随机访问不关心插入删除效率,list大量插入和删除操作不关心随 机访问。
list的模拟实现
#includeiostream
#includealgorithm
using namespace std;namespace Test
{templatetypename Yclass list;//声明了才能找到templateclass Tclass List_iterator;templatetypename Tclass Node{friend class List_iteratorT;friend class listT;//访问其私有成员Node():_val(T()),_next(nullptr),_prev(nullptr){}Node(const T val, Node* next nullptr, Node* prev nullptr) :_val(val),_next(next), _prev(prev){}~Node(){}private:T _val;Node* _next;Node* _prev;};templateclass Tclass List_iterator{public:typedef List_iteratorT self;List_iterator(NodeT* _P) :_Ptr(_P) {}bool operator!(const List_iteratorT it)//T别忘了{return this-_Ptr ! it._Ptr;}T operator*(){return _Ptr-_val;}self operator(){_Ptr _Ptr-_next;return *this;}self operator(int)//一直是int?{//List_iterator tmp(this-_Ptr);self tmp(*this);//类模板明确类型后才是具体类才能实例化对象this-_Ptr this-_Ptr-_next;return tmp;}self operator--(){_Ptr _Ptr-_prev;return *this;}self operator--(int)//一直是int?{//List_iterator tmp(this-_Ptr);self tmp(*this);//类模板明确类型后才是具体类才能实例化对象this-_Ptr this-_Ptr-_prev;return tmp;}NodeT* _Mynode(){return _Ptr;}private:NodeT* _Ptr;};templateclass Tclass list{public:typedef List_iteratorconst T const_iterator;typedef List_iteratorT iterator;typedef iterator _It;list() :_Size(0){CreatHead();}NodeT* getHead(){return _Head;}iterator begin(){return iterator(_Head-_next);}const_iterator begin() const{return const_iterator(_Head-_next);}const_iterator end() const{return const_iterator(_Head-_next);}iterator end(){return iterator(_Head);}void push_back(const T x){insert(end(), x);/*NodeT* _S new NodeT (x);_S-_prev _Head-_prev;_S-_next _Head;_S-_next-_prev _S;_S-_prev-_next _S;_Size;*/}void pop_back(){erase(--end());}void push_front(const T x){insert(begin(), x);}void pop_front(){erase(begin());}iterator insert(iterator _P, const T x){NodeT* _S new NodeT(x);NodeT* cur _P._Mynode();_S-_next cur;_S-_prev cur-_prev;_S-_next-_prev _S;_S-_prev-_next _S;_Size;return iterator(_S);}iterator erase(iterator _P){NodeT* cur _P._Mynode();NodeT* next_node cur-_next;cur-_next-_prev cur-_prev;cur-_prev-_next cur-_next;delete cur;_Size--;return iterator(next_node);}iterator erase(iterator _first, iterator _last){while (_first ! _last){_first erase(_first);//重载内部调另一个重载秀}return iterator(_last);}void swap(listT lt){std::swap(_Head, lt.getHead());}void clear(){erase(begin(), end());}size_t size() const{return _Size;}bool empty(){return _Size 0;}T front() {return *begin();}T front() const{return *begin();}T back() const{return *end();}T back() {return *(--end());}list(int n, const T val T()){CreatHead();while (n-- ){insert(begin(), val);}}list(_It _first, _It _last){CreatHead();while (_first ! _last){push_back(*_first);_first;}}list( list lt)//{CreatHead();listT tmp(lt.begin(), lt.end());std::swap(_Head, tmp._Head);//注意这里的作用域切换_Size lt.size();}listT operator( listT lt){if (this ! lt){listT tmp(lt.begin(), lt.end());std::swap(_Head, tmp._Head);//this-swap(lt);}return *this;}~list(){clear();delete _Head;_Head nullptr;}protected:void CreatHead(){_Head new NodeT;_Head-_next _Head;_Head-_prev _Head;}private:NodeT* _Head;size_t _Size;};
}void test01()
{Test::listint l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);Test::listint::iterator it l1.begin();while (it ! l1.end()){cout *it ;it;}cout endl;l1.erase(l1.begin());it l1.begin();while (it ! l1.end()){cout *it ;it;}cout endl;l1.clear();it l1.begin();while (it ! l1.end()){cout *it ;it;}cout endl;
}void test02()
{Test::listint l1(5, 10);for (auto it l1.begin(); it ! l1.end(); it){cout *it ;}cout endl;Test::listintl2(l1);for (auto it l2.begin(); it ! l2.end(); it){cout *it ;}cout endl;
}void test03()
{Test::listint l1(5, 10);Test::listint l2;l2 l1;for (auto it l2.begin(); it ! l2.end(); it){cout *it ;}
}void test04()
{Test::listintl1;for (int i 0; i 6; i){l1.push_back(i);}for (auto e : l1){cout e ;}cout endl;l1.push_front(10);for (auto e : l1){cout e ;}cout endl;l1.pop_back();for (auto e : l1){cout e ;}cout endl;l1.pop_front();for (auto e : l1){cout e ;}
}void test05()
{Test::listintl1;for (int i 0; i 6; i){l1.push_back(i);}Test::listintl2;for (int i 6; i 11; i){l2.push_back(i);}l1.swap(l2);for (auto e : l1){cout e ;}cout endl;for (auto e : l2){cout e ;}cout endl;
}void test06()
{const Test::listintl1(5,10);cout l1.front() endl;
}void main()
{test06();system(pause);
}
