HDU 1534 Schedule Problem 差分约束输出一组解

    参考文章：1.《JAVA编程思想 第4版》   2.java泛型详解http://luckykapok918.blog.163.com/blog/static/2058650432012102341548827/  

    Java泛型（generics）是JDK 5中引入的一个新特性，允许在定义类和接口的时候使用类型参数（type parameter）。声明的类型参数在使用时用具体的类型来替换。泛型最主要的应用是在JDK 5中的新集合类框架中。对于泛型概念的引入，从好的方面来说，泛型的引入可以解决之前的集合类框架在使用过程中通常会出现的运行时刻类型错误（安全性更好），因为编译器可以在编译时刻就发现很多明显的错误。而从不好的地方来说，泛型不是JAVA语言出现时就有的组成部分，为了保证与旧有版本的兼容性，Java泛型的实现上存在着一些不够优雅的地方，后续的版本更新会为早期的设计缺陷所累。  

类型擦除

• 泛型类并没有自己独有的Class类对象。比如并不存在List<String>.class或是List<Integer>.class，而只有List.class。由于这一个擦除的特性，不难理解下面的代码为何错误。

• public class Erased<T>{
  	private final int SIZE=100;
  	public static void f(Object arg){
  		T var=new T();//Error
  		T[] array=new T[SIZE];//Error
  		T[] array=(T) new Object[SIZE];//Unchecked warning
  	}
  }

  
  
• 静态变量是被泛型类的所有实例所共享的。对于声明为MyClass<T>的类，访问其中的静态变量的方法仍然是 MyClass.myStaticVar。不管是通过new MyClass<String>还是new MyClass<Integer>创建的对象，都是共享一个静态变量。
• 泛型的类型参数不能用在Java异常处理的catch语句中。因为异常处理是由JVM在运行时刻来进行的。由于类型信息被擦除，JVM是无法区分两个异常类型MyException<String>和MyException<Integer>的。对于JVM来说，它们都是 MyException类型的。也就无法执行与异常对应的catch语句。
• 任何基本类型都不能作为类型参数。JAVA的基本数据类型有byte，short，int，long，float，double，char，boolean。不能创建ArrayList<int>之类的东西。如果要解决的话，JAVA自动包装机制是解决之道，比如可以创建一个ArrayList<Integer>，然后将Int用于容器即可。
• 一个类不能实现同一个泛型接口的两种变体。这是因为由于擦除，两种变体会变成完全一样的接口。例如下面代码就会造成冲突。

• interface Payable<T>{}
  class Employee implements Payable<Employee>{}
  class Hourly extends Employee implements Payable<Hourly>{}

  
  Hourly将无法编译，因为擦除会将Payable<Employee>和Payable<Hourly>简化成相同的类Payable。这样上面的代码就是重复的两次实现相同的接口。
• 方法重载时候注意：当被擦除的参数不能产生唯一的参数列表时，必须提供明显有区别的方法名。例如，下面的代码擦除以后，重载方法会产生相同的类型签名，这样编译器就会报错。

• public class list2<W,T>{
  	void f(List<T> v){}
  	void f(List<W> v){}
  }

  
  
  

     类型擦除的基本过程也比较简单，首先是找到用来替换类型参数的具体类。这个具体类一般是Object。如果指定了类型参数的上下界的话，则使用这个边界。把代码中的类型参数都替换成具体的类。同时去掉出现的类型声明，即去掉<>的内容。比如T get()方法声明就变成了Object get()；List<String>就变成了List。接下来就可能需要生成一些桥接方法（bridge method）。这是由于擦除了类型之后的类可能缺少某些必须的方法。比如考虑下面的代码：

[java] view plaincopy

1. class MyString implements Comparable<String> {        
2.     public int compareTo(String str) {                    
3.         return 0;            
4.     }    
5. }   

     实例分析

   问题1：类型参数向上转型。

           假设Apple类是Fruit类的子类，很多人会常常写这样一句代码：List<Fruit> flist=new ArrayList<Apple>()；这句代码是错误的！！！

           有人可能认为这不是向上转型么？事实上这不是向上转型。Apple的List不是Fruit的List，因为Fruit的List将会持有各种类型的Fruit，比如Orange,Banana。但是Apple的List持有的只是Apple和它的子类。因此，这种代码完全就是错误的。

           我们需要注意，List<Fruit> flist=new ArrayList<Fruit>()；flist.add(new Apple())；这样的代码才是大家所谓的向上转型。

    问题2：泛型对象调用方法。

           看看下面的代码：

class HasF{
	public void f();
}
class Manipulator<T>{
	private T tt;
	public Manipulator(T tt){this.tt=tt;}
	public void mani(){tt.f();}//Error
	public T get(){return tt;}
}
public class Erase(){
	public static void main(String []args){
	   HasF hf=new HasF();
	   Manipulator<HasF> mad=new Manipulator<HasF>(hf);
	   mad.mani();
	}
}

    问题3：创建类型实例。

         对于以下代码：

public class Erased<T>{
	private final int SIZE=100;
	public static void f(Object arg){
		T var=new T();//Error
		T[] array=new T[SIZE];//Error
	}
}

泛型问题的解决---边界

      以上实例中出现的问题就是因为擦除以后，编译器无法识别类型参数，因为解决的方法就是为类型参数指定一个大概的范围，这个就是边界。

     在使用泛型类的时候，既可以指定一个具体的类型，如List<String>就声明了具体的类型是String；也可以用通配符?来表示未知类型，如List<?>就声明了List中包含的元素类型是未知的。 通配符所代表的其实是一组类型，但具体的类型是未知的。List<?>所声明的就是所有类型都是可以的。但是List<?>并不等同于List<Object>。List<Object>实际上确定了List中包含的是Object及其子类，在使用的时候都可以通过Object来进行引用。而List<?>则其中所包含的元素类型是不确定。其中可能包含的是String，也可能是 Integer。如果它包含了String的话，往里面添加Integer类型的元素就是错误的。正因为类型未知，就不能通过new ArrayList<?>()的方法来创建一个新的ArrayList对象。因为编译器无法知道具体的类型是什么。但是对于 List<?>中的元素确总是可以用Object来引用的，因为虽然类型未知，但肯定是Object及其子类。

     如上所示，试图对一个带通配符的泛型类进行操作的时候，总是会出现编译错误。其原因在于通配符所表示的类型是未知的。因为对于List<?>中的元素只能用Object来引用，在有些情况下不是很方便。在这些情况下，可以使用上下界来限制未知类型的范围。 如List<? extends Number>说明List中可能包含的元素类型是Number及其子类。而List<? super Number>则说明List中包含的是Number及其父类。当引入了上界之后，在使用类型的时候就可以使用上界类中定义的方法。比如访问 List<? extends Number>的时候，就可以使用Number类的intValue等方法。

    在有了边界以后我们再来看上述问题的解决之道。

    问题1：我们只需将List<Fruit> filist=new ArrayList<Apple>();换成List<? entends Fruit> filist=new ArrayList<Apple>();即可。此时flist是”具有任何从Fruit继承的类型的列表“。

    问题2：将代码改成：

class HasF{
	public void f();
}
class Manipulator<T extends HasF>{
	private T tt;
	public Manipulator(T tt){this.tt=tt;}
	public void mani(){tt.f();}
	public T get(){return tt;}
}
public class Erase(){
	public static void main(String []args){
	   HasF hf=new HasF();
	   Manipulator<HasF> mad=new Manipulator<HasF>(hf);
	   mad.mani();
	}
}

     问题3:将代码改成：

class ClassFactory<T>{
	T x;
	public ClassFactory(Class<T> kind){
		try{
			x-kind.newInstance();
		}catch(Exception e){
			new RuntimeException(e);
		}
	}
}

类型系统

• 相同类型参数的泛型类的关系取决于泛型类自身的继承体系结构。即List<String>是Collection<String> 的子类型，List<String>可以替换Collection<String>。这种情况也适用于带有上下界的类型声明。
• 当泛型类的类型声明中使用了通配符的时候， 其子类型可以在两个维度上分别展开。如对Collection<? extends Number>来说，其子类型可以在Collection这个维度上展开，即List<? extends Number>和Set<? extends Number>等；也可以在Number这个层次上展开，即Collection<Double>和 Collection<Integer>等。如此循环下去，ArrayList<Long>和 HashSet<Double>等也都算是Collection<? extends Number>的子类型。
• 如果泛型类中包含多个类型参数，则对于每个类型参数分别应用上面的规则。

     开发自己的泛型类和泛型方法

     泛型类与一般的Java类基本相同，只是在类和接口定义上多出来了用<>声明的类型参数。一个类可以有多个类型参数，如 MyClass<X, Y, Z>。 每个类型参数在声明的时候可以指定上界。所声明的类型参数在Java类中可以像一般的类型一样作为方法的参数和返回值，或是作为域和局部变量的类型。但是由于类型擦除机制，类型参数并不能用来创建对象或是作为静态变量的类型。考虑下面的泛型类中的正确和错误的用法。

class ClassTest<X extends Number, Y, Z> {           
    private X x;            
    private static Y y; //编译错误，不能用在静态变量中            
    public X getFirst() {          //正确用法                  
        return x;            
    }            
    public void wrong() {                    
        Z z = new Z(); //编译错误，不能创建对象 ，因为泛型类并没有自己独立的Class类对象           
    }  
}  

public <T> T f(T x){
	return x;
}

     3.容器类的使用

public class ListMaker<T>{
	private Class<T> kind;
	T[] create(){
		return (T[])Array.newInstance(kind, 100);
	}
}

public class ListMaker<T>{
	List<T> create(){
		return new ArrayList<T>();
	}
}

 最佳实践

• 在代码中避免泛型类和原始类型的混用。比如List<String>和List不应该共同使用。这样会产生一些编译器警告和潜在的运行时异常。当需要利用JDK 5之前开发的遗留代码，而不得不这么做时，也尽可能的隔离相关的代码。
• 在使用带通配符的泛型类的时候，需要明确通配符所代表的一组类型的概念。由于具体的类型是未知的，很多操作是不允许的。
• 泛型类最好不要同数组一块使用。你只能创建new List<?>[10]这样的数组，无法创建new List<String>[10]这样的。这限制了数组的使用能力，而且会带来很多费解的问题。因此，当需要类似数组的功能时候，使用集合类即可。
• 不要忽视编译器给出的警告信息。

HDU 1534 Schedule Problem 差分约束输出一组解,布布扣,bubuko.com

HDU 1534 Schedule Problem 差分约束输出一组解

原文：http://blog.csdn.net/u011686226/article/details/24185409