省品牌建设联合会网站网站建设和优化内容最重要

当前位置： 首页 > news >正文

省品牌建设联合会网站,网站建设和优化内容最重要,切实加强门户网站建设,开公司需要什么条件目录 一、list 容器的基本介绍 二、list 容器的成员函数 2.1 - 迭代器 2.2 - 修改操作 三、list 的模拟实现 3.1 - list.h 3.2 - 详解 list 容器的迭代器 3.2 - test.cpp 一、list 容器的基本介绍 list 容器以类模板 listT#xff08;T 为存储元素的类型TT 为存储元素的类型的形式定义在 list 头文件中并位于 std 命名空间中。 template class T, class Alloc allocatorT class list;     list 是序列容器允许在序列内的任意位置高效地插入和删除元素时间复杂度是 O(1) 常数阶其迭代器类型为双向迭代器bidirectional iterator。 list 容器的底层是以双向链表的形式实现的。 list 容器与 forward_list 容器非常相似最主要的区别在于 forward_list 容器的底层是以单链表的形式实现的其迭代器类型为前向迭代器forward iterator。 与其他标准序列容器array、vector 和 deque相比list 容器在序列内已经获得迭代器的任意位置进行插入、删除元素时通常表现得更好。 与其他序列容器相比list 容器和 forward_list 容器的最大缺点是不支持任意位置的随机访问例如要访问 list 中的第 6 个元素必须从已知位置比如头部或尾部迭代到该位置这需要线性阶的时间复杂度的开销。 二、list 容器的成员函数 2.1 - 迭代器 begin iterator begin(); const_iterator begin() const; end: iterator end(); const_iterator end() const; rbegin reverse_iterator rbegin(); const_reverse_iterator rbegin() const; rend reverse_iterator rend(); const_reverse_iterator rend() const; 示例 #include iostream #include list using namespace std; ​ int main() {listint l;l.push_back(0);l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4); ​for (listint::iterator it l.begin(); it ! l.end(); it){cout *it ;}// 0 1 2 3 4cout endl; ​for (listint::reverse_iterator rit l.rbegin(); rit ! l.rend(); rit){cout *rit ;}// 4 3 2 1 0cout endl;return 0; } 2.2 - 修改操作 push_front void push_front(const value_type val); 注意value_type 等价于 T。 pop_front void pop_front(); push_back void push_back(const value_type val); pop_back void pop_back(); insert // C 98 single element (1) iterator insert(iterator position, const value_type val);fill (2)     void insert(iterator position, size_type n, const value_type val);range (3) template class InputIteratorvoid insert(iterator position, InputIterator first, InputIterator last); 相较于 vector执行 list 的 insert 操作不会产生迭代器失效的问题。 示例一 #include iostream #include list using namespace std; ​ int main() {listint l;l.push_back(0);l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4); ​// 要求在第三个元素前面插入元素 100// l.insert(l.begin() 2, 100); // error// 因为 list 对应的迭代器类型为双向迭代器所以不支持加法操作即没有重载该运算符 ​// 解决方案listint::iterator it l.begin();for (size_t i 0; i 2; i){it;}l.insert(it, 100); ​for (auto e : l){cout e ;}// 0 1 100 2 3 4cout endl;return 0; } erase iterator erase(iterator position); iterator erase(iterator first, iterator last); 因为节点被删除后空间释放了所以执行完 list 的 erase 操作迭代器就失效了而解决方案依然是通过返回值对迭代器进行重新赋值。 示例二 #include iostream #include list using namespace std; ​ int main() {listint l;l.push_back(0);l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4); ​// 删除 list 中所有值为偶数的元素listint::iterator it l.begin();while (it ! l.end()){if (it % 2 0)it l.erase(it);  // 直接写 l.erase(it); 会报错elseit;} ​for (auto e : l){cout e ;}// 1 3cout endl;return 0; } 三、list 的模拟实现 3.1 - list.h #pragma once ​ #include iostream #include assert.h ​ namespace yzz {templateclass Tstruct list_node{list_nodeT _prev;list_nodeT* _next;T _data; ​list_node(const T val T()): _prev(0), _next(0), _data(val){ }}; ​ ​templateclass T, class Ref, class Ptrstruct __list_iterator{typedef __list_iteratorT, Ref, Ptr self;typedef list_nodeT list_node;list_node* _pnode;  // 节点指针 ​list_iterator(list_node* p 0): _pnode(p){ } ​self operator(){_pnode _pnode-_next;return *this;} ​self operator(int){self tmp(*this);_pnode _pnode-_next;return tmp;} ​self operator–(){_pnode _pnode-_prev;return *this;} ​self operator–(int){self tmp(this);_pnode _pnode-_prev;return tmp;} ​Ref operator() const{return _pnode-_data;} ​Ptr operator-() const{return _pnode-_data;} ​bool operator!(const self it) const{return _pnode ! it._pnode;} ​bool operator(const self it) const{return _pnode it._pnode;}}; ​ ​templateclass Tclass list{private:typedef __list_nodeT list_node; ​void empty_initialize(){_phead new list_node;_phead-_prev _phead;_phead-_next _phead;} ​public:/——– 构造函数和析构函数 ——–/list(){empty_initialize();} ​list(const listT l)  // 实现深拷贝{empty_initialize();for (auto e : l){push_back(e);}} ​~list(){clear();delete _phead;_phead 0;} ​/——– 赋值运算符重载 ——–/// 利用上面写好的拷贝构造函数实现深拷贝void swap(listT l){std::swap(_phead, l._phead);} ​listT operator(listT tmp){swap(tmp);return this;} ​/——– 迭代器 ——–/typedef __list_iteratorT, T, T iterator;typedef __list_iteratorT, const T, const T* const_iterator;iterator begin(){return _phead-_next;// 等价于return iterator(_phead);// 返回的过程中发生了隐式类型转换} ​iterator end(){return _phead;} ​const_iterator begin() const{return _phead-_next;// 等价于return const_iterator(_phead-_next);} ​const_iterator end() const{return _phead;} ​/——– 容量操作 ——–/size_t size() const{size_t sz 0;list_node* cur _phead-_next;while (cur ! _phead){sz;cur cur-_next;}return sz;} ​bool empty() const{return _phead-_next _phead;} ​/——– 修改操作 ——–/iterator insert(iterator pos, const T val){list_node* newnode new list_node(val);newnode-_prev pos._pnode-_prev;newnode-_next pos._pnode; ​pos._pnode-_prev-_next newnode;pos._pnode-_prev newnode;return newnode;} ​void push_back(const T val){// 方法一/list_node newnode new list_node(val);newnode-_prev _phead-_prev;newnode-_next _phead; ​_phead-_prev-_next newnode;_phead-_prev newnode;*/ ​// 方法二直接复用insert(end(), val);} ​void push_front(const T val){// 方法一/list_node newnode new list_node(val);newnode-_prev _phead;newnode-_next _phead-_next; ​_phead-_next-_prev newnode;_phead-_next newnode;/ ​// 方法二直接复用insert(begin(), val);} ​iterator erase(iterator pos){assert(pos ! end());  // 前提是 list 非空list_node prev_pnode pos._pnode-_prev;list_node* next_pnode pos._pnode-_next;prev_pnode-_next next_pnode;next_pnode-_prev prev_pnode;delete pos._pnode;return iterator(next_pnode);} ​void pop_back(){erase(–end());} ​void pop_front(){erase(begin());} ​void clear(){list_node* cur _phead-_next;while (cur ! _phead){list_node* tmp cur;cur cur-_next;delete tmp;}_phead-_prev _phead-_next _phead;} ​private:list_node* _phead;  // 头指针}; } 3.2 - 详解 list 容器的迭代器 我们可以通过循序渐进的方式来了解 list 容器的迭代器 首先不能使用原生态指针直接作为 list 容器的正向迭代器即 typedef list_node* iterator; 否则当正向迭代器进行 /– 操作时无法让它指向下一个或上一个节点并且进行解引用 * 操作时无法直接获得节点的值所以需要对原生态指针进行封装然后对这些操作符进行重载即 typedef __list_iteratorT iterator; 其次不能按以下方式直接定义 list 容器的常量正向迭代器即 typedef const __list_iteratorT const_iterator; 否则常量正向迭代器就无法进行 /– 操作因为 const 类对象只能去调用 const 成员函数并且 operator* 的返回值类型为 T即仍然可以在外部修改 list 容器。 可以重新定义一个常量正向迭代器 __list_const_iterator但需要修改的地方仅仅是 operatr* 的返回值即将其修改为 const T显然这样的解决方案会造成代码的冗余所以在 __list_iterator 类模板中增加一个类型参数 Ref将 operator* 的返回值修改为 Ref即 typedef __list_iteratorT, T iterator; typedef __list_iteratorT, const T const_iterator; 最后在重载 - 操作符时对于正向迭代器返回值类型应该是 T*对于常量正向迭代器返回值类型应该是 const T所以再增加一个类型参数 Ptr将 operator- 的返回值类型修改为 Ptr即 typedef __list_iteratorT, T, T iterator; typedef __list_iteratorT, const T, const T* const_iterator; 3.2 - test.cpp #include list.h #include iostream using namespace std; ​ void Print1(const yzz::listint l) {yzz::listint::const_iterator cit l.begin();while (cit ! l.end()){cout *cit ;cit;}cout endl; } ​ void test_list1() {yzz::listint l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);cout l1.size() endl;  // 4yzz::listint l2(l1);for (yzz::listint::iterator it l2.begin(); it ! l2.end(); it){cout *it ;}// 1 2 3 4cout endl; ​l1.push_front(10);l1.push_front(20);l1.push_front(30);l1.push_front(40);cout l1.size() endl;  // 8yzz::listint l3;l3 l1;for (auto e : l3){cout e ;}// 40 30 20 10 1 2 3 4cout endl; ​l1.pop_back();l1.pop_back();l1.pop_front();l1.pop_front();cout l1.size() endl;  // 4Print1(l1);// 20 10 1 2 ​l1.clear();cout l1.size() endl;  // 0cout l1.empty() endl;  // 1 } ​ struct Point {int _x;int _y; ​Point(int x 0, int y 0): _x(x), _y(y){ } }; ​ void Print2(const yzz::listPoint l) {yzz::listPoint::const_iterator cit l.begin();while (cit ! l.end()){// 方法一// cout ( (*cit)._x , (*cit)._y ) ;// 方法二cout ( cit-_x , cit-_y ) ;// 注意operator- 是单参数所以本应该是 cit–_i 和 cit–_j// 但为了可读性编译器做了优化即省去一个 -cit;}cout endl; } ​ void test_list2() {yzz::listPoint l;l.push_back(Point(1, 1));l.push_back(Point(2, 2));l.push_back(Point(3, 3));l.push_back(Point(4, 4));Print2(l);// (1, 1) (2, 2) (3, 3) (4, 4) } ​ int main() {// test_list1();test_list2();return 0; }