什么是范型算法？

Question

什么是范型算法？

Answer 1

C++程序员对范型编程肯定不陌生，尤其在STL大行其道的时候，C#2.0也将实现范型编程的功能。Java也不甘示弱，也推出了范型编程的语言新特性。

1．一个简单的范型示例

在以前，你可能遇到过这样的代码：

List list = new LinkedList();

list.add(“麻省理工”);

list.add(“普林斯顿”);

list.add(“伯克利”);

java/lang/String.java.html" target="_blank">String name = (java/lang/String.java.html" target="_blank">String)list.iterator.next();

注意，第三行需要强制转换。而使用范型：

List<java/lang/String.java.html" target="_blank">String> list = new LinkedList<java/lang/String.java.html" target="_blank">String>();

list.add(“麻省理工”);

list.add(“普林斯顿”);

list.add(“伯克利”);

java/lang/String.java.html" target="_blank">String name = list.iterator.next();

这里将list声明成String类型的List。List是有一个类型参数的范型接口。这个例子中类型参数是String。

2．定义简单的范型

看j2se5.0中List和Iterator接口的实现（片断）：

public interface List<E>

{

void add(E x);

Iterator<E> iterator();

}

public interface Iterator<E>

{

E next();

boolean hasNext();

}

上面的代码我们比较熟悉，但是其中增加了尖括号。尖括号中的内容定义了接口List和Iterator的形式类型参数。类型参数可以用在范型声明中，如类和接口的声明。

一旦声明了范型，你就可以使用它。在上面的例子中使用了List<String>。这里使用String是实参，代替了形参E。如果使用List<Integer>，则用实参Integer代替了形参E。

不管List<Integer>还是List<String>，它们的类只有一个。考虑下面的代码：

List<java/lang/String.java.html" target="_blank">String> list1 = new LinkedList<java/lang/String.java.html" target="_blank">String>();

List<java/lang/Integer.java.html" target="_blank">Integer> list2 = new LinkedList<java/lang/Integer.java.html" target="_blank">Integer>();

java/lang/System.java.html" target="_blank">System.out.println(list1.getClass()==list2.getClass());

输出结果为true。

一般来说，形式类型参数都是大写，尽量使用单个字母，许多容器类都使用E作为参数。

3．范型和继承

考虑下面的代码，你认为它会出错吗？

java/lang/String.java.html" target="_blank">String s ＝ “smallnest@163.com”;

java/lang/Object.java.html" target="_blank">Object o = s:

当然，String类继承Object类，这样做不会出错。但下面的代码呢？

List<java/lang/String.java.html" target="_blank">String> s = new LinkedList<java/lang/String.java.html" target="_blank">String>();

List<java/lang/Object.java.html" target="_blank">Object>o=s;

编译出错！

是的，List<Object>和List<String>没有继承关系。

4．通配符

考虑下面一个方法：

public void printCollection(Collection<java/lang/Object.java.html" target="_blank">Object> c)

{

for(java/lang/Object.java.html" target="_blank">Object o:c)

{

java/lang/System.java.html" target="_blank">System.out.printf(“%s%n”,o);

}

}

事实上，上面这个方法并不通用，它只能打印Collection<Object>类型的集合，象其他的如Collection<String>、Collection<Integer>并不能被打印，因为对象类型不一致。

为了解决这个问题，可以使用通配符：

public void printCollection(Collection<？> c)

{

for(java/lang/Object.java.html" target="_blank">Object o:c)

{

java/lang/System.java.html" target="_blank">System.out.printf(“%s%n”,o);

}

}

Collection<？>被称作未知类型的集合。问号代表各种类型。

上面的读取集合中的数据时，我们采用Object类型。这样做时可以的，因为不管未知类型最终代表何种类型，它的数据都继承Object类，那么再考虑一下下面的代码:

Collection<?> c = new ArrayList<java/lang/String.java.html" target="_blank">String>();

c.add(new java/lang/Object.java.html" target="_blank">Object()); //!!!!

这样做时错误的，因为我们不知道?代表何种类型，所以我们不能直接将Object增加到集合中，这会出现类型不匹配的情况。

5．有限制的通配符

考虑下面的代码

class Man

{

public java/lang/String.java.html" target="_blank">String name = “”;

}

class GoodMan extends Man

{

public java/lang/String.java.html" target="_blank">String name = “”

}

class BadMan extends Man

{

public java/lang/String.java.html" target="_blank">String name = “”

}

考虑下面的范型方法：

public void printName(List<Man> men)

{

for(Man man:men)

{

java/lang/System.java.html" target="_blank">System.out.println(“姓名:” + man.name);

}

}

这个范型方法只能显示List<Man>类型的数据,下面的代码允许显示Man和它的子类。

public void printName(List<？ extends Man> men)

{

for(Man man:men)

{

java/lang/System.java.html" target="_blank">System.out.println(“姓名:” + man.name);

}

}

这里使用? extends Man代替Man，表明接受任何Man的子类做为参数。

和前面的代码类似，下面的代码也是不正确的：

public void adman(List<? extends Man> men)

{

GoodMan good = new GoodMan();

good.name = “晁岳攀”;

men.add(good);

}

原因也很简单，因为?代表一切继承Man的类，你并不能保证就一定时GoodMan类。

和这种用法类似：

public void adman(List<? super GoodMan> men)

{

GoodMan good = new GoodMan();

good.name = “晁岳攀”;

men.add(good);

}

6．范型方法

考虑下面的代码,我们将一个数组的内容加到一个集合中

public void copyArrayToCollection(Man[] men, Collection<?>c)

{

for(Man man:men)

{

c.add(man);

}

}

这段代码时错的！

因为我们并不知道集合C的类型，所以不能将Man类型的数据加到集合中。

可以使用范型方法解决：

public <T> void copyArrayToCollection(T[] men, Collection<T>c)

{

for(T man:men)

{

c.add(man);

}

}

这里T时一个形式类型参数。

何时该采用通用方法？何时该采用通配符？

考虑下面的例子：

interface Collection<E>

{

public boolean containsAll(Collection<?> c);

public boolean addAll(Collection<? extends E> c);

}

改写成通用方法

interface Collection<E>

{

public <T> boolean containsAll(Collection<T> c);

public <T extends E> boolean addAll(Collection<T> c);

}

然而，在这里每个方法T只使用了一次,返回值不依赖形式参数，其他参数也不依赖形式参数。这说明实参被用作多态，这种情况下就应该用通配符。

Answer 2

普遍适用有
普遍适用类型 （int, float, userdefine...)
普遍适用算法 (insert, delete, find, ...)
其实，就是使用模板

比如
int max(int,int);
用模板
template<typename T>
T max(T,T);(什么类型都能比较大小)
就是普遍适用类型的例子