本人小白一枚,在这里和大家分享一些编程日常,希望大佬们多多支持!!!❤️❤️❤️
容器
容器(Containers):用来管理某类对象的集合。各种数据结构,如vector、list、deque、set、map等,用来存放数据,从实现角度来看,STL容器是一种 class template
。
迭代器
迭代器
(Iterators):用来在一个对象集合的元素上进行遍历动作。扮演了容器与算法之间的胶合剂,共有五种类型,从实现角度来看,迭代器是一种将operator* , operator-> , operator++, operator–等指针相关操作予以重载的class template。所有STL容器都附带有自己专属的迭代器,只有容器的设计者才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。
List
List 由
双向链表
(doubly linked list)实现而成,元素也存放在堆中,每个元素都是放在一块内存中,它的内存空间可以是不连续的,通过指针来进行数据的访问,这个特点使得它的随机存取变得非常没有效率,因此它没有提供 [] 操作符的重载。
但是由于链表的特点,它可以很有效率的支持任意地方的插入和删除操作。
访问开始和最后两个元素最快,其他元素的访问时间一样。
优缺点和适用场景
优点:内存不连续,动态操作,可在任意位置插入或删除且效率高。
缺点:不支持随机访问。
适用场景:适用于经常进行插入和删除操作并且不经常随机访问的场景。
源代码:
#include<iostream>
using namespace std;
template <class T>
struct Node {
public:
Node(T data):data(data){}//构造
Node(T data,Node<T>* next):data(data),next(next){}//构造
T& getdata() {//获取data
return data;
}
Node<T>* &getnext() {//获取next
return next;
}
protected:
T data;//数据域
Node<T>* next;//指针域
};
template <class T>
class List {
public:
List() {//构造
headNode =tailNode = nullptr;
cursize = 0;
}
~List() {//析构
Node<T>* pmove = headNode;
while (!empty()) {
delete pmove;
}
}
void push_front(T data) {//头插法
headNode = new Node<T>(data, headNode);
cursize++;
}
void push_back(T data) {//尾插法
Node<T>* newNode = new Node<T>(data);
tailNode->getnext() = newNode;
tailNode = newNode;
cursize++;
}
void pop_front() {//头删除
Node<T>* tempNode = headNode->getnext();
delete headNode;
headNode = tempNode;
cursize--;
}
void pop_back() {//尾删除
Node<T>* leftNode = headNode;
Node<T>* rightNode = headNode;
while (leftNode->getnext()) {
leftNode = rightNode;
rightNode = rightNode->getnext();
}
delete tailNode;
tailNode = leftNode;
tailNode->getnext() = nullptr;
cursize--;
}
int size() {//获取结点数量
return cursize;
}
protected:
Node<T>* headNode;//头节点
Node<T>* tailNode;//尾结点
int cursize;//结点数目
public:
class iterator {//内置迭代器
public:
iterator() {//构造
pmove = nullptr;
}
iterator(Node<T>* move):pmove(move){}//构造
iterator operator=(Node<T>* move) {
pmove = move;
return iterator(pmove);
}
bool operator!=(Node<T>* move) {//重载!=
return pmove != move;
}
void operator++(int) {//重载++
pmove = pmove->getnext();
}
T operator*() {//重载*
return pmove->getdata();
}
protected:
Node<T>* pmove;//移动指针
};
Node<T>* begin() {//获取头节点
return headNode;
}
Node<T>* end() {//获取尾节点
return tailNode;
}
bool empty() {//判断是否有结点
return cursize == 0;
}
};
测试代码:
void test() {
const int arraySize = 4;
string Man[arraySize] = { "何美人1号","何美人2号" ,"何美人3号","何美人4号" };
List<string> list;
for (int i = 0; i < arraySize; i++) {
list.push_front(Man[i]);
}
List<string>::iterator iter;
for (iter = list.begin(); iter != list.end(); iter++)
cout << *iter << endl;
cout << "......................"<<endl;
list.pop_front();
for (iter = list.begin(); iter != list.end(); iter++)
cout << *iter << endl;
cout << "......................"<<endl;
list.pop_back();
for (iter = list.begin(); iter != list.end(); iter++)
cout << *iter << endl;
return 0;
}
运行效果: