vi设计都包括什么,南通网站流量优化,wordpress ip插件,网站内链怎么删除目录
1. list的介绍及使用
1.1 list的介绍
1.2 list的使用注意事项
2.list接口介绍及模拟实现
2.1构造编辑
2.2容量
2.3修改
3.list迭代器
4.迭代器失效
5.模拟实现
6.vector和list的区别 1. list的介绍及使用
1.1 list的介绍
list的文档介绍 1. list是可以在常…目录
1. list的介绍及使用
1.1 list的介绍
1.2 list的使用注意事项
2.list接口介绍及模拟实现
2.1构造编辑
2.2容量
2.3修改
3.list迭代器
4.迭代器失效
5.模拟实现
6.vector和list的区别 1. list的介绍及使用
1.1 list的介绍
list的文档介绍 1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。 2. list的底层是带头双向循环链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。 3. list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高效。 4. 与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。 5. 与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素) 1.2 list的使用注意事项
1.list不支持随机访问不能使用[ ]来访问元素。
2.list.sort()使用的是归并排序默认为升序如果需要排降序
// 降序
listint lt;
greaterint it;
lt.sort(it);//匿名对象
lt.sort(greaterint ());
但是使用list的sort排序效率不是很高在处理数据量较多的情况下可以将数据拷贝到vector中再使用vector.sort()再将数据拷贝回去。
listint lt;vectorint v(lt.begin(), lt.end());
sort(v.begin(), v.end());
lt.assign(v.begin(), v.end()); 2.list接口介绍及模拟实现
2.1构造
void empty_init()
{head new Node;head-next head;head-prev head;_size 0;
}list()
{empty_init();
}list(const list lt)
{empty_init();for (auto e : lt){push_back(e);}
} 2.2容量 bool empty()
{return head-next head;
}size_t size()
{return _size;
} 2.3修改 void push_front(const T value)
{insert(begin(), value);
}void push_back(const T value)
{insert(end(), value);
}void pop_front()
{erase(begin());
}void pop_back()
{erase(--end());
}void insert(iterator pos, const T value T())
{Node* cur pos._node;Node* prev cur-prev;Node* newnode new Node(value);prev-next newnode;newnode-prev prev;newnode-next cur;cur-prev newnode;_size;
}iterator erase(iterator pos)
{Node* cur pos._node;Node* prev cur-prev;Node* next cur-next;prev-next next;next-prev prev;delete cur;--_size;return next;
}void swap(listT lt)
{std::swap(lt.head);std::swap(lt.size)
}void clear()
{iterator cur begin();while (cur ! end()){cur erase(cur);}
} 3.list迭代器
与vector和string不同list的迭代器需要自己实现list迭代器可以理解为一个指针指向list中的某个结点而链表的每个结点在物理空间上并不连续所以当迭代器的时候并不能直接到下一个结点的位置并且*的时候并不知道访问的是链表中的哪个数据所以我们需要自己实现将迭代器进行封装。
templateclass T, class Ref, class Ptr
struct _list_iterator
{typedef _list_nodeT Node;typedef _list_iteratorT, Ref, Ptr self;Node* _node;_list_iterator(Node* node): _node(node){}Ref operator*(){return _node-date;}Ptr operator-(){return _node-date;}self operator(){_node _node-next;return *this;}self operator--(){_node _node-prev;return *this;}bool operator!(const self lt){return _node ! lt._node;}
};
需要注意的是类模板参数有三个是为了同时能实现迭代器和const迭代器在list类中直接传不同的参数即可。 4.迭代器失效
此处大家可将迭代器暂时理解成类似于指针迭代器失效即迭代器所指向的节点的无效即该节点被删除了。因为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()){it l.erase(it);}
} 5.模拟实现
namespace cola
{templateclass Tstruct _list_node{T date;_list_nodeT* next;_list_nodeT* prev;_list_node(const T value T()): date(value), next(nullptr), prev(nullptr){}};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-date;}Ptr operator-(){return _node-date;}self operator(){_node _node-next;return *this;}self operator--(){ _node _node-prev;return *this;}self operator(int){self temp(*this);_node _node-next;return temp;}self operator--(int){self temp(*this);_node _node-prev;return temp;}bool operator!(const self lt){return _node ! lt._node;}bool operator(const self lt){return _node lt._node;}};templateclass Tclass list{typedef _list_nodeT Node;public:typedef _list_iteratorT, T, T* iterator;typedef _list_iteratorT, const T, const T* const_iterator;iterator begin(){return head-next;}iterator end(){return head;}const_iterator begin() const{return head-next;}const_iterator end() const{return head;}void empty_init(){head new Node;head-next head;head-prev head;_size 0;}list(){empty_init();}~list(){clear();delete head;}list(const list lt){empty_init();for (auto e : lt){push_back(e);}}list operator(const list lt){if (head ! lt.head){clear();for (auto e : lt){push_back(e);}}return *this;}void push_front(const T value){insert(begin(), value);}void push_back(const T value){insert(end(), value);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}void insert(iterator pos, const T value T()){Node* cur pos._node;Node* prev cur-prev;Node* newnode new Node(value);prev-next newnode;newnode-prev prev;newnode-next cur;cur-prev newnode;_size;}iterator erase(iterator pos){Node* cur pos._node;Node* prev cur-prev;Node* next cur-next;prev-next next;next-prev prev;delete cur;--_size;return next;}void swap(listT lt){std::swap(lt.head);std::swap(lt.size)}void clear(){iterator cur begin();while (cur ! end()){cur erase(cur);}}bool empty(){return head-next head;}size_t size(){return _size;}private:Node* head;size_t _size;};//打印函数适用于任何容器templatetypename Containervoid print_container(const Container lt){typename Container::const_iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;}
} 6.vector和list的区别
