北京网站优化外包,十大小说网站排名,js 做网站,自己开发一个app要多少钱目录
list介绍
list的函数接口
构造函数
push_front和pop_front
push_back和pop_back
insert
erase
迭代器
front和back
size
resize
empty
clear
list::sort
unique
reverse
迭代器的实现 list介绍 list是一种可以在常数范围内在任意位置进行插入和删除的序列…目录
list介绍
list的函数接口
构造函数
push_front和pop_front
push_back和pop_back
insert
erase
迭代器
front和back
size
resize
empty
clear
list::sort
unique
reverse
迭代器的实现 list介绍 list是一种可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立结点当中在结点中通过指针指向其前一个元素和后一个元素。list与forward_list非常相似最主要的不同在于forward_list是单链表只能进行单方向迭代。与其他容器相比list通常在任意位置进行插入、删除元素的执行效率更高。list和forward_list最大的缺陷是不支持在任意位置的随机访问其次list还需要一些额外的空间以保存每个结点之间的关联信息对于存储的类型较小元素来说这可能是一个重要的因素。 总的来说list就是一个带头双向循环链表。 list的函数接口 构造函数 listint l1; //构造int类型的空容器
listint l2(10, 2); //构造含有10个2的int类型容器
listint l3(l2); //拷贝构造int类型的l2容器的复制品 push_front和pop_front // push_front函数用于头插pop_front函数用于头删
listint l;
l.push_front(1);
l.push_front(0);l.pop_front() push_back和pop_back // push_back函数用于尾插pop_back函数用于尾删
listint l;
l.push_back(0);
l.push_back(1);l.pop_back(); insert listint l;
l.push_back(0);
l.push_back(1);
l.push_back(2);listint::iterator pos find(l.begin(), l.end(), 2); // 要包含algorithm库l.insert(pos, 10); // 在pos2位置之前插入10l.insert(pos, 2, 9); // 在pos2位置之前插入2个9 erase listint l;
l.push_back(0);
l.push_back(1);listint::iterator pos find(l.begin(), l.end(), 1);
if (pos ! l.end()) // 一定要找到了再删除
{l.erase(pos); // 删除指定迭代器位置的元素// pos l.erase(pos) // 也可以接受返回值返回的是删除位置的下一个节点
} 要注意的是list也有迭代器失效的问题既然放到erase这里才讲那就是erase的时候会导致迭代器失效。 迭代器 listint l(5, 2);
// 正向迭代器遍历容器
listint::iterator it lt.begin();
while (it ! lt.end())
{cout *it ;it;
}// 反向迭代器遍历容器
listint::reverse_iterator rit lt.rbegin();
while (rit ! lt.rend())
{cout *rit ;rit;
} front和back // size函数用于获取当前容器当中的元素个数
listint l;
l.push_back(0);
l.push_back(1);
l.push_back(2);
cout l.size() endl; size // front函数用于获取list容器当中的第一个元素back函数用于获取list容器当中的最后一个元素
listint l;
l.push_back(0);
l.push_back(1);
l.push_back(2);cout l.front() endl;
cout l.back() endl; resize // 当所给值大于当前的size时将size扩大到该值扩大的数据为第二个所给值若未给出则默认为容器所存储类型的默认构造函数所构造出来的值。
// 当所给值小于当前的size时将size缩小到该值。
listint l(5, 1);
l.resize(10, 2);l.resize(2);empty listint l;
cout l.empty() endl; // 判断容器是否为空返回的是bool类型就是0或1 clear // clear函数用于清空容器清空后容器的size为0。
listint l(5, 1);
l.clear(); list::sort listint l;
l.push_back(4);
l.push_back(7);
l.push_back(5);
l.push_back(9);l.sort(); // 默认将容器内数据排为升序// 既然algorithm中已经有了一个sort函数那为什么还有在list中加入这个函数呢
// 那是因为算法库中的sort让list使用是会报错的
// 算法库中的sort要求物理空间必须是连续的// 注意一般也不会使用list中的sort函数
// 在数据量大的时候效率较低不如直接把数据插入到vector中使用algorithm中的sort函数 unique // unique函数用于删除容器当中连续的重复元素使用这个函数必须要先排序
listint l;
l.push_back(0);
l.push_back(0);
l.push_back(1);
l.push_back(1);
l.push_back(2);
l.push_back(3);
l.unique(); reverse // reverse函数用于将容器当中元素的位置进行逆置
listint l();
l.push_back(0);
l.push_back(1);
l.push_back(2);
l.push_back(3);
l.reverse();迭代器的实现 // 简单定义一下list的结构
templateclass T
class list_node // 结点
{T _data;list_nodeT* _next;list_nodeT* _prev;list_node(const T x T()):_data(x),_next(nullptr),_prev(nullptr){}
};templateclass T
struct __list_iterator // 这里使用struct不用考虑class的权限
{typedef list_nodeT Node;typedef __list_iteratorT iterator;Node* _node; // 迭代器还是结点的指针__list_iterator(Node* node) // 用指针初始化迭代器:_node(node){}bool operator!(const iterator it) const{return _node ! it._node; // 判断两个迭代器指针不等就可以了}T operator*(){return _node-_data; // 解引用就是拿到结点指向的值}T* operator-() // -运算符是使用指针来访问成员{return (operator*()); // 拿到指针指向的数据再取地址返回这个指针类型}iterator operator() // 就把下一个结点的指针赋值给_node注意这是前置{_node _node-_next;return *this;}
};templateclass T
class list
{typedef list_nodeT Node;
public:typedef __list_iteratorT iterator;void push_back(const T x){Node* tail _head-_prev;Node* newnode new Node(x);tail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;}iterator begin() // begin就是头结点的下一个{return iterator(_head-_next); // 使用头结点的下一个的指针构造迭代器}iterator end() // end就是头结点{return iterator(_head-_prev);}list() // 构造函数{_head new Node;_head-_next _head;_head-_prev _head;}
public:Node* _head;
};void test01()
{listint l;l.push_back(1);l.push_back(2);listint::iterator it l.begin();while (it ! l.end()){cout it-_data endl; // 使用-运算符重载有的时候list中存放的不是int类型的数据只使用一次it-是不够的// 比如一个坐标类型有两个成员变量it-只能拿到这个坐标类型的指针// 但是还不能访问到这个类型的成员所以需要使用it--// 但这样又会显得很奇怪所以编译器为了增加可读性进行了特殊处理所以用一个-就可以了it;}
} // 既然有了正常的迭代器那如果是const对象呢
// const对象使用正常迭代器时会出现权限的放大不可以被修改
// 那有一个返回const类型的函数就可以了例如下面这个函数T opeartor*()
{}
// 这里可以添加一个返回const类型的函数
// 但是只有返回类型不一样不能构成重载
// 所以笨方法就是再写一个const迭代器类这个类除了返回值不一样其他的基本都一样
// 但是很忌讳这样写// 可以这样该一下模板参数
templateclass T, class Ref, class Ptr // Ref就是引用Ptr就是指针
struct __list_iterator
{typedef __list_iteratorT, Ref, Ptr iterator;// ...
}// operator*()就可以修改为
Ref opeartor*()
{}// operator-()可以修改为
Ptr operator-()
{}templateclass T
class list
{typedef list_nodeT Node;
public:typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;const_iterator cbegin() const{return cosnt_iterator(_head-_next);}const_iterator cend() const{return cosnt_iterator(_head);}// ...
}
