目录
C++提高编程
- 本阶段主要针对C++泛型编程和STL技术做详细讲解
模版
- C++另一种编程思想称为泛型编程,主要利用的技术就是模版
- C++提供两种模版机制:函数模版和类模版
- 函数模板
建立一个通用函数,可以不指定函数返回值类型和参数类型
// 利用myswap模板函数,进行交换
#include <iostream>
using namespace std;
template<typename T> // typename可以替换为class
void myswap(T& a, T&b) {
T temp;
temp = a;
a = b;
b = temp;
}
int main() {
int a = 1, b = 2;
char c = 'c', d = 'd';
myswap(a, b);
myswap(c, d);
return 0;
}
模板函数的调用有两种方式:自动类型推导、显示指定类型
- 自动类型推导
myswap(a, b); // 直接传入变量,编译器会推导出类型
- 显示指定类型
myswap<int>(a, b); // 告诉编译器,模板类型是int
注意事项:
- 自动类型推导,必须推导出一致的数据类型才可以使用
- 模板必须要确定出T的数据类型才可以使用
- 函数模板案例
- 利用函数模板封装一个排序的函数,可以对不同的数据类型进行排序
#include <iostream>
using namespace std;
template<class T>
void my_Sort(T array[], int len) {
for (int i = 0; i < len; i ++ ) {
int max = i;
for (int j = i + 1; j < len; j ++ ) {
if (array[i] < array[j]) {
max = j;
}
}
swap(array[i], array[max]);
}
}
int main() {
char array[] = "abcdef";
my_Sort(array, 6);
for (int i = 0; i < 6; i ++ ) cout << array[i]; // 输出结果为 fedcba
int newarray[] = {1, 2, 3};
my_Sort(newarray, 3);
for (int i = 0; i < 3; i ++ ) cout << newarray[i]; // 输出结果为 321
}
- 普通函数与函数模板区别
- 普通函数调用时可以发生隐式类型转换
int myAdd(int a, int b) {
return a + b;
}
int a = 10;
char b = 'c';
myAdd(a, b); // 可以正常执行,字符c会被转为整形,然后进行相加
- 函数模板 用自动类型推导 不可以发生隐式类型转换
template<class T>
T myAdd(T a, T b) {
return a + b;
}
int a = 10;
char b = 'c';
myAdd(a, b); // 不可以正常执行,编译器无法确定T的类型
- 函数模板 用显示指定类型 可以发生隐式类型转换
和普通函数调用类似
- 普通函数和函数模板的调用规则
- 如果函数模板和普通函数都可以实现,优先调用普通函数
- 可以通过空模板参数列表来强制调用函数模板
- 函数模板也可以发生重载
- 如果函数模板可以产生更好的匹配优先调用函数模板
- 模板的局限性
略
学习模板并不是为了写模板,而时在STL中使用系统提供的模板
- 类模板
template<class NameType, class AgeType>
class Person {
NameType a;
AgeType b;
Person (NameType name, AgeType age) {
a = name;
b = age;
}
};
Person<string, int> p1("libai", 10);
- 类模板与函数模板区别
- 类模板没有自动类型推导的使用方式
- 类模板在模板参数列表中可以有默认参数
- 类模板中成员函数创建时机
- 只有在调用时才会创建
- 类模板对象做函数参数
- 指定传入的类型
template<class T1, class T2>
class Person {
public:
T1 name;
T2 age;
Person(T1 name, T2 age) {
this->name = name;
this->age = age;
}
void showInfo() {
cout << this->name << " " << this->age;
}
};
void printPerson(Person<string, int>& p) {
p.showInfo();
}
void test01() {
Person<string, int> p("libai", 1);
printPerson(p);
}
- 参数模板化
template<class T1, class T2>
class Person {
public:
T1 name;
T2 age;
Person(T1 name, T2 age) {
this->name = name;
this->age = age;
}
void showInfo() {
cout << this->name << " " << this->age;
}
};
template<class T1, class T2>
void printPerson(Person<T1, T2>& p) {
p.showInfo();
}
void test02() {
Person<string, int> p("wukong", 2);
printPerson(p);
}
- 整个类模板化
template<class T1, class T2>
class Person {
public:
T1 name;
T2 age;
Person(T1 name, T2 age) {
this->name = name;
this->age = age;
}
void showInfo() {
cout << this->name << " " << this->age;
}
};
template<class T>
void printPerson(T& p) {
p.showInfo();
}
void test02() {
Person<string, int> p("xixi", 3);
printPerson(p);
}
- 类模板与继承
- 当子类继承的父类是一个类模板时,子类在声明时,要指定类型
template<class T>
class Base {
T m;
}
class son : public Base<int> { // T为int
}
- 如果想灵活指定父类中的类型,字类也要是类模板
template<class T>
class Base {
T m;
}
template<class T1, class T2>
class son : public Base<T2> { // T为int
T1 obj;
}
son<int, char> s; // 声明了一个son对象,指定了T1为int T2为char,同时T2也是父类中的T
- 类模版的分文件编写
- 类模版中的成员函数只有在调用时才会创建
- 分文件编写会导致函数内容链接不到
解决方法:
- 直接包含.cpp文件
- 将.h和.cpp中的内容写到一起,将后缀名改为.hpp文件
- 类模版与友元
类外函数访问不到私有变量
STL初识
String
-
string是C++风格的字符串 而string本质是一个类
-
find函数,字符串匹配
string str = "hello world";
int pos = str.find("hello"); // 结果为0
- string的比较 按照ASCII码进行比较
string s1 = "hello";
string s2 = "hello";
str1.compare(s2); 返回0
-
字符串的存取 利用[]或at
-
string的插入
string s = "hello";
s.insert(1, "111"); // 在第1个位置前,插入"111"
s.erase(pos, 3); //从pos位置起,删除3个元素
- string子串
string str = "abcde";
string subStr = str.substr(1, 3); // 从第一个位置起,3个元素
Vector
- Vector与数组非常相似
- 构造函数
vector<int> v;
vector<int> v(n, 10);
vector<int> v1(v.begin(), v.end())
- 容量和大小
vector<int> v(10, 1);
v.resize(100); // 用0来填充
- 插入和删除
v.insert(v.begin(), 1);
v.erase(v.begin());
- 存取
v.front();
v.back();
- 互换
vector<int> v1(3, 1);
vector<int> v2(3, 2);
v1.swap(v2); // v1容器和v2容器互换
vector<int> v(10000, 1);
v.resize(10);
vector<int>(v).swap(v); // 收缩内存,v的容量变为10
- vector预留空间
reserve(int len); // 预留一部分空间,但是size不变
vector<int> v;
v.reserve(1000);
Deque
双端数组
vector对于头部的插入删除效率低
vector访问元素的速度会比deque快
- 内部实现
利用一个中控器
-
构造函数
-
赋值
-
大小
deque.empty()
deque.size()
deque.resize(n)
deque.resize(n, number)
deque<int> dq;
- 插入删除
deque<int> dq;
dq.push_back(1); // 尾插
dq.push_front(2); // 头插
dq.pop_back();
dq.pop_front();
dq.insert(dq.begin(), 1);
dq.insert(dq.begin(), newdq.begin(), newdq.end());
- 数据存取
Stack
- 构造函数
- 赋值操作
- 数据存取
- 大小操作
Queue
List
-
链表:将数据进行链式存储
-
STL中的链表是一个双向循环链表
-
链表的迭代器是一个双向迭代器,不支持随机访问
-
构造函数
list<int> l1;
l1.push_back(1);
list<int> l2(l1,begin(), l1.end());
list<int> l3(l2);
list<int> l4(10, 100);
- 赋值和交换
// 赋值
list<int> l1;
l1.push_back(1);
list<int> l2;
l2 = l1;
list<int> l3;
l3.assign(l2.begin(), l2.end());
list<int> l4;
l4.assign(10, 100);
// 交换
list<int> l1;
l1.push_back(1);
list<int> l2;
l2.assign(10, 100);
l1.swap(l2);
- 大小操作
list<int> l1;
l1.push_back(1);
l1.empty();
l1.resize(10); // 默认用0填充
- 插入和删除
list<int> l1;
l1.push_back(1);
l1.push_front(2);
l1.pop_back();
l1.pop_front();
l1.insert(l1.begin(), 100);
l1.erase(l1.begin());
l1.remove(1000); // 按照值删除
l1.clear();
- 数据存取
list是链表,不是用连续线性空间存储数据,迭代器不支持随机访问,所以不能用[]的方式访问
list<int> l1;
l1.push_back(1);
l1.front();
l1.back();
- 反转和排序
list<int> l1;
l1.push_back(1);
l1.reverse();
l1.sort(); // 通过写回调函数,可以实现自定义规则排序
Set
- set属于关联式容器,底层结构是用二叉树实现(红黑树)
- set不允许容器中有重复的元素
- multiset允许容器中有重复元素
- set容器在插入数据后会自动排序
set<int> a;
a.insert(1);
-
大小和交换
-
排序
利用仿函数来实现对set的排序
class campare {
public:
bool operator()(int v1, int v2) {
return v1 > v2;
}
};
set<int, campare> s;
s.insert(1);
Pair
- pair的创建
pair<char, int> a('c', 1);
pair<char, int> a = make_pair(c, 2);
Map
- map中所有元素都是pair
- key和value,key是索引
- 插入删除
map<int, int> a;
a.insert(make_pair(1, 1));
a.insert(pair<int, int>(2, 2));
a.earse(a.begin());
a.erase(1);
- 查找与统计
map<int, int> a;
auto it = a.find(1); // 返回的是迭代器
其它
函数对象
- 重载函数调用操作符的类,其对象称为函数对象
- 函数对象使用重载的()时,行为类似函数调用,也叫仿函数
- 函数对象使用时,可以像普通函数那样调用,可以有参数,可以有返回值
class Myadd {
public:
int operator()(int a, int b) {
return a + b;
}
};
void test01() {
Myadd a;
cout << a(10, 10) << endl;
}
int main() {
test01();
}
- 函数对象超出了普通函数的概念,函数对象可以有自己的状态
class Myprint {
public:
Myprint() {
this->count = 0;
}
void operator() (string s) {
cout << s << endl;
this->count ++;
}
int count; // 内部状态
};
void test02() {
Myprint s;
s("hello world");
s("hello world"); // count变为2
cout << s.count;
}
int main() {
test02();
}
- 函数对象可以作为参数进行传递
class Myprint {
public:
Myprint() {
this->count = 0;
}
void operator() (string s) {
cout << s << endl;
this->count ++;
}
int count; // 内部状态
};
void doPrint(Myprint& mp, string test) {
mp(test);
}
void test03() {
Myprint s;
doPrint(s, "hello world");
}
int main() {
test03();
}
谓词
- 一元谓词
- 返回bool类型的仿函数称为谓词
- 如果operator()接受一个参数,称为一元谓词
- 如果接受两个参数,称为二元谓词
class GreatFive {
public:
bool operator()(int a) {
return a > 5;
}
};
void test01() {
vector<int> a;
a.push_back(1);
a.push_back(2);
a.push_back(7);
vector<int>::iterator it = find_if(a.begin(), a.end(), GreatFive());
}
- 二元谓词
class Mycompare {
public:
bool operatoe()(int a, int b) {
return a > b;
}
}
void test01() {
vector<int> v;
v.push_back(1);
v.push_back(3);
v.push_back(-2);
// sort(v.begin(), v.end(), [](int a, int b){ return a > b};);
sort(v.begin(), v.end(), Mycompare());
}
- 内建函数对象
- STL内建了一些函数对象
- 分为算数仿函数、
算数仿函数
void test01() {
negate<int> n;
cout << n(50);
}
void test02() {
plus<int> a;
// minus、multiplies、divides、modulus(取模)
cout << a(10, 10);
}
int main() {
test01(); // 输出-50
test02(); // 输出20
}
关系仿函数
void test01() {
vector<int> a;
a.push_back(1);
a.push_back(3);
a.push_bacl(-1);
sort(a.begin(), a.end()); // 从小到大
sort(a.begin(), a.end(), greater<int>()); // 内建函数对象
}
逻辑仿函数
void test01() {
vector<bool> v;
v.push_back(false);
v.push_back(true);
for (int i = 0; i < v.size(); i ++ ) {
cout << v[i] << ' ';
}
vector<bool> temp(v.size());
transform(v.begin(), v.end(), temp.begin(), logical_not<bool>())
for (int i = 0; i < temp.size(); i ++ ) {
cout << temp[i] << ' ';
}
}
STL常见算法
遍历算法
- for_each
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
class print {
public:
void operator()(int val) {
cout << val << endl;
}
};
void print01(int val) {
cout << val << ' ';
}
void test01() {
vector<int> v;
v.push_back(1);
v.push_back(3);
// for_each(v.begin(), v.end(), print01);
for_each(v.begin(), v.end(), print());
}
int main() {
test01();
}
- transform
将一个容器的内容搬运到另一个容器
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
class Trans {
public:
int operator()(int v) {
return v + 1 ;
}
};
class print {
public:
void operator()(int val) {
cout << val << ' ';
}
};
void test01() {
vector<int> v;
v.push_back(17);
v.push_back(1);
vector<int> target;
target.resize(v.size());
transform(v.begin(), v.end(), target.begin(), Trans());
for_each(target.begin(), target.end(), print());
}
int main() {
test01();
}
查找算法
- find
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void test01() {
vector<int> v;
for (int i = 0; i < 10; i ++ ) v.push_back(i);
vector<int>::iterator it = find(v.begin(), v.end(), 5);
if (it != v.end()) cout << *it;
}
int main() {
test01();
}
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
class Person {
public:
string name;
int age;
Person(string name, int age) {
this->age = age;
this->name = name;
}
bool operator==(const Person& p) {
if (this->name == p.name && this->age == p.age) return true;
else return false;
}
};
void test01() {
Person p1 = Person("libai", 1);
Person p2 = Person("wangwei", 2);
Person p3 = Person("dufu", 3);
vector<Person> v;
v.push_back(p1);
v.push_back(p2);
v.push_back(p3);
vector<Person>::iterator it = find(v.begin(), v.end(), p2);
if (it != v.end()) cout << (*it).name << ' ' << (*it).age;
}
int main() {
test01();
}
- find_if
class greaterFive {
public:
bool operator()(int val) {
return val > 5;
}
};
void test01() {
vector<int> v;
for (int i = 0; i < 10; i ++ ) v.push_back(i);
auto it = find_if(v.begin(), v.end(), greaterFive());
if (it != v.end()) cout << *it;
}
- adjacent_find
查找相邻重复元素
返回相邻元素的第一个元素的迭代器
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void test02() {
vector<int> v;
for (int i = 0; i < 5; i ++ ) v.push_back(i);
v.push_back(4);
auto it = adjacent_find(v.begin(), v.end());
if (it != v.end()) cout << *it << ' ' << *(it ++);
}
int main() {
test02();
}
- binary_search
查找指定元素是否存在,查到了返回True,否则返回false
// 必须在有序序列中
void test01() {
vector<int> v;
for (int i = 0; i < 10; i = i + 2) v.push_back(i);
bool ans = binary_search(v.begin(), v.end(), 5);
cout << ans;
}
- count
void test01() {
vector<int> v;
for (int i = 0; i < 10; i ++ ) v.push_back(i);
int num = count(v.begin(), v.end(), 1);s
cout << num;
}
class Person {
public:
int age;
string name;
bool operator==(const Person& p) {
if (this->age == p.age) return true;
else return false;
}
Person(string name, int age) {
this->name = name;
this->age = age;
}
};
void test02() {
vector<Person> p;
Person p1("libai", 1);
Person p2("zhangsan", 1);
p.push_back(p1);
p.push_back(p2);
int num = count(p.begin(), p.end(), p2);
}
- count_if
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
class greaterFive {
public:
bool operator()(int val) {
return val > 5;
}
};
void test01() {
vector<int> v;
for (int i = 0; i < 10; i ++ ) v.push_back(i);
int num = count_if(v.begin(), v.end(), greaterFive());
cout << num;
}
void test02() {
}
int main() {
test01();
}
排序算法
- sort
sort(iterator beg, iterator end, _Pred); // _Pred是谓词
void test01() {
vector<int> v;
v.push_back(9);
v.push_back(-2);
v.push_back(7);
sort(v.begin(), v.end());
}
- random_shuffle
打乱数据,洗牌
void test01() {
vector<int> v;
for (int i = 0; i < 10; i ++ ) v.push_back(i);
random_shuffle(v.begin(), v.end());
}
- merge
两个有序容器元素合并
void test01() {
vector<int> v1 = {1, 2, 3};
vector<int> v2 = {4, 7, 9};
vector<int> v;
v.resize(v1.size() + v2.size());
merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v.begin());
}
- reverse
反转元素
拷贝和替换算法
- copy
void test01() {
vector<int> v1 = {1, 2, 3};
vector<int> v;
v.resize(v1.size());
copy(v1.begin(), v1.end(), v.begin());
}
- replace
replace(iterator beg, iterator end, old_val, new_val)
void test01() {
vector<int> v1(3, 10);
replace(v1.begin(), v1.end(), 10, 20); // 10替换为20
}
- replace_if
replace(iterator beg, iterator end, _Pred, new_val)
class greaterFive {
public:
bool operator()(int val) {
return val > 5;
}
};
void test01() {
vector<int> v;
for (int i = 0; i < 10; i ++ ) v.push_back(i);
replace_if(v.begin(), v.end(), greaterFive(), 2000);
}
- swap
互换两个容器的元素
void test01() {
vector<int> v1 = vector<int>(5, 1);
vector<int> v2 = vector<int>(6, 7);
swap(v1, v2);
for (int i = 0; i < v1.size(); i ++ ) cout << v1[i] << ' ';
cout << endl;
for (int i = 0; i < v1.size(); i ++ ) cout << v2[i] << ' ';
}
算术生成算法
- accumulate
void test01() {
vector<int> v;
for (int i = 0; i <= 100; i ++ ) v.push_back(i);
int num = accumulate(v.begin(), v.end(), 0);
cout << num;
}
- fill
向容器中填充指定元素
void test01() {
vector<int> v;
v.resize(10); // 10个0
fill(v.begin(), v.end(), 100);
}
常见集合算法
- set_intersection
// 求交集
void test01() {
vector<int> v1;
vector<int> v2;
for (int i = 0; i < 10; i ++ ) {
v1.push_back(i);
v2.push_back(i + 5);
}
vector<int> target;
target.resize(min(v1.size(), v2.size()));
auto it = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin());
// 返回的it指向交集最后元素的下一个位置
}
- set_union
// 求并集
void test01() {
vector<int> v1;
vector<int> v2;
for (int i = 0; i < 10; i ++ ) {
v1.push_back(i);
v2.push_back(i + 5);
}
vector<int> target;
target.resize(v1.size() + v2.size());
auto it = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin());
}
- set_difference
// 求差集
void test01() {
vector<int> v1;
vector<int> v2;
for (int i = 0; i < 10; i ++ ) {
v1.push_back(i);
v2.push_back(i + 5);
}
vector<int> target;
target.resize(max(v1.size(), v2.size()));
auto it = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin());
}
标签:begin,STL,void,back,C++,int,vector,push,泛型
From: https://www.cnblogs.com/-yuanyuan/p/18619962