泛型
泛型
为什么C++泛型支持int等基本类型而Java泛型不支持呢？
泛型在Java中是一个非常重要的语法，比如我们经常用的容器都支持泛型。Java泛型不支持int等基本类型，所以，在Java容器中不能存储基本类型数据，比如List<int>这样是不合法的。而C++泛型支持int等基本类型，所以，在C++容器中可以存储基本类型数据，比如vector<int>这样是合法的。那么，为什么C++泛型支持int等基本类型而Java泛型不支持呢？带着这个问题，我们来学习本节的内容。
一、为什么使用泛型
假设我们要实现一个栈Stack，并且希望这个栈可以支持不同类型数据的存储，比如Integer、User等。如果不使用泛型，我们有两种实现方式。
1）第一种实现方式
我们为存储不同类型的数据定义不同的Stack类，示例如下所示，我们定义了存储Integer类型数据的IntegerStack和存储Long类型数据的LongStack。支持多少种类型数据的存储，我们就需要定义多少个Stack类。这种实现方式的弊端显而易见，需要实现很多功能相似的类，并且编写大量的重复代码。
// 存储Integer类型数据的Stack类
public class IntegerStack {
private Integer[] arr;
private int top;
private int size;
public IntegerStack(int size) {
this.arr = new Integer[size];
this.size = size;
this.top = 0;
}
public void push(Integer elem) {
if (top == size) return;
arr[top++] = elem;
}
public Integer pop() {
if (top == 0) return null;
return arr[--top];
}
}
// 存储Long类型数据的Stack类
public class LongStack {
private Long[] arr;
private int top;
private int size;
public LongStack(int size) {
this.arr = new Long[size];
this.size = size;
this.top = 0;
}
public void push(Long elem) {
if (top == size) return;
arr[top++] = elem;
}
public Long pop() {
if (top == 0) return null;
return arr[--top];
}
}
2）第二种实现方式
我们为所有可能存储的类型，抽象出统一的接口或者父类。这样，我们只需要针对接口或父类实现一个通用的Stack类，所有的子类数据都可以存储到这个通用的Stack类。比如，如果栈中存储的是Integer、Long、Float、Double等数字类型的数据，这些数字类型的父类是Number，那么我们只需要设计一个存储Number类型数据的Stack类。示例代码如下所示。
// 支持Number的子类类型数据存储
public class NumericStack {
private Number[] arr;
private int top;
private int size;
public NumericStack(int size) {
this.arr = new Number[size];
this.size = size;
this.top = 0;
}
public void push(Number elem) {
if (top == size) return;
arr[top++] = elem;
}
public Number pop() {
if (top == 0) return null;
return arr[--top];
}
}
当然，如果栈中存储的数据的类型不确定，这种情况下，我们可以使用Object作为公共的父类来定义Stack栈。示例代码如下所示。
// 支持任意类型数据存储
public class Stack {
private Object[] arr;
private int top;
private int size;
public Stack(int size) {
this.arr = new Object[size];
this.size = size;
this.top = 0;
}
public void push(Object elem) {
if (top == size) return;
arr[top++] = elem;
}
public Object pop() {
if (top == 0) return null;
return arr[--top];
}
}
上述实现方式看起来很完美，但在使用时却存在一定的问题，示例代码如下所示。下列代码编译不会报错，但在运行时会抛出ClassCastException异常。
Stack stack = new Stack(10);
stack.push(12);
stack.push("34"); //编译时未作类型检查
Integer elem = (Integer) stack.pop(); //运行时报错
我们本希望在栈中存储整型数据，但在代码编写的过程中，因为疏忽，将字符串存储到了栈中。因为Stack支持Object类型的数据存储，所以，存储字符串到栈中并不会引起编译或者运行时报错，换句话说，编译器没有帮我们做类型检查。
父类类型向子类类型转换，需要显式的强制类型转换。当我们使用pop()函数将数据从栈中取出时，因为函数的返回值为Object类型，我们需要将其转化成Integer类型再使用。而执行pop()函数返回的是String类型的数据，强制类型转换为Integer类型失败，于是，就抛出了ClassCastException运行时异常。
总结一下，以上两种实现方式各有利弊，都不完美。使用第一种实现方式，需要定义大量相似的类，编写大量的重复代码。而使用第二中实现方式，无法享受到编译器在编译时的类型检查服务，并且，代码中充斥着显式的强制类型转换，也不美观。
于是，为了解决以上问题，JDK5引入了泛型语法。泛型继承了上述两种实现方式的优点，又摒弃了两种实现方式的缺点。使用泛型，我们既可以消除重复代码，又可以利用编译器的类型检查，保证类型的安全性。
我们使用泛型实现了一个支持各种类型数据存储的栈，代码如下所示。
public class Stack<E> {
private Object[] arr; //这里不是T[] arr; 原因稍后解释
private int top;
private int size;
public Stack(int size) {
this.arr = new Object[size];
this.size = size;
this.top = 0;
}
public void push(E elem) {
if (top == size) return;
arr[top++] = elem;
}
public E pop() {
if (top == 0) return null;
return (E) arr[--top];
}
}
当使用上述Stack泛型类（Stack<T>）时，我们需要指定类型，将其转化为具体类（比如Stack<Integer>）。如果往栈中存储不同类型的数据，编译器会在编译时提示类型错误。除此之外，在代码中，我们也不需要使用强制类型转换。示例代码如下所示。
Stack<Integer> stack = new Stack<>(10); //指定类型
stack.push(12);
// stack.push("34"); //去掉注释之后会报编译错误
Integer elem = stack.pop(); //不需要类型转换
根据上面的讲解，我们发现，泛型本质上就是对类型的参数化，在类的定义中，我们可以把类型当做参数，当使用类时，我们向类型参数传入具体类型。
二、泛型的基本用法
刚刚我们介绍了泛型的由来，接下来，我们详细讲解一下泛型的用法。泛型一般有三种使用方式：泛型接口、泛型类、泛型方法，示例代码如下所示。
// 泛型接口
public interface List<E> {
void add(E element);
E get(int index);
...
}
// 泛型类
public class ArrayList<E> implements List<E> {
private Object[] arr; //这里不是T[] arr; 原因稍后解释
...
public void add(E element) { ... }
public E get(int index) { ... }
}
// 泛型方法
public class Collections {
public static <T> int binarySearch(List<T> list, T key);
...
}
以上代码中，尖括号内的E、T等表示类型参数，实际上，它们也可以替换为任意大写字母。不过，我们一般习惯性使用E、T、K、V、N这几个大写字母来表示类型参数。
1）E是element的首字母，一般用来表示容器中的元素的类型参数。
2）T是type的首字母，一般用来表示非容器元素的数据类型参数。
3）K、V分别是key和value的首字母，一般用来表示键值对中键和值的类型参数。
4）N是number的首字母，一般用来表示数字类型参数。
当然，一个泛型接口、泛型类、泛型方法中也可以支持多个类型参数，如下所示。
public interface Map<K,V> {
void put(K key, V value);
V get(K key);
...
}
对于泛型，除了以上基本用法之外，我们还可以使用extends上界限定符，限定类型参数的具体取值范围。例如，<T extends Person>表示限定传入类型参数的具体类型必须是Person或者Person的子类。需要注意的是，泛型中只有extends，没有implements。这里的extends既可以表示类型继承，也可以表示接口实现。例如，<T extends Closable>表示限定传入类型参数的具体类型必须实现了Closable接口。
对于extends上界限定符的用法，我们举例解释一下。
假设我们希望设计一个泛型方法，用来比较两个对象的大小。这个方法只支持实现了Comparable接口的对象进行大小比较。为了实现这个需求，如下代码所示，我们可以使用extends关键字，限制a、b的类型必须实现Comparable接口。
// Utils类中定义了一个泛型方法
public class Utils {
public <T extends Comparable<T>> T max(T a, T b) {
if (a.compareTo(b) <= 0) return a;
else return b;
}
}
// 具体使用方法
Student s1 = new Student(2, 13); //Student类实现了Comparable接口
Student s2 = new Student(4, 22);
Student maxStu = Utils.max(s1, s2); //不需要强制类型转换
// Comparable接口的定义（泛型接口）
public interface Comparable<T> {
int compareTo(T o);
}
// Student
public class Student implements Comparable<Student> {
public int id;
public int age;
public Student(int id, int age) {
this.id = id;
this.age = age;
}
@Override
public int compareTo(Student o) {
return this.age - o.age;
}
}
三、泛型中的通配符
除了类型参数之外，泛型中还有另外一个常用语法：？通配符。
通配符跟类型参数的应用场景并不相同。类型参数一般用来定义泛型类、泛型接口和泛型方法，而通配符跟Integer、Person、String这些具体类型无异，用来具体化泛型类或泛型接口，可以看做一种特殊的具体类型。当我们在具体化某个泛型类或泛型接口，但又无法指明明确的具体类型时，我们就可以使用通配符这种特殊的具体类型。
通配符常用于方法参数中，当方法中的某个参数为泛型类或接口时，如果我们无法指定具体的类型，那么就可以使用通配符来表示可以匹配任意类型。示例代码如下所示。reverse()方法中的list对应的类是一个泛型类，在使用时，需要传入具体类型，但是，这里我们并不知道具体的类型是什么，所以，我们就用通配符来替代具体类型。
public class Colletions {
public static void reverse(List<?> list) { ... }
}
当然，在reverse()函数中，我们也可以使用类型参数替代通配符，如下所示，只不过，此时的reverse()函数便是一个泛型方法。在泛型方法中，方法的前面需要添加<T>类型参数声明，而使用通配符定义的reverse()函数中，并没有类型参数声明。这是两者的主要区别。
public class Colletions {
public static <T> void reverse(List<T> list) { ... }
}
关于通配符，我们再来看另一个稍微复杂点的例子。下面的代码是否可以成功执行呢？
public class Demo {
public static class Member {}
public static class Student extends Member {}
public static void test(List<Member> members) { }
public static void main(String[] args) {
List<Student> students = new ArrayList<Student>();
test(students);
}
}
上述代码编译失败，编译器提示test(students);这一语句类型不匹配。尽管Student是Member的子类，但是，List<Student>跟List<Member>并没有任何继承关系，所以，将List<Student>类型的数据传递给List<Member>会报错。对于这个问题，我们只需要使用通配符配合extends上界限定符即可解决。
public class Demo {
public static class Member {}
public static class Student extends Member {}
public static void test(List<? extends Member> members) { }
public static void main(String[] args) {
List<Student> students = new ArrayList<Student>();
test(students);
}
}
当然，我们也可以使用类型参数替代通配符来解决。代码如下所示。不过，从类型参数与通配符的应用场景来看，我们更倾向于使用通配符来实现test()方法。
public class Demo {
public static class Member {}
public static class Student extends Member {}
public static <T extends Member> void test(List<T> members) { }
public static void main(String[] args) {
List<Student> students = new ArrayList<Student>();
test(students);
}
}
如果说上面列举的一些场景，类型参数完全可以替代通配符，使用类型参数和使用通配符没有明显区别，都可以，那么，以下两种情况下，我们就只能使用通配符，而不能使用类型参数。
1）<? super Person>
前面我们只讲到了extends上界限定符，实际上，对应地还有super下界限定符。extends上界限定符既可以用于类型参数（如<T extends Student>），也可以用于通配符（如<? extends Student>）。而super下界限定符只能用于通配符，比如<? super Student>，表示传入通配符的具体类型为Student或者Student的父类。
public void add(List<? super Student> list, Student stu) { ... }
2）<? extends T>或<? super T>
通配符可以extends或super类型参数，但类型参数不可以extends或super类型参数。示例代码如下所示。
// 合法
public <T> void copy(List<? super T> dest, List<? extends T> src) { ... }
// 报错
public <T, U, S> void copy(List<U super T> dest, List<S extends T> src) { ... }
四、泛型的类型擦除
刚刚我们讲了泛型的用法，现在，我们来看下泛型的底层实现原理。
实际上，泛型只不过是一个语法糖。在编译时，编译器会使用泛型做类型检查，但是，当代码编译为字节码之后，泛型中的类型参数和通配符统统替换成上界，比如<T>替换为Object，<T extends String>替换为String，示例如下所示。Java这种独特的泛型实现方式叫做类型擦除。
public class Box<T> {
private T var;
public Box(T var) { this.var = var; }
public T get() { return var; }
}
上述代码对应的字节码如下所示。在字节码中，成员变量、参数、返回值都是Object类型的。
public class Box<T extends java.lang.Object> extends java.lang.Object
{
public Box(T);
descriptor: (Ljava/lang/Object;)V
flags: (0x0001) ACC_PUBLIC
Code:
stack=2, locals=2, args_size=2
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: aload_0
5: aload_1
6: putfield #2 // Field var:Ljava/lang/Object;
9: return
LineNumberTable:
line 3: 0
line 4: 4
line 5: 9
Signature: #13 // (TT;)V
public T get();
descriptor: ()Ljava/lang/Object;
flags: (0x0001) ACC_PUBLIC
Code:
stack=1, locals=1, args_size=1
0: aload_0
1: getfield #2 // Field var:Ljava/lang/Object;
4: areturn
LineNumberTable:
line 6: 0
Signature: #16 // ()TT;
}
Signature: #17 // <T:Ljava/lang/Object;>Ljava/lang/Object;
因为Java泛型的类型擦除，我们不能使用new T()来创建类型参数对象。在代码编译成字节之后，类型信息已经擦除，所以，在运行时，JVM无法确定具体类型，也就无法知道T是否存在无参构造函数，所以，也就无法使用new来创建T对象了。这也是为什么在本节的第一小节中实现的Stack泛型类中使用Object来定义arr数组的原因。
除此之外，Java泛型这种独特的实现方式，也导致了只有引用类型才可以传入类型参数，而基本类型并不继承自Object，无法做类型擦除，因此无法传入类型参数。也就是说，Java泛型并不支持基本类型。如下所示的代码会报错。
List<int> list = new ArrayList<>(); //编译出错
list.add(123);
当然，Java也可以提供跟进一步的语法糖，当程序员如上代码所示声明List<int>时，编译器将int替换为对应的包装类Integer，也就是将List<int>替换为List<Integer>，这样就可以在表面上实现支持基本类型参数了，但在List容器中存储的并非int类型数据，所以，从本质上讲，这样做并没有真正支持基本类型。而如果要从本质上让Java泛型支持基本类型，需要从底层上改变Java泛型的实现方式，那么，牵扯到的需要改动的JDK代码就非常多了，对应的开发量就非常大了。
Java泛型无法实现基本类型，也带来了一些开发上的困难，比如在12节中讲到的用于排序的DualPivotQuickSort类，为了支持不同的基本类型，分别定义了不同的排序函数，而每个函数都要重复实现一遍类似的排序逻辑，代码实现非常不美观。
//DualPivotQuickSort类中sort()函数定义
public static void sort(int[] a, int left, int right,
int[] work, int workBase, int workLen);
public static void sort(long[] a, int left, int right,
long[] work, int workBase, int workLen);
public static void sort(float[] a, int left, int right,
float[] work, int workBase, int workLen);
public static void sort(double[] a, int left, int right,
double[] work, int workBase, int workLen);
public static void sort(short[] a, int left, int right,
short[] work, int workBase, int workLen);
public static void sort(char[] a, int left, int right,
char[] work, int workBase, int workLen);
如果Java泛型支持基本类型，那么，我们只需要如下所示，定义一个泛型方法即可。我觉得，在后续版本中，Java很有可能会优化泛型，让其支持基本类型。
public static <T> void sort(T[] a, int left, int right,
T[] work, int workBase, int workLen);
熟悉C++语言的同学应该知道，C++语言也支持泛型，只不过它有另一个叫法，叫做模板（Templates）。跟Java泛型不同的是，C++泛型支持基本类型，如下所示，我们可以定义int类型的vector容器。那么，C++泛型为什么能支持基本类型呢？
vector<int> nums;
之所以C++泛型支持基本类型，是因为其底层实现方式跟Java泛型完全不同。C++中的泛型有点类似宏定义，当某个cpp文件用到泛型类时，编译器会讲泛型类中的类型参数，替换为具体类型，也就是将泛型类转换为具体类，然后内联到这个cpp文件中。如果有多个cpp文件使用同一个泛型类，那么就要生成多个具体类。可想而知，这种实现方式并不高效。对于一个泛型类，JVM中只需要保存一个类型擦除之后的类即可，但是C++需要生成多个不同的具体类。
五、课后思考题
把接口或类中的所有方法都设置为泛型方法，是不是就等价于泛型接口或泛型类了呢？