STL 总结与常见面试题

#include<iostream>
#include<array>
using namespace std;
int main() 
{
	array<int, 8> myArr = {1,3,4,6,9};//固定大小为8
	cout << "myArr元素序列：";
	for (auto i = 0; i < 8; ++i) 
	{
		cout << myArr[i] << " ";
	}
	cout << endl;
	array<int, 8> myArr1 = {2,3,4,7,8,9};//固定大小为8
	cout << "myArr1元素序列：";
	for (auto i = 0; i < 8; ++i) 
	{
		cout << myArr1[i] << " ";
	}
	cout << endl;
	myArr.swap(myArr1);   //交换两个容器的内容
	cout << "交换myArr与myArr1"<< endl;
	cout << endl;
	cout << "myArr.at(3) = " << myArr.at(3) << endl;//任意访问
	cout << "myArr[3] = " << myArr[3] << endl;//任意访问
	cout << "myArr.front() = " << myArr.front() << endl;//获取第一个元素
	cout << "myArr.back() =  " << myArr.back() << endl;//获取最后一个元素
	cout << "myArr.data() = " << myArr.data() << endl;//获取第一个元素的指针
	cout << "*myArr.data() = " << *myArr.data() << endl;//获取第一个元素的指针指向的元素
	cout << "正向迭代器遍历容器：";
	for (auto it = myArr.begin(); it != myArr.end(); ++it) 
	{
		cout << *it << " ";
	}
	cout << endl;
	//逆向迭代器测试
	cout << "逆向迭代器遍历容器：";
	for (auto rit = myArr.rbegin(); rit != myArr.rend(); ++rit) 
	{
		cout << *rit << " ";
	}
	cout << endl;
	//正向常迭代器测试
	cout << "正向常迭代器遍历容器：";
	for (auto it = myArr.cbegin(); it != myArr.cend(); ++it) 
	{
		cout << *it << " ";
	}
	cout << endl;
	//逆向常迭代器测试
	cout << "逆向常迭代器遍历容器：";
	for (auto rit = myArr.crbegin(); rit != myArr.crend(); ++rit) 
	{
		cout << *rit << " ";
	}
	cout << endl;
	if(myArr.empty())
		cout << "myArr为空 " << endl;
	else
		cout << "myArr不为空 " << endl;
	cout << "myArr.size() = " << myArr.size() << endl;
	cout << "myArr.max_size() = " << myArr.max_size() << endl;
	return 0;
}

#include <vector>
#include <iostream>
using namespace std;
int main()
{
	//构造函数,复制构造函数(元素类型要一致),
	vector<int> vecA;  //创建一个空的的容器
	vector<int> vecB(10,20); //创建一个10个元素,每个元素值为20
	vector<int> vecC(vecB.begin(),vecB.end()); //使用迭代器,可以取部分元素创建一个新的容器
	vector<int> vecD(vecC); //复制构造函数,创建一个完全一样的容器
	//重载=
	vector<int> vecE;
	vecE = vecB;
	//vector::begin()，返回的是迭代器
	vector<int> vecF(10); //创建一个有10个元素的容器
	cout << "vecF:";
	for (int i = 0; i < 10; i++)
	{
		vecF[i] = i;
		cout << vecF[i]<< " ";
	}
	cout << endl;
	//vector::begin() 返回迭代器
	vector<int>::iterator Beginit = vecF.begin();
	cout<< "vecF.begin():" << *Beginit << endl; 
	//vector::end() 返回迭代器
	vector<int>::iterator EndIter = vecF.end();
	EndIter--; //向后移一个位置
	cout <<"vecF.end():"<< *EndIter << endl; 
	//vector::rbegin() 返回倒序的第一个元素，相当于最后一个元素
	vector<int>::reverse_iterator ReverBeIter = vecF.rbegin();
	cout << "vecF.rbegin(): "<< *ReverBeIter << endl; 
	//vector::rend() 反序的最后一个元素下一个位置，也相当于正序的第一个元素前一个位置
	vector<int>::reverse_iterator ReverEnIter = vecF.rend();
	ReverEnIter--;
	cout << "vecF.rend():"<< *ReverEnIter << endl; 
	//vector::size() 返回元素的个数
	cout << "vecF.size():"<< vecF.size() << endl; 
	//vector::max_size()
	cout << "vecF.max_size():"<< vecF.max_size() << endl; 
	//vector::resize()
	cout<< "vecF.size():" << vecF.size() << endl; 
	vecF.resize(5);
	cout<< "调整vecF大小后重新赋值:"; 
	for(int k = 0; k < vecF.size(); k++)
		cout << vecF[k] << "  "; 
	cout << endl;
	//vector::capacity()
	cout<< "调整后vecF.size():"<< vecF.size() << endl; 
	cout<< "调整后vecF.capacity():" << vecF.capacity() << endl; 
	//vector::empty()
	vecB.resize(0);
	cout<< "vecB.resize(0)后"<< endl; 
	cout  << "vecB.size():" << vecB.size() << endl; 
	cout  << "vecB.capacity():" << vecB.capacity() << endl; 
	if(vecB.empty())
	    cout << "vecB为空"<< endl; 
	else
		cout << "vecB不为空"<< endl; 
	//vector::reserve() //重新分配存储空间大小
	cout<< "vecC.capacity():" << vecC.capacity() << endl; //
	vecC.reserve(4);
	cout << "vecC.reserve(4)后vecC.capacity()： "<< vecC.capacity() << endl; //10
	vecC.reserve(14);
	cout << "vecC.reserve(14)后vecC.capacity()： "<< vecC.capacity() << endl; //14
	//vector::operator []
	cout << "vecF[0]:"<< vecF[0] << endl; //第一个元素是0
	//vector::at()
	try
	{
		cout << "vecF.size = " << vecF.size() << endl; //5
		cout << vecF.at(6) << endl; //抛出异常
	}
	catch(out_of_range)
	{	
		cout << "at()访问越界" << endl;
	}
	//vector::front() 返回第一个元素的值
	cout << "vecF.front():"<< vecF.front() << endl; //0
	//vector::back()
	cout << "vecF.back():"<< vecF.back() << endl; //4
	//vector::assign()
	cout <<"vecA.size():"<< vecA.size() << endl; //0
	vector<int>::iterator First = vecC.begin();
	vector<int>::iterator End = vecC.end()-2;
	vecA.assign(First,End);
	cout << vecA.size() << endl; //8
	cout << vecA.capacity() << endl; //8
	vecA.assign(5,3); //将丢弃原来的所有元素然后重新赋值
	cout << vecA.size() << endl; //5
	cout << vecA.capacity() << endl; //8
	//vector::push_back()
	cout << *(vecF.end()-1) << endl; //4
	vecF.push_back(20);
	cout << *(vecF.end()-1) << endl; //20
	//vector::pop_back()
	cout << *(vecF.end()-1) << endl; //20
	vecF.pop_back();
	cout << *(vecF.end()-1) << endl; //4
	//vector::swap()
	cout << "vecF:";
	for (int i = 0; i < vecF.size(); i++)
	{
		vecF[i] = i;
		cout << vecF[i]<< " ";
	}
	cout << endl;
	cout << "vecD:";
	for (int d = 0; d < vecD.size(); d++)
	{
		vecD[d] = d;
		cout << vecD[d]<< " ";
	}
	cout << endl;
	vecF.swap(vecD); //交换这两个容器的内容
	cout <<"vecD与vecF交换后：" <<endl;
	cout << "vecF:";
	for(int f = 0; f < vecF.size(); f++)
		cout << vecF[f] << " ";
	cout << endl;
	cout << "vecD:";
	for (int d = 0; d <vecD.size(); d++)
		cout << vecD[d] << " ";
	cout << endl;
	//vector::clear()
	vecF.clear();
	cout << "vecF.clear()后vecF.size()："<< vecF.size() << endl;     //0
	cout << "vecF.clear()后vecF.capacity()："<< vecF.capacity() << endl; //10
	return 0;
}

template<class T, class Alloc = alloc, size_t BufSiz = 0>  
class deque{  
public :  
    typedef T value_type ;  
    typedef value_type* pointer ;  
    ...  
protected :  
    //元素的指针的指针(pointer of pointer of T)  
    // 其实就是T**，一个二级指针，维护一个二维数组
    typedef pointer* map_pointer ; 
  
protected :  
    map_pointer map ; //指向map,map是块连续空间，其内的每个元素  
                      //都是一个指针(称为节点)，指向一块缓冲区  
    size_type map_size ;//map内可容纳多少指针  
    ...  
};  

#include "stdafx.h"
#include<iostream>
#include<deque>
 
using namespace std;
int main()
{
	deque<int> d;
	d.push_back( 11 );//在 deque 容器的末尾添加一个新元素
	d.push_back(20);
	d.push_back(35);
	cout<<"初始化双端队列d："<<endl;
	for(int i = 0; i < d.size(); i++)
	{
		cout<<d.at(i)<<"\t";
	}
	cout<<endl;
	d.push_front(10);//容器的开始位置插入一个新的元素，位于当前的第一个元素之前
	d.push_front(7);
	d.push_front(1);
 
	cout<<"队列d向前陆续插入10、7、1:"<<endl;
	for(int i = 0;i < d.size();i++)
	{
		cout<<d.at(i)<<"\t";
	}
	cout<<endl;
	d.pop_back(); //删除 deque 容器中的最后一个元素，有效地将容器大小减少一个
	d.pop_front(); //删除 deque 容器中的第一个元素，有效地减小其大小
	cout<<"删除deque最后一个和第一个元素后:"<<endl;
	for(int i = 0;i < d.size();i++)
	{
		cout<<d.at(i)<<"\t";
	}
	cout<<endl;
	return 0;
}

template<tyepname T,...>
struct __list_iterator{
    __list_node<T>* node;
    //...
    //重载 == 运算符
    bool operator==(const __list_iterator& x){return node == x.node;}
    //重载 != 运算符
    bool operator!=(const __list_iterator& x){return node != x.node;}
    //重载 * 运算符，返回引用类型
    T* operator *() const {return *(node).myval;}
    //重载前置 ++ 运算符
    __list_iterator<T>& operator ++(){
        node = (*node).next;
        return *this;
    }
    //重载后置 ++ 运算符
    __list_iterator<T>& operator ++(int){
        __list_iterator<T> tmp = *this;
        ++(*this);
        return tmp;
    }
    //重载前置 -- 运算符
    __list_iterator<T>& operator--(){
        node = (*node).prev;
        return *this;
    }
    //重载后置 -- 运算符
    __list_iterator<T> operator--(int){
        __list_iterator<T> tmp = *this;
        --(*this);
        return tmp;
    }
    //...
}

//deque<T> >中间有个空格是为了兼容较老的版本
template <class T, class Sequence = deque<T> >
class stack {
    // 以㆘的 __STL_NULL_TMPL_ARGS 会开展为 <>
    friend bool operator== __STL_NULL_TMPL_ARGS (const stack&, const stack&);
    friend bool operator< __STL_NULL_TMPL_ARGS (const stack&, const stack&);
public:
    typedef typename Sequence::value_type value_type;
    typedef typename Sequence::size_type size_type;
    typedef typename Sequence::reference reference;
    typedef typename Sequence::const_reference const_reference;
protected:
    Sequence c; // 底层容器
public:
    // 以㆘完全利用 Sequence c 的操作，完成 stack 的操作。
    bool empty() const { return c.empty(); }
    size_type size() const { return c.size(); }
    reference top() { return c.back(); }
    const_reference top() const { return c.back(); }
    // deque 是两头可进出，stack 是末端进，末端出（所以后进者先出）。
    void push(const value_type& x) { c.push_back(x); }
    void pop() { c.pop_back(); }
};
template <class T, class Sequence>
bool operator==(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
    return x.c == y.c;
}
template <class T, class Sequence>
bool operator<(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
    return x.c < y.c;
}

#include<stack>  
  #include<list>  
  #include<algorithm>  
  #include <iostream>  
  using namespace std;  
    
  int main(){  
      stack<int, list<int>> istack;  
      istack.push(1);  
      istack.push(3);  
      istack.push(5);  
        
      cout << istack.size() << endl; //3  
      cout << istack.top() << endl;//5  
      istack.pop();  
      cout << istack.top() << endl;//3  
      cout << istack.size() << endl;//2  
    
      system("pause");  
      return 0;  
  }  

template <class T, class Sequence = deque<T> >
class queue {
  friend bool operator== __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
  friend bool operator< __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
public:
  typedef typename Sequence::value_type value_type;
  typedef typename Sequence::size_type size_type;
  typedef typename Sequence::reference reference;
  typedef typename Sequence::const_reference const_reference;
protected:
  Sequence c;
public:
  bool empty() const { return c.empty(); }
  size_type size() const { return c.size(); }
  reference front() { return c.front(); }
  const_reference front() const { return c.front(); }
  reference back() { return c.back(); }
  const_reference back() const { return c.back(); }
  void push(const value_type& x) { c.push_back(x); }
  void pop() { c.pop_front(); }
};
template <class T, class Sequence>
bool operator==(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {
  return x.c == y.c;
}
template <class T, class Sequence>
bool operator<(const queue<T, Sequence>& x, const queue<T, Sequence>& y) {
  return x.c < y.c;
}

template<class _Kty,
    class _Pr = less<_Kty>,
    class _Alloc = allocator<_Kty> >
class set