泛型

要说泛型，就需要了解类型的本质。

类型

编程语言会有两种类型，一种是内建类型，如 int、float 和 char 等，一种是抽象类型，如 struct、class 和 function 等

对于静态类型编程语言：静态类型检查是在编译器进行语义分析时进行的。
对于动态类型编程语言：一个变量的类型是由运行时的解释器来动态标记的，这样就可以动态地和底层的计算机指令或内存布局对应，动态类型的语言必然要给出一堆诸如：is_array(), is_int(), is_string() 或是 typeof() 这样的运行时类型检查函数。

作用于不同类型的代码，虽然长得非常相似，但是由于类型的问题需要根据不同类型写出不同的算法，如果要做到泛型，就需要涉及比较底层的玩法。

👆：对不同类型有不同的操作方式;

👇：类型是内存的一种抽象，不同类型有不同内存。

泛型操作

所以要做到泛型，就需要：

抽象不同类型的初始化/销毁。（分配/释放）
抽象为一组对类型的操作。
标准化掉数据容器的操作。（比如：查找算法、过滤算法、聚合算法……）

类型是对内存的一种抽象。不同的类型，会有不同的内存布局和内存分配的策略。不同的类型，有不同的操作。所以，对于特定的类型，也有特定的一组操作。

类型抽象&数据结构抽象&业务与控制逻辑的分离

类型抽象：对于静态类型编程语言有许多不同的类型。
数据结构：是数据的聚合形式，比如基础的数组，链表，然后在此延伸出的队列，栈，散列表，堆，树和图。
- 类型相当于元素（element）,数据结构是多个元素的组织形式。
算法的抽象。
- 程序的算法（成应用逻辑）
- 应该是和数据类型甚至数据结构无关的。
- 各种特殊的数据类型（或数据结构）
- 理应做好自己的份内的工作。
- 算法只关于一个完全标准和通用的实现。
- 对于泛型的抽象，我们需要回答一个问题：
  - 如果让我的数据类型符合通用的算法，那么什么是数据类型最小的需求？

评估方式

通过让不同的编程语言来写出swap/search/sum三种函数，来评估此语言的类型抽象,数据结构抽象和控制逻辑的抽象能力

Swap(X,y)通用的与类型无关的泛型
- 类型抽象
Search(container,va)泛型函数
- 类型的抽像
- 数据结构的抽像
Sum-Employee.vacation/Emplyee.Salary
- 业务逻辑与控制逻辑的分离
- 控制逻辑的抽象和泛型

C语言

swap

 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
#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#include<assert.h>

void *t;
void swap(void* t1,void* t2,int size){
    t = (void*)malloc(size);
    assert(t != NULL);
    memcpy(t,t1,size);  
    memcpy(t1,t2,size);
    memcpy(t2,t,size);

}

int main(int argc,char *argv[]){
    int i1 =4, i2= 5;
    swap(&i1, &i2, sizeof(i1));
    printf("i1:%d, i2:%d\n",i1, i2);

    char c1='A', c2='Z';
    swap(&c1, &c2, sizeof(c1));
    printf("c1:%c, c2:%c\n",c1, c2);
    
    free(t);
    return 0;
}

执行：https://onlinegdb.com/1SPNbkCSPr

search

 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
#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#include<assert.h>

//任意类型的查找，elemsize指定单个元素的大小
int search(void* sour, void* targetElem, size_t sourLen, size_t elemsize)
{
	assert(sour != NULL);
	void* elemTemp;
	for (int i = 0; i < sourLen; i++)
	{
		elemTemp =(char*)(sour)+i*elemsize;//获取第i个元素
		if (memcmp(elemTemp, targetElem,elemsize) == 0)
			return i;
	}
	return -1;
}



//自定义比较函数
int searchByCmp(void* sour, void* targetElem, size_t sourLen, size_t elemsize, int (*cmpfun)(void*, void*))
{
	assert(sour != NULL);
	void* elemTemp;
	for (int i = 0; i < sourLen; i++)
	{
		elemTemp = (char*)sour+i*elemsize;
		if (cmpfun(elemTemp, targetElem)==0)
			return i;
	}
	return -1;
}

int cmpFunForStr(void* vp1, void* vp2)
{
	char* s1 = *((char**)vp1);//这里获取值而非地址
	char* s2 = *((char**)vp2);
	printf("s1:%s, s2:%s\n", s1, s2);
	return strcmp(s1,s2);
}


int main(int argc,char *argv[]){
    int intArray[] = {4, 5};
    int intTarget = 5;
    assert(search(intArray, &intTarget, 2, sizeof(intTarget)) == 1);

    printf("success for int\n");
    
    double doubleArray[] = {1000.0, 2.0, 3.4, 7.0, 50.0};
    double doubleTarget = 2.0;
    assert(search(doubleArray, &doubleTarget, 2, sizeof(doubleTarget)) == 1);

    printf("success for double\n");


    char* strArray[] = {"hello", "world", "2023"};
    char* strTarget = "world";
    assert(searchByCmp(strArray, &strTarget, 3, sizeof(char *), cmpFunForStr) == 1);


    printf("end\n");
    return 0;
}

https://onlinegdb.com/SGnFZeqx3

Do not use memcmp() to compare security critical data, such as cryptographic secrets, because the required CPU time depends on the number of equal bytes. Instead, a function that performs comparisons in constant time is required. Some operating systems provide such a function (e.g., NetBSD’s consttime_memequal()), but no such function is specified in POSIX. On Linux, it may be necessary to implement such a function oneself.

C语言泛型的问题

没有办法解决数据结构的抽象。
- 如果再继续进入数据结构中的泛型。如：vector,stack,map几乎很难了
- 数据容器还需要解决两个问题：
  - 数据对象的内存是如何分配和释放的？
  - 数据对象的复制是如何复制的？深拷贝还是浅拷贝？
算法越复杂，对于类型的抽象越难满足。
- 随着算法越来越复杂，接口越来越复杂。
  - 数据类型的自适应问题

C++语言

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
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
#include <iostream>
#include <vector>
#include <list>

using namespace std;

void testVector ();
void testList ();

template < class InputIterator, class T >
  T sum (InputIterator first, InputIterator last, T start)
{
  while (first != last)
    {
      start += *first++;
    }
  return start;
}


int
main ()
{
  testVector ();
  testList ();

  return 0;
}

void
testVector ()
{
  vector < int >v;
  v.push_back (1);
  v.push_back (2);
  v.push_back (3);
  v.push_back (4);

  cout << "Sum of Vector v is : " << sum (v.begin (), v.end (), 0) << endl;

}

void
testList ()
{
  //for list 
  list < double >l;		//creat a double type list
  l.push_back (10);		//pushing data into list l
  l.push_front (11);		//pushing data into list l
  l.push_back (9);		//pushing data into list l
  l.push_front (12);		//pushing data into list l
  l.push_back (8);		//pushing data into list l

  // list<double>::iterator itlist;

  cout << "Sum of List L is : " << sum (l.begin (), l.end (), 0.0) << endl;
}

https://onlinegdb.com/NqSDCn8Xk

sum

 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
#include <iostream>
#include <vector>
#include <string>

using std::cout; using std::endl;
using std::vector; using std::string;

struct Employee {
    string name;
    string id;
    int vacation;
    double salary;
};

//total salary or total vacation days?
//sum(staff.begin(),staff.end(),0);

template<class Iter,class T,class Op>
T reduce (Iter start,Iter end,T init,Op op){
    T result = init;
    while (start != end) {
        result = op(result,*start );
        start++;
    }
    return result;
}

int main(){
    vector<Employee>staff = {{"t", "121221", 1, 1.0},
        {"s", "121221", 2, 2.0}
    };

    double sum_salries = reduce(staff.begin(),staff.end(),0.0, [](double s,Employee e){return s+e.salary;});
    double max_salary = reduce(staff.begin(),staff.end(),0.0, [](double s,Employee e) {return s > e.salary?s:e.salary; } );

    cout << "Sum of sum_salries:" << sum_salries << "\n max_salary:"<< max_salary << endl;
}

https://onlinegdb.com/9cJxKV9el

c++Lambda

[capture list] (params list) mutable exception-> return type { function body }

referenece

c++迭代器

20230115164413

迭代器的种类迭代器可以被分为5种：输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机访问迭代器。下面是它们的分类依据：

输入迭代器：只能单步向前迭代元素，不允许修改由该类迭代器引用的元素。输出迭代器：只能单步向前迭代元素，对元素只有写的权力。前向迭代器：拥有输入迭代器和输出迭代器的所有特性双向迭代器：在前向迭代器的基础上提供了单步向后迭代元素的能力随机访问迭代器：拥有上面4个迭代器的所有特性，而且可以像指针那样进行算术计算，而不是仅仅只有单步向前或向后迭代。在STL中，各容器提供的迭代器种类如下：

vector，deque：随机访问迭代器 list，set，multiset，map，multimap：双向迭代器 stack，queue，priority_queue：不支持任何迭代器

各种迭代器支持的操作如下：

20230115164634

五种迭代器均支持：

p++：后置单步向前迭代
++p：前置单步向前迭代
输入迭代器：
- *p：解引用作为右值（读）
- p=p1：将一个迭代器赋给另一个迭代器
- p==p1：比较迭代器的相等性
- p!=p1：比较迭代器的不等性
输出迭代器：
- *p：解引用作为左值（写）
- p=p1：将一个迭代器赋给另一个迭代器
前向迭代器：
- 输入迭代器和输出迭代器的所有支持操作的总和
双向迭代器：
- p–：后置单步向后迭代
- –p：前置单步向后迭代
随机访问迭代器：
- p+=i/p+i：i步向前迭代
- p-=i/p-i：i步向后迭代
- p[i]：返回偏离i位元素的引用
- p<p1 & p<=p1 & p>p1 & p>=p1：比较两个迭代器的先后顺序位置

golang

sum

 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
package main

import "fmt"

type Number interface {
	int | int64 | float64 | string
}

func Sum[T Number](numbers []T) T {
	var total T
	for _, x := range numbers {
		total += x
	}
	return total
}

func main() {
	testInt()
	testStr()
}

func testInt() {
	xs := []int{3, 5, 10}
	total := Sum(xs)
	fmt.Println(total)
}

func testStr() {
	xs := []string{"3", "-", "5", "-", "10"}
	total := Sum(xs)
	fmt.Printf("%s", total)
}

https://go.dev/play/p/uwtXoqETqWT

  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
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
package main

import "fmt"

// Iterator[T] represents an iterator yielding elements of type T.
type Iterator[T any] interface {
	// Next yields a new value from the Iterator.
	Next() Option[T]
}

// ---------------------------------------

type sliceIter[T any] struct {
	slice []T
}

// Slice returns an Iterator that yields elements from a slice.
func Slice[T any](slice []T) Iterator[T] {
	return &sliceIter[T]{
		slice: slice,
	}
}

func (it *sliceIter[T]) Next() Option[T] {
	if len(it.slice) == 0 {
		return None[T]()
	}
	first := it.slice[0]
	it.slice = it.slice[1:]
	return Some[T](first)
}

// ---------------------------------------

type mapIter[T, R any] struct {
	inner Iterator[T]
	fn    func(T) R
}

// Map is an Iterator adapter that transforms each value yielded by the
// underlying iterator using fn.
func Map[T, R any](it Iterator[T], fn func(T) R) Iterator[R] {
	return &mapIter[T, R]{
		inner: it,
		fn:    fn,
	}
}

func (it *mapIter[T, R]) Next() Option[R] {
	return MapOption(it.inner.Next(), it.fn)
}

// ----------------------------------------------------------

// Options[T] represents an optional value of type T.
type Option[T any] struct{ value *T }

// MapOption applies a function fn to the contained value if it exists.
func MapOption[T any, R any](opt Option[T], fn func(T) R) Option[R] {
	if !opt.IsSome() {
		return None[R]()
	}
	return Some(fn(opt.Unwrap()))
}

// Some returns an Option containing a value.
func Some[T any](v T) Option[T] {
	return Option[T]{value: &v}
}

// None returns an empty Option.
func None[T any]() Option[T] {
	return Option[T]{value: nil}
}

// IsNone returns true if Option is empty.
func (opt Option[T]) IsNone() bool {
	return opt.value == nil
}

// IsSome returns true if Option contains a value.
func (opt Option[T]) IsSome() bool {
	return !opt.IsNone()
}

// Unwrap extracts a value from Option. Panics if Option does not contain a
// value.
func (opt Option[T]) Unwrap() T {
	if opt.IsNone() {
		panic("Attempted to unwrap an empty Option.")
	}
	return *opt.value
}

// ------------------------------------------------------

func main() {
	testSlice()
}

func testSlice() {
	it := Slice([]int{1, 2, 3})
	for v := it.Next(); !v.IsNone(); v = it.Next() {
		fmt.Println(v.Unwrap())
	}
}
func testMap() {
	it :=Map([]int{1, 2, 3})
	for v := it.Next(); !v.IsNone(); v = it.Next() {
		fmt.Println(v.Unwrap())
	}
}

https://go.dev/play/p/IM2tTB_iAeU

php

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

function add($a, $b) 
{
    return $a + $b;
}
add('1', '2');
add([], true); // ?

function add($a, $b) 
{
    if (!is_int($a) || !is_int($b)) {
        return null;
    }

    return $a + $b;
}
// 内置类型提示 
function add(int $a, int $b): int 
{
    return $a + $b;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Collection extends ArrayObject
{
    public function offsetGet(mixed $key): mixed 
    { /* … */ }

    public function filter(Closure $fn): self 
    { /* … */ }

    public function map(Closure $fn): self 
    { /* … */ }
}

class StringCollection extends Collection
{
    public function offsetGet(mixed $key): string 
    { /* … */ }
}

class UserCollection extends Collection
{
    public function offsetGet(mixed $key): User 
    { /* … */ }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Collection<Type> extends ArrayObject
{
    public function offsetGet(mixed $key): Type 
    { /* … */ }

    // …
}

$users = new Collection<User>();
$slugs = new Collection<string>();

php generic discuss

编程范式-泛型编程

文章目录

泛型

类型