【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);
}