威县做网站哪儿好,基于wordpress的博客系统,淄博企业网站设计公司,宁波建设局网站首页 1.封装除了对数据的保护、更好地管理数据之外#xff0c;还有实现了对上层的统一#xff1b;
2.类模板参数的不同#xff0c;一方面是为了实例化出来不同的类#xff0c;另一方面是为了实现类的成员函数的不同#xff1b;
一、认识list
1.list是一种带头双向循… 1.封装除了对数据的保护、更好地管理数据之外还有实现了对上层的统一
2.类模板参数的不同一方面是为了实例化出来不同的类另一方面是为了实现类的成员函数的不同
一、认识list
1.list是一种带头双向循环链表。相较于vector的最大优点就是支持了头插头删而且时间复杂度是O12.list不支持因为链表不是一段连续的空间重载实现得遍历一遍代价太大但是却支持了迭代器可以用迭代器遍历查找或者算法find配合查找3.迭代器循环访问使用!不是是因为空间可能是不连续的4.insert不存在迭代器失效问题erase存在。
1.默认成员函数
explicit list (const allocator_type alloc allocator_type());
explicit list (size_type n, const value_type val value_type(),const allocator_type alloc allocator_type());
template class InputIterator
list (InputIterator first, InputIterator last,const allocator_type alloc allocator_type());
list (const list x);2.迭代器
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;3.空间
bool empty() const;
size_type size() const;4.元素访问
reference front();
const_reference front() const;
reference back();
const_reference back() const;5.成员类型
InputIterator涉及到父子类关系一般都可以使用。
迭代器按容器底层结构分为单向迭代器可以双向迭代器可以 --随机迭代器可以 – -。
单向迭代器forward iteratorforward_list/(哈希)unordered_map/unordered_set
双向迭代器bidirectional iteratorlist/map/set
随机迭代器random iteratorvector/string/dequeue/
//与vector类似除了迭代器类型发生了变化变成了双向迭代器6.成员修改
void push_front (const value_type val);
void pop_front();
void push_back (const value_type val);
void pop_back();
iterator insert (iterator position, const value_type val);
void insert (iterator position, size_type n, const value_type val);//配合算法的find迭代器区间迭代器区间的设计统一为左闭右开。
template class InputIterator
void insert (iterator position, InputIterator first, InputIterator last);
iterator erase (iterator position);
iterator erase (iterator first, iterator last);7.其他操作
reserve()//与库里面实现的功能是一样的较为冗余
sort()//算法库里面的不支持使用的是快排因为库里面使用的是随机迭代器而list的迭代器是双向的迭代器不支持。list的sort底层使用的是归并排序
//如果要排序最好用vector效率远大于list。
merge()//归并使用前需要先排序归并结果才正确
unique()//去重使用前需要先排序效率会提高
remove()//finderase找到了删除找不到什么都不做
splice()//将一个链表的节点转移到另一个链表全部转移转移一个节点区间转移二、模拟实现list
1.命名空间
namespace List
{template class Tstruct list_node{list_node(const T val T()) : next_(nullptr), prev_(nullptr), val_(val) {}list_nodeT *next_;list_nodeT *prev_;T val_;};template class Tstruct list_iterator{//迭代器内嵌类型typedef list_nodeT node;// 迭代器的构造函数__list_iterator(node *node) : node_(node) {}// 迭代器的成员node *node;};template class Tclass list{typedef list_nodeT node;public:typedef __list_iteratorT, T iterator;typedef __list_iteratorT, const T const_iterator;public:list() : head_(nullptr){head_ new node;head_-next_ head_;head_-prev_ head_;head_-val_ T();}~list(){delete head;head}private:node *head_;};
}2.成员变量
private:node *head_;size_t size_;3.普通成员函数
void push_back(const T val)
{insert(end(), val);
}
void push_front(const T val)
{insert(begin(), val);
}
void pop_back()
{erase(--end());
}
void pop_front()
{erase(begin());
}
iterator insert(iterator pos, const T val)
{// 对于带头双向循环链表不需要检查pos的合法性。// 1.将迭代器转换为节点指针便于访问数据node *cur pos.node_;// 2.创建新节点node *newnode new node(val);// 3.建立连接node *prev cur-prev_;prev-next_ newnode;newnode-prev_ prev;newnode-next_ cur;cur-prev_ newnode;size_;return newnode;
}
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;cur nullptr;size_--;return next;
}
size_t size()
{// 每次都要遍历时间复杂度是On// size_t sz 0;// iterator it begin();// while (it ! end())// {// sz;// it;// }// return sz;return size_;
}
void clear()
{iterator it begin();while (it ! end()){it erase(it);}
}
void empty_init()
{head_ new node;head_-next_ head_;head_-prev_ head_;
}
void swap(listT lt)
{std::swap(head_, lt.head_);std::swap(size_, lt.size_);
}4.迭代器类的定义
//1.不写拷贝构造内置类型浅拷贝已经满足析构函数对内置类型不做处理这样使得迭代器类满足只访问和修改不参与节点的创建和销毁
//2.vector与string使用指针做迭代器是因为它们的底层结构使用指针天然支持迭代器比如 、、*等都是直接就满足要求的而list需要自己设计来符合这种上层统一的像指针一样访问数据的方法。
template class T
struct __list_iterator
{// 迭代器的内嵌类型typedef list_nodeT node;typedef __list_iteratorT, Ref, Ptr self;// 迭代器的构造函数__list_iterator(node *node) : node_(node) {}// 迭代器的普通成员函数Ref operator*(){return node_-val_;}// 如果value是一个自定义对象而想要访问的是对象的成员但是直接解引用就是对象本身而不是对象的成员还需要对象.成员的操作来访问// 使用箭头就可以直接访问到成员// iterator-返回的是val的地址iterator-成员转化成了地址成员应该是地址-成员所以猜测编译器进行了特殊处理将iterator-成员识别// 成了iterator--成员即为了增强可读性做了优化Ptr operator-(){return (node_-val_);}self operator(){node_ node_-next_;return *this;}self operator(int){self tmp(node_);node_ node_-next_;return tmp;}self operator--(){node_ node_-prev_;return *this;}self operator--(int){self tmp(node_);node_ node_-prev_;return tmp;}bool operator!(const self it) const{return node_ ! it.node_;}bool operator(const self it) const{return node_ it.node_;}// 迭代器的成员node *node_;
};
//const迭代器的设计
//1.首先const迭代器本身要允许即允许自身改变而typedef const __list_iteratorT iterator;
//则是对象本身不允许修改。2.只要改变*运算符重载返回值const修饰不允许修改即可。3.直接设计const迭代器类过于冗余可以增加模板参数来实现对返回值和参数的修改。5.迭代器
iterator begin()
{return head_-next_; // 隐式类型转换加拷贝构造优化为构造
}
iterator end()
{return head_;
}
const_iterator begin() const
{return head_-next_;
}
const_iterator end() const
{return head_;
}6.默认成员函数
// 默认成员函数
list() : head_(nullptr), size_(0)
{empty_init();
}
// list(const list lt) : head_(nullptr), size_(0)
list(const listT lt) : head_(nullptr), size_(0)
{// 初始化哨兵位头节点empty_init();// 遍历拷贝for (auto e : lt){push_back(e);// list内部存放的是一个头节点可以通过头节点找到并访问普通节点中所存放的值。而vector内部一大块空间所以可以实现赋值。}
}
// list operator(list lt)//在类内语法上支持直接用类名替换类型成员函数也支持
listT operator(listT lt)
{swap(lt);return *this;
}
~list()
{clear();delete head_;head_ nullptr;
}7.内嵌类型
privatetypedef list_nodeT node;
public:typedef __list_iteratorT, T iterator;typedef __list_iteratorT, const T const_iterator;
