【C++】STL容器、算法的简单认识

几种模板

首先认识一下函数模板、类模板、栈模板。

函数模板

函数模板就是一个模型，而模板函数是函数模板经过类型实例化的函数。

如下template<class T>是一个简单的函数模板：

template<class T>
T Max(T a, T b)
{return a > b ? a : b;
}
int main()
{cout << Max(2, 5) << endl;//与Max匹配的函数叫模板函数cout << Max('t', 'a') << endl;//使用模板不受限于它的类型
}

也可以一次定义几个不同类型

template<class T1, class T2>
void fn(T1 a, T2 b)
{cout << a << " " << b << endl;
}
void main()
{fn('a', 5);
}

类模板

类模板不是类，需要经过参数实例化之后才是可以用的类（创建对象的时候告诉类模板<类型>）

template<class T>
class A
{
public:A(int i=0):m_i(i){}void print() { cout << m_i << endl; }
private:T m_i
};
int main()
{//A a;//errA<int> a(10);//这样经过参数实例化之后才是可以用的类a.print();
}

使用栈模板

自己模拟栈要很长一段代码：

#define SIZE 10
template<class T>
class SeqStack
{
public:SeqStack(){m_capacity = SIZE;m_data = new T[m_capacity];m_top = -1;}~SeqStack(){delete[]m_data;m_data = nullptr;}void Push(int v){if (IsFull())return;m_data[++m_top] = v;}void Pop(){if (IsEmpty()){return;}m_top--;}bool IsEmpty(){return m_top == -1;}bool IsFull(){return m_top >= m_capacity - 1;}int GetTop()  //要优化{if (IsEmpty())return 0;return m_data[m_top];}
private:T* m_data;int m_top;int m_capacity;
};
int main()
{SeqStack<int> ss;ss.Push(1);ss.Push(2);ss.Push(3);while (!ss.IsEmpty()){cout << ss.GetTop() << " ";ss.Pop();}
}

栈模板就可以直接用，带上头文件#include<stack>，很方便，效果跟自己模拟是一样的

int main()
{stack<int> ss;ss.push(1);ss.push(2);ss.push(3);while (!ss.empty()){cout << ss.top() << endl;ss.pop();}
}

---

STL 标准模板库

STL的重要的组件：容器、算法、迭代器

容器：存放数据

算法：操作数据

迭代器：容器和算法之间的粘合器——通过迭代器把容器里的东西取出，给算法操作（指针）

STL是泛型程序库：所有组件可以针对任意型别运作。

使用

例：从标准输入读取一段整数，将这些整数存放在一个动态开辟的数组中，数组的

第一个元素存储整数的个数，以后依次是这些整数。

void main()
{vector<int> vv;copy(istream_iterator<int>(cin), istream_iterator<int>(),back_insert_iterator<vector<int>>(vv));copy(vv.begin(), vv.end(), ostream_iterator<int>(cout, " "));
}

容器

•容器：用来管理某类对象的集合。容纳特定数据类型对象的集合,STL容器是将最常用的一些数据结构实现出来.包含了许多数据结构,如:vector,queue,statck…,string也可以看作是一个容器.

•分类:容器用来管理一组元素，为了适应不同需要，STL根据数据在容器中排列的特性,容器可分为序列式容器和关联式容器两种.

•序列式容器:可序群集，其中每个元素都有固定位置——取决于插入时机和地点,与元素的值没有关系,如果你以追加方式对一个群集置入n个元素，它们的排列次序将和置入次序一致。如vector,deque,list

•关联式容器:已序群集，元素位置取决于特定的排序准则,和插入顺序无关。如果你将n个元素置入这样的群集中，它们的位置取决于元素值，和插入次序无关。STL提供了4个这样的容器：set,map，。multiset，multimap。

关联式容器也可被视为特殊的序列式容器，因为已序群集正是根据某个排序准则排列而成。

vector容器

向量（Vector）是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。

vector:将其元素置于一个动态数组中加以管理，是一种动态数组，是基本数组的类模板，用于代替数组，支持随机存取。

int main()
{vector<int> v;//v里面的构造方法vector<int> v1(5);//5个0vector<int> v2(4, 7);//4个7int arr[5] = { 1,2,3,4,5 };vector<int> v3(arr,arr+5);//1，2，3，4，5for (int i = 0; i < v2.size(); i++)cout << v2[i] << " ";cout << endl;v.push_back(1);v.push_back(2);v.push_back(40);v.push_back(3);for (int i = 0; i < v.size(); i++)cout << v[i] << " ";cout << endl;
}

普通二维数组必须定义列数，如a[][3]，但vector的每行列数可以不一样

void main()
{vector<int> v;vector<vector<int>> vv;//vv相当于一个二维数组v.push_back(1);//1vv.push_back(v);//1v.push_back(2);//1 2vv.push_back(v);
//1    
//1 2v.push_back(3);//1 2 3vv.push_back(v);
//1
//1 2    
//1 2 3for (int i = 0; i < vv.size(); i++){for (int j = 0; j < vv[i].size(); j++)cout << vv[i][j] << " ";cout << endl;}
}

vector定义后不能直接赋值，必须有东西存进去再修改

void main()
{vector<int> v;//v.resize(5);v[0] = 5;
//这相当于下面这两行，是不行的//int a;//a[0] = 6;
}

---

算法

•算法：用来处理群集内的元素。它们可以出于不同的目的而搜寻，排序，修改，使用那些元素。是一种应用在容器上以各种方法处理其内存的行为或功能,如sort(排序),copy(拷贝)…,算法由模板函数体现,这些函数不是容器类的成员函数，是独立的函数,它们可以用于STL容器,也可以用于普通的C++数组等.

•头文件：#include<algorithm>在STL的泛型算法中有4类基本的算法：

•1)变序型队列算法: 可以改变容器内的数据；

•2)非变序型队列算法:处理容器内的数据而不改变他们；

•3)排序值算法:包涵对容器中的值进行排序和合并的算法，还有二叉搜 索算法 ,

•4)通用数值算法：此种算法不多，涉及到专业领域中有用的算术操作，独立包涵于头文件<numeric>中，在此不多做解释

排序sort()

使用必须加上头文件#include<algorithm>。

sort默认是做非递减排序，用的类模板，这个自己也可以模拟，如下：

自己也可以写个函数传入sort使其做非递增排序。

bool great(int a, int b)
{return a > b;
}
template<class T>
class Great
{
public:bool operator()(T a, T b){return a > b;}
};
void main()
{int a[] = { 1,3,2,5,4,7,6,9,8,0 };int n = sizeof(a) / sizeof(a[0]);//sort(a, a + n,greater<int>());//sort(a, a + n, great);//函数模板，用函数名当做函数指针传入sort(a, a + n, Great<int>());//类模板，运用了（）的重载for (int i = 0; i < n; i++)cout << a[i] << " ";cout << endl;
}

遍历for_each()

for_each()函数是C++ STL中的一个遍历函数，函数原型如下：

for_each(InputIterator first, InputIterator last, Function functor);

拷贝copy()

复制 [first, last) 所定义的范围中的元素到始于 d_first 的另一范围。

函数原型：

template<class InputIterator, class OutputIterator>  
inline OutputIterator copy(  InputIterator first,   InputIterator last,   OutputIterator result  
);

for_each()和copy()的使用：

void print(int n)
{cout << n << " ";
}
int s = 0;
void Sum(int n)
{s = s + n;
}
void main()
{int a[5] = { 1,2,3,4,5 };int b[5];copy(a, a + 5, b);//把[a,a+n)复制到b//    copy(b, b + 5, ostream_iterator<int>(cout, ","));for_each(b, b + 5, print);//输出12345for_each(b, b + 5, Sum);//输出15cout << "s = " << s << endl;
}

反转函数reverse

将区间[iterator1,iterator2)内的元素反转

交换swap_ranges

函数原型：

template<typename T1, typename T2>void swap(std::pair<T1,T2> left, std::pair<T1,T2> right);

前两个参数分别是第一个序列的开始和结束迭代器，第三个参数是第二个序列的开始迭代器。显然，这两个序列的长度必须相同。这个算法会返回一个迭代器，它指向第二个序列的最后一个被交换元素的下一个位置。

使用：

bool great5(int n)
{return n > 5;
}
template<class T>
class Less5
{
public:bool operator()(T n){return n < 5;}
};
void main()
{int a[] = { 1,2,3,4,5 };int b[] = { 6,7,8,9,0 };int n = sizeof(a) / sizeof(a[0]);int* p = find(a, a + n, 15);cout << *(p - 1) << endl;p = find_if(a, a + n, great5);cout << *p << endl;p = find_if(a, a + n, Less5<int>());cout << *p << endl;reverse(a, a + n);swap_ranges(a, a + 3, b);cout << count(a, a + 5, 2) << endl;cout << count_if(a, a + 5, Less5<int>()) << endl;
}

判断包含关系includes

函数原型

template <class InputIterator1, class InputIterator2, class Compare>bool includes ( InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2, Compare comp );

测试 [first1,last1)里面是否包含了[first2,last2)里面的所有元素。

int main(void)
{int a[10] = { 12,0,5,3,6,8,9,34,32,18 };int b[5] = { 5,3,6,8,9 };int d[15];sort(a, a + 10);for (int i = 0; i < 10; i++)cout << " " << a[i];sort(b, b + 5);  // 3 5 6 8 9if (includes(a, a + 10, b, b + 5))  //一个数组是否包含另外一个数组cout << "\n" << "sorted b members are included in a." << endl;elsecout << "sorted a dosn`t contain sorted b!";merge(a, a + 10, b, b + 5, d); //合并for (int j = 0; j < 15; j++)cout << "  " << d[j];return 0;
}

归并排序merge

merge只有归并部分，使用它必须是两个有序数组经行归并（先用sort()排序）

void main()
{int a[5] = { 5,4,1,2,3 };int b[5] = { 6,8,1,4,6 };int c[10];sort(a, a + 5);sort(b, b + 5);merge(a, a + 5, b, b + 5, c);
}