c++ 容器STL

分手后的思念是犯贱 2022-03-16 09:40 361阅读 0赞

STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），几乎所有的代码都采用了模板类和模版函数的方式，这相比于传统的由函数和类  
容器部分主要由头文件`<vector>,<list>,<deque>,<set>,<map>,<stack>和<queue>`组成。对于常用的一些容器和容器适配器（可以看作由其它容器实现的容器），现在来总结一下它们。  
1，vector的应用

#include <iostream>
    #include <vector>
    using namespace std;
    void print(vector<int>& v)
    {
    	for (auto m : v)
    		cout << m << "=";
    	cout << endl;
    }
    int main()
    {
    	int a[4];
    	//size() 为0
    	vector<int> v0;
    	//	初始化成n个默认值
    	vector<int> v1(-1);
    //	cout << v1.size() << endl;
    					 //n value
    	vector<string> v2(4, "hello");
    	//拷贝初始化
    	auto v3 = v2;
    	//列表初始化
    	vector<int> v4{2, 3, 4, 65};
    		//		   |			|
    		//		  begin()		end()
    	vector<int> v5 = {22, 31};
    	for (int i=0; i<v5.size(); i++)
    		cout << v5[i] << endl;
    	
    	for (auto m : v4)
    		cout << m << " ";
    	cout << endl;
    	//使用迭代器访问动态数组的成员
    	//it相当于一个指针，指向数组的某个位置
    	for (vector<int> ::iterator it = v4.begin();
    			it != v4.end(); it++)
    		cout << *it << ", ";
    	cout << endl;
    	
    	for (auto it = v3.begin(); it != v3.end(); it++)
    		cout << *it << "-";
    	cout << endl;
    	cout << "增加" << endl;
    	auto it = v5.begin();
      //	it++;
    	//插入在it的位置, 需要获得返回值,返回值是新的迭代器位置
    	vector<int> ::iterator p;
    	//	(iterator pos, value)
    	p = it = v5.insert(it, 90);
    	it = v5.insert(it, 91);
    	it = v5.insert(it, 92);
    	cout << &v5[0] << endl;
    	p = v5.erase(p);
    	p = v5.erase(p);
    	cout << v5.size() << endl;
    	cout << &v5[0] << endl;
    // 如果it不更新，it指向的还是旧的空间所在的位置
    	v5.push_back(1);
    	v5.push_back(2);
    	print(v5);
    	cout << "删除" << endl;
    	v5.pop_back();
    	v5.pop_back();
    	print(v5);
    //	for (int i=0; i<20; i++)//	访问了非法空间
    //		cout << v5[i] << endl;
    	return 0;
    }

2,vector的实现

#include <iostream>
    using namespace std;
    template <typename T>
    class Stack
    {
    	T* ptr;
    	int len;
    	int max;
    public:
    	Stack() : ptr(nullptr), len(0), max(4) {
    	}
    	//拷贝构造
    	~Stack() {
    		delete[] ptr;
    	}
    	int size() {
    		return len;
    	}
    	bool empty() {
    		return len == 0;
    	}
    	void push(const T& t) {
    		if (ptr == nullptr) {
    			ptr = new T[max];
    		} else if (len >= max) {
    			max *= 2;
    			T* pnew = new T[max];
    			for (int i=0; i<len; i++) {
    				pnew[i] = ptr[i];
    			}
    			delete [] ptr;
    			ptr = pnew;
    		}
    		ptr[len++] = t;
    	}
    	void pop() {
    		if (len > 0)
    			len--;
    	}
    	T& top() {
    		if (len == 0)
    			return ptr[0];
    		return ptr[len-1];
    	}
    };

3，list的应用

#include <iostream>
    //双向链表
    #include <list>
    using namespace std;
    int main()
    {
    	//0个结点
    	list<int> l0;
    	cout << "size = " << l0.size() << endl;
    	cout << l0.front() << endl;
    	cout << l0.back() << endl;
    	l0.front() = 90;
    	cout << l0.front() << endl;
    	cout << l0.back() << endl;
    //	l0.resize(1);
    //	cout << l0.front() << endl;
    //	cout << l0.back() << endl;
    	
    	//n个结点，每个都是默认值
    	list<int> l1(4);
    	//n个结点，都是value
    	list<int> l2(4, 10);
    	list<int> l3 = {2, 3, 4};
    	list<int> l4(l3);
    	l2.empty();
    	l2.size();
    	l2.pop_back();
    	l2.pop_front();
    	l2.push_front(12);
    	l2.push_back(34);
    	for (list<int>::iterator it = l2.begin();
    			it != l2.end(); it++)
    		cout << *it << ", ";
    	cout << endl;
    	//删除所有值为value的结点
    	l2.remove(10);
    	//list内的成员方法，从小到大排序
    	l2.sort();
    	//l2.insert(it, value); 
    	//l2.erase(it);
    	cout << "front = " << l2.front() << endl;
    	//头
    	l2.front() = 100;
    	//尾
    	l2.back() = 200;
    	for (auto m : l2)
    		cout << m << " ";
    	cout << endl;
    	return 0;
    }

4，list（双向链表）的实现

#include <iostream>
    using namespace std;
    template <typename T>
    class List
    {
    	struct Node {
    		T value;
    		Node* prev;
    		Node* next;
    	};
    	Node* head;
    	Node* tail;
    	int len;
    public:
    	class Iterator {
    		Node* pi;
    	public:
    		Iterator() : pi(nullptr) { }
    		Iterator(Node* p) : pi(p) { }
    		Iterator& operator++() {
    			pi = pi->next;
    			return *this;
    		}
    		Iterator operator++(int) {
    			Iterator t(pi);
    			pi = pi->next;
    			return t;
    		}
    		Iterator& operator--() {
    			pi = pi->prev;
    			return *this;
    		}
    		Iterator operator--(int) {
    			Iterator t(pi);
    			pi = pi->prev;
    			return t;
    		}
    		bool operator==(const Iterator& it) {
    			return pi == it.pi;
    		}
    		bool operator!=(const Iterator& it) {
    			return pi != it.pi;
    		}
    		T& operator*() {
    			return pi->value;
    		}
    		T* operator->() {
    			return &pi->value;
    		}
    	};
    	List() : len(0) {
    		head = tail = new Node{};
    	}
    	List(int n) : head(nullptr), tail(nullptr), len(n){
    		Node* p = nullptr;
    		p = new Node{};
    		head = tail = p;
    		for (int i=0; i<n-1; i++) {
    			p = new Node{};	
    			tail->next = p;
    			p->prev = tail;
    			tail = p;
    		}
    	}
    	void show() {
    		Node* p = head;
    		while(p) {
    			cout << p->value << endl;
    			p = p->next;
    		}
    	}
    	List(int n, const T& v) : len(n) {
    		head = tail = new Node{v, nullptr, nullptr};
    		for (int i=0; i<n-1; i++) {
    			tail->next = new Node{v, tail, nullptr};
    			tail = tail->next;
    		}
    	}
    	List(const List& l) : len(l.len) {
    		Node* p = l.head;
    		head = tail = new Node{p->value, nullptr, nullptr};
    		p = p->next;
    		while(p) {
    			tail->next = new Node{p->value, tail, nullptr};
    			tail = tail->next;
    			p = p->next;
    		}
    	}
    	~List() {
    		Node* p = head;
    		while(head) {
    			cout << "delete " << p->value << endl;
    			p = head->next;
    			delete head;
    			head = p;
    		}
    	}
    	T& front() {
    		return head->value;
    	}
    	T& back() {
    		return tail->value;
    	}
    	int size() {
    		return len;
    	}
    	bool empty() {
    		return len == 0;
    	}
    	void push_back(const T& t) {
    		if (len != 0) {
    			tail->next = new Node{t, tail, nullptr};
    			tail = tail->next;
    		} else { 
    			head->value = t;
    		}
    		len++;
    	}
    	void push_front(const T& t) {
    		if (len !=0 ) {
    			head->prev = new Node{t, nullptr, head};
    			head = head->prev;
    		} else {
    			head->value = t;
    		}
    		len++;
    	}
    	void pop_back() {
    		if (len > 1) {
    			tail->prev->next = nullptr;
    			Node* p = tail;
    			tail = tail->prev;
    			delete p;
    			len--;
    		} else if (len == 1) {
    			len = 0;
    		} 
    	}
    	void pop_front() {
    		if (len > 1) {
    			Node* p = head;
    			head = head->next;
    			head->prev = nullptr;
    			delete p;
    			len--;
    		} else if (len == 1) 
    			len = 0;
    	}
    
    	void remove(const T& t) {
    		Node* p = head;
    		if (len == 0)
    			return;
    		while(p) {
    			if (p->value == t) {
    				if (len == 1)
    					len = 0;
    				else if (p == head) {
    					pop_front();
    					p = head;
    				} else if (p == tail) {
    					pop_back();
    					//return;
    					p = nullptr;
    				} else {
    					p->next->prev = p->prev;
    					p->prev->next = p->next;
    					Node* t = p->next;
    					delete p;
    					len--;
    					p = t;
    				}
    			} else
    				p = p->next;
    		}
    	}
    	Iterator begin() {
    		return Iterator(head);	
    	}
    	Iterator end() {
    		return Iterator(tail->next);
    	}
    };

5，栈的应用

#include <iostream>
    #include <stack
    using namespace std;
    int main()
    {
    	stack<int> s1;
    	cout << "top = " << s1.top() << endl;
    	cout << "size = " << s1.size() << endl;
    	s1.push(2);
    	s1.push(20);
    	s1.push(20);
    	cout << s1.top() << endl;
    	s1.top() = 30;
    	cout << "top = " << s1.top() << endl;
    	cout << "size = " << s1.size() << endl;
    	cout << s1.empty() << endl;
    	s1.pop();
    	cout << "size = " << s1.size() << endl;
    	if (s1.empty())
    		cout << "栈为空" << endl;
    	else
    		cout << "top = " << s1.top() << endl;
    	return 0;
    }

6，栈的实现

#include <iostream>
    using namespace std;
    
    template <typename T>
    class Stack
    {
    	T* ptr;
    	int len;
    	int max;
    public:
    	Stack() : ptr(nullptr), len(0), max(4) {
    	}
    	//拷贝构造
    	~Stack() {
    		delete[] ptr;
    	}
    	int size() {
    		return len;
    	}
    	bool empty() {
    		return len == 0;
    	}
    	void push(const T& t) {
    		if (ptr == nullptr) {
    			ptr = new T[max];
    		} else if (len >= max) {
    			max *= 2;
    			T* pnew = new T[max];
    			for (int i=0; i<len; i++) {
    				pnew[i] = ptr[i];
    			}
    			delete [] ptr;
    			ptr = pnew;
    		}
    		ptr[len++] = t;
    	}
    	void pop() {
    		if (len > 0)
    			len--;
    	}
    	T& top() {
    		if (len == 0)
    			return ptr[0];
    		return ptr[len-1];
    	}
    };

关联容器  
7 pair的实现和应用

#include <iostream>
    #include <vector>
    using namespace std;
    
    template <typename T1, typename T2>
    struct Pair
    {
    	T1 first;
    	T2 second;
    	Pair() { }
    	Pair(const T1& t1, const T2& t2) : first(t1), second(t2) { }
    	bool operator==(const Pair& p) const {
    		return first==p.first && second==p.second;
    	}
    	bool operator<(const Pair& p) const {
    		if (first < p.first) 
    			return true;
    		else if (first==p.first && second < p.second)
    			return true;
    		return false;
    	}	
    	bool operator>(const Pair& p) const {
    		return !(p < *this || p == *this);
    	}
    	bool operator<=(const Pair& p) const {
    		return *this < p || *this == p;
    	}
    	//>= != 
    };
    int main()
    {
    	Pair<string, int> p1("hello", 123);
    	Pair<string, int> p2("hello", 123);
    	Pair<int, Pair<int, string> > p3(100, Pair<int, string>(200, "world"));
    	cout << p3.first << " " << p3.second.first << " "
    		<< p3.second.second << endl;
    	Pair<int, string[4] > p4;
    	p4.first = 1;
    	/*
    	p4.second.push_back("hello");
    	p4.second.push_back("asd");
    	*/
    	p4.second[0] = "fds";
    	p4.second[1] = "fdss";
    	cout << p4.first << " ";
    	for (auto m : p4.second) 
    		cout << m << ", ";
    	cout << endl;
    	cout << p1.first << " " << p1.second << endl;
    	cout << p2.first << " " << p2.second << endl;
    	if (p1 == p2) {
    		cout << "==" << endl;
    	} else if (p1 < p2) {
    		cout << "<" << endl;
    	} else if (p1 > p2) {
    		cout << ">" << endl;
    	}
    };

8,map的应用（实现后序补充）

#include <iostream>
    #include <map>
    //映射
    using namespace std;
    
    int main()
    {
    	pair<int, string> p;
    	//key是唯一的，有序
    	//  key	 value
    	map<int, string> m;
    	//make_pair()函数是制作一个pair
    	m.insert(make_pair(1003, "Cindy"));
    	m.insert({1002, "Mike"});
    	m.insert(pair<int, string>(1001, "Tom"));
    	//如果key 有相同的，后面的插入会失败
    	//pair<iterator, bool>
    	auto b = m.insert({1002, "David"});
    	cout << b.second << endl;
    
    	bool x = m.erase(1002);
    	cout << x << endl;
    	
    	//m[key] 可以查找key对应的value
    	m[1001] = "Bob";
    	cout << m[1001] << endl;
    	//m[key]如果没有key, m会增加一个pair
    	cout << m[2000] << endl;
    	//增加一个pair
    	m[1003] = "An";
    	//m.find(key), 如果找到key，返回相应的位置，如果没有找到，返回 m.end() 位置
    	map<int, string> ::iterator i = m.find(1011);
    	if (i != m.end()) {
    		cout << "找到了 ";
    		cout << i->first << " " << i->second << endl;
    	} else {
    		cout << "没有找到" << endl; 
    	}
    	//upper_bound(key) 返回大于key的位置
    	auto it1 = m.upper_bound(1001);
    	//lower_bound(key) 返回不小于key的位置
    	auto it2 = m.lower_bound(1001);
    
    	cout << "it1 " << it1->first << " " << it1->second << endl; 
    	cout << "it2 " << it2->first << " " << it2->second << endl; 
    	//pair<map<>::iterator, map<>::iterator> 返回上面两个位置
    	auto it3 = m.equal_range(1001);
    	cout << "it3 l " << it3.first->first << " " <<
    		it3.first->second << endl;
    	cout << "it3 u " << it3.second->first << " " << 
    		it3.second->second << endl;
    	
    	for (auto i : m) {
    		cout << i.first << " " << i.second << endl;
    	}
    	for (auto it = m.begin(); it != m.end(); it++) {
    		cout << it->first << "," << it->second << endl;
    	}
    	return 0;
    }

9,set的实现和使用（后序补充）