slacr_

Just to record my life and thoughts.
笔记/编程/杂乱/极简

126Archives20Categories

[C++笔记]群体类和群体数据的组织二

May 1, 2023C_C++3670 words in 24 min

C++笔记

模板实现几个常见的排序/查找算法
每个算法都有很多种实现方式, 懂得其内在思想才是最重要的.

排序

插入排序

插入排序的基本思想是: 每一步将一个待排序元素按其关键字值的大小插入到己排序序列的适当位置上，直到待排序元素插入完为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class T>
void insertionSort(T arr[], int len) {
	int i, j;
	T temp;

	for (int i = 1; i < len; i++) {  // 从第2个数开始, 依次往后扫描, 插入后面 len - 1 个数
		int j = i;					// 每次要插的数的位置
		T temp = arr[i];
		while (j > 0 && temp < arr[j - 1]) {	// 前i个数位置正确, 从后往前找到正确位置
			arr[j] = arr[j - 1];				// 后移一位
			j--;
		}
		// 退出循环, 插入位置已找到
		arr[j] = temp;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 另一种
#include<iostream>
using namespace std;

template<class T>
void printArr(T* arr, int len) {
	for (int i = 0; i < len; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}

template<class T>
void insertSort(T* arr, int len) {
	// 模板插入排序
	for (int i = 1; i < len; i++)
	{
		for (int j = i; arr[j] < arr[j-1] && j > 0; j--) {
			T temp = arr[j];
			arr[j] = arr[j - 1];
			arr[j - 1] = temp;
		}
		printArr(arr, len);
	}
}

int main() {
	int data[] = {1,3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18,20};
	int len = sizeof data / sizeof data[0];
	insertSort<int>(data, len);
	return 0;
}

选择排序

选择排序的基本思想是:每次从待排序序列中选择一个关键字最小的元素(当需要按关键字升序排列时) ，顺序排在已排序序列的最后，直至全部排完。在选择类排序方法中，根据从待排序序列中选择元素的方法不同，又分为不同的选择排序方法。其中最简单的是通过顺序比较找出待排序序列中的最小元素，称为直接选择排序.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<class T>
void swap(T& x, T& y) {
	T temp = x;
	x = y;
	y = temp;
}

template<class T>
void selectionSort(T arr[], int len) {
	for (int i = 0; i < len - 1; i++) {		// 选择len-1次
		int min_idx = i;			// 初始最小假设idx 为 i
		for (int j = i + 1; j < len; j++) {		// 从 i +1 开始往后依次比较
			if (arr[j] < arr[min_idx]) {
				min_idx = j;
			}
		}
		// 得到min_idx
		if (min_idx == i) continue;		// 位置正确, 无需交换	
		swap<T>(arr[i], arr[min_idx]);		// 交换
	}
}

交换排序

交换排序的基本思想是: 两两比较待排序序列中的元素，并交换不满足顺序要求的各对元素，直到全部满足顺序要求为止。最简单的交换排序方法是冒泡排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<class T>
void swap(T& a, T& b) {
	T temp = a;
	a = b;
	b = temp;
}

template<class T>
void bubbleSort(T arr[], int len) {
	for (int i = 0; i < len - 1; i++) {				// n-1趟
		for (int j = 0; j < len - 1 - i; j++) {		// 每趟使最大的一项交换到最后
			if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
		}
	}
}

查找

顺序查找

1
2
3
4
5
6
7
template<class T>
int sequentialSearch(const T arr[], int len, const T& key) {
	for (int i = 0; i < n; i++) {
		if (arr[i] == key) return i;
	}
	return -1;
}

折半/二分查找

如果是在一个元素排列有序的数组中进行查找，可以采用折半查找方法。折半查找方法的基本思想是:对于已接关键字排序的序列，经过一次比较后，可将序列分割成两部分，然后只在有可能包含待查元素的一部分中继续查找，并根据试探结果继续分割，逐步缩小查找范围，直至找到或找不到为止。

本质是减制, 还可以递归实现

1
2
3
4
5
6
7
8
9
10
11
12
template <class T>
int binarySearch(const T arr[], const int len, const T& key)  {
	int low = 0;
	int high = len - 1;
	while (low <= high) {
		int mid = (low + high) / 2;		// 中间元素下标
		if (key == arr[mid]) return mid;		// 查找到
		else if (key < arr[mid]) high = mid - 1;  // 在左半边, 重新置high
		else low = mid + 1;						  // 在右半边, 重新置low
	}
	return -1;				// 没有查找到 返回-1
}

模板的实例化

类模板本身不是类, 函数模板也不是函数, 只有实例化之后才能当类/函数使用.

模板的实例化是按需进行的，用到哪个类型就生成针对哪个类型的函数或类，不会提前生成过多的代码。也就是说，编译器会根据传递给类型参数的实参（也可以是编译器自己推演出来的实参）来生成一个特定版本的函数或类，并且相同的类型只生成一次。实例化的过程也很简单，就是将所有的类型参数用实参代替。

另外需要注意的是类模板的实例化，通过类模板创建对象时并不会实例化所有的成员函数，只有等到真正调用它们时才会被实例化；如果一个成员函数永远不会被调用，那它就永远不会被实例化。这说明类的实例化是延迟的、局部的，编译器并不着急生成所有的代码。

通过类模板创建对象时，一般只需要实例化成员变量和构造函数。成员变量被实例化后就能够知道对象的大小了（占用的字节数），构造函数被实例化后就能够知道如何初始化了；对象的创建过程就是分配一块大小已知的内存，并对这块内存进行初始化。

通常模板的实例化是在调用函数或者创建对象时由编译器自动完成的，不需要程序员引导，因此称为隐式实例化。相对应的，我们也可以通过代码明确地告诉编译器需要针对哪个类型进行实例化，这称为显式实例化。

编译器在实例化的过程中需要知道模板的所有细节：对于函数模板，也就是函数定义；对于类模板，需要同时知道类声明和类定义。我们必须将显式实例化的代码放在包含了模板定义的源文件中，而不是仅仅包含了模板声明的头文件中。这样一来，就可以把模板的声明和定义放在不同文件里面了。

显式实例化实现模板分文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// ================= templ.h
#pragma once
template<class T> void swap(T& a, T& b);		// 函数模板声明
template<class T> class TestClass {             // 类模板声明
public:
	void showType();
};												

// ================= templ.cpp
#include <iostream>
#include "templ.h"
template<class T> void swap(T& a, T& b)  //函数模板实现
{
	T temp = a;
	a = b;
	b = temp;
};
template void swap<int>(int& a, int& b);	// 函数模板显示实例化, 会在生成当前源文件的该类型函数目标代码
											// <int>可以不写, 编译器自动类型识别
template<class T>                           // 类模板的实现
void TestClass<T>::showType() {
	std::cout << typeid(T).name() << std::endl;
};

template class TestClass<int> ;		// 类模板显示实例化


// ================= main.cpp
#include <iostream>
#include "templ.h"

int main() {
	int a = 1, b = 2;
	swap(a, b);
	std::cout << a << " " << std::endl;
	TestClass<int> t;
	t.showType();
	// TestClass<float> f;	// 这句能过编译, 编译器生成的构造函数
	// f.showType();	    // 错误没有实例化的函数成员, 源文件只显示实例化了 TestClass<int> 型
	return 0;
}

模板的特化

模板是一种泛型技术，它能接受的类型是宽泛的、没有限制的，并且对这些类型使用的算法都是一样的（函数体或类体一样）。让模板能够针对某种具体的类型使用不同的算法（函数体或类体不同），这在 C++ 中是可以做到的，这种技术称为模板的显式具体化（Explicit Specialization）。

通常模板的实例化是在调用函数或者创建对象时由编译器自动完成的，不需要程序员引导，因此称为隐式实例化。相对应的，我们也可以通过代码明确地告诉编译器需要针对哪个类型进行实例化，这称为显式实例化。

在 C++ 中，对于给定的函数名，可以有非模板函数、模板函数、显示具体化模板函数以及它们的重载版本，在调用函数时，显示具体化优先于常规模板，而非模板函数优先于显示具体化和常规模板。

模板类调用优先级从高到低进行排序是：全特化类 > 偏特化类 > 主版本模板类

函数显示具体化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <string>
using namespace std;
typedef struct {
    string name;
    float score;
} STU;

template<typename T> const T& Max(const T& a, const T& b) {
    return a > b ? a : b;
}

template<> const STU& Max<STU>(const STU& a, const STU& b) {
    return a.score > b.score ? a : b;
    // 显示实例化， <STU>可省略， 由编译器自动推导.
}

ostream& operator << (ostream& out, const STU& stu) {
    out << stu.name << ' ' << stu.score;
    return out;
}

int main(int argc, char const* argv[]) {
    int a = 10, b = 20;
    cout << Max(a, b) << endl;

    STU stu1 = { "Sam", 90 }, stu2 = { "Amy", 100 };
    cout << Max(stu1, stu2);
    // 同名函数会按优先级调用普通函数 显示具体化的模板函数, 普通模板函数
    return 0;
}

类的显式具体化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
using namespace std;


//====================================================
template<class T1, class T2> class Point {
public:
    Point(T1 x, T2 y) : m_x(x), m_y(y) { }
public:
    T1 getX() const { return m_x; }
    void setX(T1 x) { m_x = x; }
    T2 getY() const { return m_y; }
    void setY(T2 y) { m_y = y; }
    void display() const;
private:
    T1 m_x;
    T2 m_y;
};

template<class T1, class T2>
void Point<T1, T2>::display() const {
    cout << "x=" << m_x << ", y=" << m_y << endl;
}


//=====================================================
// 全特化类模板具体化, 必须有一个主模板类, 参数全部明确
//====================================================


template<> class Point<const char*, const char*> {
public:
    Point(const char* x, const char* y) : m_x(x), m_y(y) { }
public:
    const char* getX() const { return m_x; }
    void setX(const char* x) { m_x = x; }
    const char* getY() const { return m_y; }
    void setY(const char* y) { m_y = y; }
    void display() const;
private:
    const char* m_x;
    const char* m_y;
};

void Point<const char*, const char*>::display() const {
    cout << "x=" << m_x << " 全特化 y=" << m_y << endl;
}

//=====================================================
// 偏特化类模板具体化, 具体化部分模板参数, 参数全部明确则为全特化
// 调用优先级从高到低进行排序是：全特化类 > 偏特化类 > 主版本模板类
//====================================================

template<typename T2>
class Point<const char*, T2> {

public:
    Point(const char* x, T2 y) : m_x(x), m_y(y) { }
public:
    const char* getX() const { return m_x; }
    void setX(const char* x) { m_x = x; }
    T2 getY() const { return m_y; }
    void setY(T2 y) { m_y = y; }
    void display() const;
private:
    const char* m_x;
    T2 m_y;
};

template<typename T2>
void Point<const char*, T2>::display() const {
    cout << "x=" << m_x << " 偏特化 y=" << m_y << endl;
}


int main() {
    (new Point<int, int>(10, 20))->display();
    (new Point<const char*, int>("E180",  10))->display();
    (new Point<const char*, const char*>("E180", "N210"))->display();
    return 0;
}

函数模板的重载

c++ 不允许将函数模板偏特化，但函数模板像普通函数那样允许被重载，通过将函数模板重载也可以完成与类模板偏特化类似的功能。

注意特化是模板的参数明确, 而不是函数参数表中的参数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;

template<class T1, class T2> void test() {
	cout << "模板函数" << endl;
}

template<> void test<double, double>() {
	cout << "函数全特化" << endl;
}

//template<class T1> void test<T1, double>() {  // 函数没有偏特化
//	cout << "函数偏特化" << endl;
//}

int main() {
	test<double, double>();			// 函数全特化
	test<int, double>();			// 模板函数
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
using namespace std;

template<class T> T& findMax(T& t1, T& t2) {
	return (t1 > t2 ? t1 : t2);
}

// 模板函数重载
template<class T> T& findMax(T* t1, T* t2) {		
	return (*t1 > *t2 ? *t1 : *t2);
}

template<class T> T& findMax(T arr[], int len) {
	T& Max = arr[0];
	for (int i = 1; i < len; i++) {
		Max = findMax(Max, arr[i]);
	}
	return Max;
}

int main() {
	int a = 1, b = 2;
	cout << findMax(a, b) << endl;			// 2
	cout << findMax(&a, &b) << endl;		// 2
	int arr[] = { 1, 2 ,3, 4, 8 };
	int len = sizeof arr / sizeof arr[0];
	cout << findMax(arr, len) << endl;		// 8
	return 0;
}

具体化和实例化的区别：

具体化：即显式具体化，与实例化不同的是，它也是一个模板定义，但它是对特定类型的模板定义。

实例化：在程序中的函数模板本身并不会生成函数定义，它只是一个用于生成函数定义的方案。编译器使用模板为特定类型生成函数定义时，得到的是模板实例。这即是函数模板的实例化。
程序运行时完成了实例化的工作，而具体化是由程序员完成的。

模板元编程

模板元编程是指在模板实例化的同时利用编译器完成一些计算任务。通过模板元编程，可以把一些需要在运行时计算的任务放到编译时来做，从而提高程序的运行时效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
using namespace std;

// 计算阶乘
template<unsigned int N>
struct Factorial {				// 也可以声明成模板类
	enum { VALUE = N * Factorial<N-1>::VALUE};
};

template<> struct Factorial<0> {	// 特化给出终止条件
	enum { VALUE = 1 };				
};

// 计算乘方
template<unsigned int N>
struct Power {
	template<class T>
	static T value(T x) {
		return x * Power<N - 1> ::value(x);
	}
};

template<>
struct  Power<1> {			// 特化递归终止条件
	template<class T>
	static T value(T x) {
		return x;
	}
};

// 简化写法, 辅助函数
template<unsigned int N, class T>
inline T power(T v) {
	return Power<N>::value(v);
}


int main() {
	const int M = 6;
	int arr[Factorial<M>::VALUE];		// 编译时自动计算阶乘, 而不是运行时
	cout << sizeof arr / sizeof arr[0] << endl; // 720

	cout << Power<3>::value<int>(2) << endl;  // 2^3 类模板嵌套函数模板
	cout << Power<3>().value(1.5) << endl;	  // 3.375

	cout << power<10, int>(2) << endl;	// 2^10

	return 0;
}

参考

  1. 《C++语言程序设计（第4版）》 IBSN 9787302227984
  2. C++参考手册
  3. Microsoft C++文档
  4. Chapter16：模板（二）——显式具体化和显式实例化
  • Author:

    slacr_

  • Copyright:

  • Published:

    May 1, 2023

  • Updated:

    May 1, 2023

Buy me a cup of coffee ☕.

支
read 1000000
1 排序
1.1 插入排序
1.2 选择排序
1.3 交换排序
2 查找
2.1 顺序查找
2.2 折半/二分查找
3 模板的实例化
3.1 显式实例化实现模板分文件
4 模板的特化
4.1 函数显示具体化
4.2 类的显式具体化
4.3 函数模板的重载
4.4 具体化和实例化的区别：
5 模板元编程