【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;//err
A<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个0
vector<int> v2(4, 7);//4个7
int arr[5] = { 1,2,3,4,5 };
vector<int> v3(arr,arr+5);//1，2，3，4，5
for (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);//1
vv.push_back(v);//1
v.push_back(2);//1 2
vv.push_back(v);
//1
//1 2
v.push_back(3);//1 2 3
vv.push_back(v);
//1
//1 2
//1 2 3
for (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);//输出12345
for_each(b, b + 5, Sum);//输出15
cout << "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 9
if (includes(a, a + 10, b, b + 5)) //一个数组是否包含另外一个数组
cout << "\n" << "sorted b members are included in a." << endl;
else
cout << "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);
}