Java和C++在细节上的差异(四)
八、泛型程序设计：
1. 泛型类的定义，见如下代码：
1 publicclassPair<T,U> {
2 publicPair() { first = null; second = null; }
3 publicPair(T first,U second) { this.first = first; this.second = second; }
4
5 publicT getFirst() { returnfirst; }
6 publicU getSecond() { returnsecond; }
7 publicvoidsetFirst(T first) { this.first = first; }
8 publicvoidsetSecond(U second) { this.second = second; }
9
10 privateT first;
11 privateU second;
12 }
以上代码中的T,U都是泛型类Pair的类型参数。以下为C++中模板类的定义方式：
1 template<typename T,typename U>
2 classPair {
3 public:
4 Pair(T first,U second): _first(first),_second(second) {}
5 ~Pair() {}
6 public:
7 T getFirst() { return_first; }
8 U getSecond() { return_second; }
9 voidsetFirst(T frist) { _first = first; }
10 voidsetSecond(U second) { _second = second; }
11 private:
12 T _first;
13 U _second;
14 }
2. 泛型方法的定义，在Java中泛型方法不一定声明在泛型类中，可以声明在普通类中，见如下代码：
1 publicclassMyFirst {
2 publicstaticvoidmain(String[] args) throwsException {
3 String[] names = {"john","Q.","Public"};
4 String middle = ArrayAlgo.<String>getMiddle(names);
5 System.out.println(middle);
6 }
7 }
8
9 classArrayAlgo {
10 publicstatic<T> T getMiddle(T[] a) {
11 returna[a.length/2];
12 }
13 }
在以上代码中可以看出getMiddle方法为静态泛型方法，类型变量位于修饰符"public static" 的后面，返回值的前面。调用的时候在方法名的前面给出了参数类型。由于Java的编译器提供类型推演的功能，既类型参数可以通过函数参数的类型进行推演，因此也可以直接调用泛型函数，如String middle = ArrayAlgo.getMiddle(names)。如果编译器无法通过函数参数的类型推演出类型参数的实际类型，这样将会导致编译错误。在C++中同样存在模板函数，也同样存在模板函数的类型推演，在这一点上主要的差异来自于函数声明的语法，见如下C++代码：
1 classArrayAlgo {
2 public:
3 template<typename T>
4 staticT getMiddle(T* a,size_t len) {
5 returna[len/2];
6 }
7 };
8
9 intmain()
10 {
11 intv[] = {1,2,3};
12 intret = ArrayAlgo::getMiddle(v,3);
13 printf("This value is %d.\n",ret);
14 return0;
15 }
3. 类型参数的限定：有些泛型函数在使用类型参数变量时，经常会用到该类型的特殊方法，如在进行数组元素比较时，要求数组中的元素必须是Comparable接口的实现类，见如下代码：
1 publicstatic<T> T min(T[] a) {
2 if(a == null|| a.length == 0)
3 returnnull;
4 T smallest = a[0];
5 for(inti = 0; i < a.length; ++i) {
6 if(smallest.compareTo(a[i]) > 0)
7 smallest = a[i];
8 }
9 returnsmallest;
10 }
在以上代码中，数组元素的类型为T，如果该类型并未提供compareTo域方法，将会导致编译错误，如何确保类型参数确实提供了compareTo方法呢？如果T是Comparable接口的实现类，那么该方法一定会被提供，因此可以通过Java语法中提供的类型参数限定的方式来确保这一点。见如下修订代码：
1 publicstatic<T extendsComparable> T min(T[] a) {
2 if(a == null|| a.length == 0)
3 returnnull;
4 T smallest = a[0];
5 for(inti = 0; i < a.length; ++i) {
6 if(smallest.compareTo(a[i]) > 0)
7 smallest = a[i];
8 }
9 returnsmallest;
10 }
其中的<T extends Comparable>语法保证了类型参数必须是Comparable接口的实现类，否则将会导致编译错误。Java中可以支持多接口的限定，之间用&分隔，如<T extends Comparable & Serializable>和之前的例子一样，尽管同样都会导致编译错误，但是后者不仅会产生更为明确的编译错误信息，同样也使使用者能够更加清晰的看到该方法的使用规则。在标准C++中并未提供这样的限定，但是在C++中对该种方式有另外一种称谓，叫做"类型绑定"，在Boost等开源库中通过更复杂的模板技巧模仿了该功能的实现。然而，就泛型的该功能而言，C#的支持也是相当不错的，可参考C#泛型中的which关键字。
在标准C++中，其模板的实现较Java而言更为灵活和强大。对于第一个例子中的代码，只是要求模参必须提供compareTo方法即可通过编译。
1 template<typename T>
2 staticT min(T* a,size_t len) {
3 T smallest = a[0];
4 for(inti = 0; i < len; ++i) {
5 if(smallest.compareTo(a[i]) > 0)
6 smallest = a[i];
7 }
8 returnsmallest;
9 }
注：C++中的模板是在引用时才编译的，因此如果在模板类型中出现任何语法错误，但此时尚未有任何引用时，编译器是不会报错的。
4. 泛型代码中的类型擦除：记得在我阅读Thinking in Java 4th 的时候，书中给出了一些比较明确的解释，为什么Java会这样实现泛型，其最主要的原因是为了考虑向前兼容，也承认这样的实现方式有着很多的缺陷和弊病，希望Java在今后的版本中予以补足。
简单的说类型擦除，就是几乎所有的泛型相关的行为都是由编译器通过暗插各种各样的代码，或者是暗自修订部分代码的声明，然后再将修订后的代码(基本不再包含泛型信息)生成字节码后交给JVM去执行，因此可以据此判断在JVM中对我们的泛型类型是一无所知的。C++也是同样的道理，只是编译器完成的工作被定义为类型展开或类型实例化，因此，同样的模板类，如果实例化的类型参数不同，那么用他们声明出来的类对象也同样不属于相同类型的对象，其限制主要表现为，不能通过缺省copy constructor或者缺省赋值操作符来完成对象之间的复制，除非其中某个类型实例化后的对象专门针对另外一种类型实例化后的类型进行了copy constructor和赋值等于的重载。
1) 类型擦除：将类型参数替换为限定类型，如果没有限定类型则替换为Object，见如下代码：
1 publicclassPair<T> {
2 publicPair(T first,T second) { this.first = first; this.second = second; }
3 publicT getFirst() { returnfirst; }
4 publicT getSecond() { returnsecond; }
5 publicvoidsetFirst(T first) { this.first = first; }
6 publicvoidsetSecond(T second) { this.second = second; }
7 privateT first;
8 privateT second;
9 }
由于Pair中的类型参数T没有限定类型，因此类型擦除后将会变成如下代码：
1 publicclassPair {
2 publicPair(Object first,Object second) { this.first = first; this.second = second; }
3 publicObject getFirst() { returnfirst; }
4 publicObject getSecond() { returnsecond; }
5 publicvoidsetFirst(Object first) { this.first = first; }
6 publicvoidsetSecond(Object second) { this.second = second; }
7 privateObject first;
8 privateObject second;
9 }
因此尽管在调用Pair时，传递的类型参数有所不同，如String、Date，但是在类型擦除之后，他们将成为相同的类型。如果类型参数存在多个限定类型，则取第一个限定类型作为擦除后的类型参数，见如下代码：
1 publicclassInterval<T extendsComparable & Serializable> implementsSerializable {
2 publicInterval(T first, T second) {
3 if(first.compareTo(second) <= 0) {
4 lower = first;
5 upper = second;
6 } else{
7 lower = second;
8 uppper = first;
9 }
10 }
11 privateT lower;
12 privateT upper;
13 }
擦除类型信息后的原始类型如下：
1 publicclassInterval implementsSerializable {
2 publicInterval(Comparable first, Comparable second) {
3 if(first.compareTo(second) <= 0) {
4 lower = first;
5 upper = second;
6 } else{
7 lower = second;
8 uppper = first;
9 }
10 }
11 privateComparable lower;
12 privateComparable upper;
13 }
5. 泛型类向遗留代码的兼容：由于编译器自动完成了类型信息的擦除，因此在原有调用原始类型的地方，可以直接传入等价的泛型类，只要保证该泛型类在类型擦除后可以符合被调用函数参数的语法要求即可，见如下代码：
1 publicclassTestMain {
2 publicstaticvoidtest(MyClass t) {
3 System.out.println(t.getValue());
4 }
5
6 publicstaticvoidmain(String[] args) {
7 MyClass<Integer> v = newMyClass<Integer>(5);
8 test(v);
9 }
10 }
11 classMyClass<T> {
12 publicMyClass(T t) {
13 this.t = t;
14 }
15 publicT getValue() { returnt;}
16 privateT t;
17 }
6. 约束与局限性：
1) 不能使用原始类型作为类型参数，如int、double等，因为他们和Object之间没有直接的继承关系，因此在需要时只能使用包装类，如Integer、Double分别予以替换，不能这样的替换确实也带来了效率上的折损，C++中没有这样的限制，因此模板类的增多只会影响编译的效率和不会影响运行时的效率。
2) 运行时的类型查询只适用于原始类型，即if (a instanceof Pair<String>) 等价于if (a instanceof Pair)。
3) 泛型类对象调用getClass()方法返回的Class对象都是擦除类型信息的原始Class类型，因此在做比较时，他们将为真，见如下代码：
1 publicclassTestMain {
2 publicstaticvoidmain(String[] args) {
3 MyClass<Integer> i = newMyClass<Integer>(5);
4 MyClass<Double> d = newMyClass<Double>(5.0);
5 //返回的均为MyClass.Class
6 if(d.getClass() == i.getClass())
7 System.out.println("Type info will be ignored here");
8 }
9 }
10 classMyClass<T> {
11 publicMyClass(T t) {
12 this.t = t;
13 }
14 publicT getValue() { returnt;}
15 privateT t;
16 }
17 /* 输入结果：
18 Type info will be ignored here
19 */
4) 泛型类不能实现Throwable接口，换言之泛型类不能成为异常类，否则会导致编译错误。
5) 不能声明参数化类型的数组，如Pair<String>[] table = new Pair<String>[10]; 在擦除类型后将会变为Pair[] table = new Pair[10]; 因此可以执行该转换：Objec[] objarray = table; 由于数组可以记住元素的类型，如果此时试图插入错误的类型元素，将会导致异常ArrayStoreException的抛出。C++中没有该限制。
6) 不能实例化泛型类型的变量，如public Pair() { first = new T(); second = new T();}，C++中不存在这样的限制，针对以上写法，类型T只要存在缺省的构造函数即可。如果确实需要实例化类型参数的对象，见如下代码：
1 publicstatic<T> Pair<T> makePair(Class<T> c1) {
2 returnnewPair<T>(c1.newInstance(),c1.newInstance());
3 }
4 publicstaticvoidmain(String[] args) {
5 //String.class的类型为Class<String>
6 Pair<String> p = Pair.makePair(String.class);
7 }
这里主要是利用Class类型本身也是泛型类型，可以利用Class<T>的类型参数推演出Pair<T>中T的类型。同样的道理带有类型参数的数组对象也不能直接创建，需要利用Array的反射机制来辅助完成，见如下代码：
1 publicstatic<T extendsComparable> T[] minmax(T[] a) {
2 T[] mm = (T[])Array.newInstance(a.getClass().getComponentType(),a.length);
3 //do something here based on mm
4 returnmm;
5 }
7) 泛型类不能应用于静态上下文中，见如下代码：
1 publicclassSingleton<T> {
2 publicstaticT getInstance() { //Compilation ERROR
3 returnsingleInstance;
4 }
5 privateT singleInstance; //Compilation ERROR
6 }
因为这样的写法在定义Singleton<String>和Singleton<Date>之后，由于类型擦除，将会生成唯一一个Singleton原始共享对象，事实上这并不是我们所期望的结果，在C++中没有这样的限制，甚至有的时候还可以利用这样的机制针对不同类型的对象作声明计数器用，见如下代码：
1 template<typename T>
2 classMyClassCounter {
3 public:
4 MyClassCounter(T t) {
5 _t = t;
6 _counter++;
7 }
8
9 operatorT() {
10 return_t;
11 }
12
13 T* operator->() {
14 return&_t;
15 }
16 intgetCount() const{ return_counter; }
17 private:
18 T _t;
19 staticint_counter;
20 }
8) 泛型类不能同时继承或实现只是拥有不同参数类型的同一泛型类，如public class MyClass implements Comparable<String>, Comparable<Date> {}
7. 泛型类型的继承规则：
1) 如果public class Manager extends Employee {}，那么Pair<Employee> pe = new Pair<Manager>()将会是非常的赋值操作，会导致编译错误。试想如下代码引发的运行时问题。在C++中这种赋值方式同样会导致编译错误，因为他们在类型实例化之后就被视为完全无关的两个类型。
1 publicvoidtest() {
2 Pair<Manager> manager = newPair<Manager>();
3 Pair<Employee> employee = manager; //compilation error
4 employee.setFirst(otherEmployeeButNotManager); //employee的另外一个子类，但不是Manager。
5 }
2) 数组由于在运行时会记住元素的类型，因此数组可以完成这样的赋值，如Manager[] manager = {}; Employee[] employee = manager;如果赋值之后出现错误的元素赋值将会引发ArrayStoreException异常。
3) 泛型类型可以直接赋值给擦除类型后的原始类型，但是同样也会出现2)中数组赋值的问题，只是触发的异常改为ClassCastException，见如下代码：
1 publicvoidtest() {
2 Pair<Manager> manager = newPair<Manager>();
3 Pair rawType = manager;
4 rawType.setFirst("Hello"); //only compilation warning, but will encounter runtime error.
5 }
4) 如果public class ArrayList<Manager> extends List<Manager> {}, 那么从ArrayList<Manager>到List<Manager>的赋值是允许的，这一点和普通类型是一致的，该规则同样适用于C++。
8. 泛型类型的通配符类型：该泛型特征在标准C++中完全不被支持，C#中存在类似的特征。见以下代码：
1) 子类型限定：
1 publicclassManager extendsEmployee {}
2
3 publicstaticvoidprintBuddies(Pair<Employee> p) {
4 }
5
6 publicstaticvoidmain(String[] args) {
7 printBuddies(newPair<Employee>()); //legal
8 printBuddies(newPair<Manager>()); //illegal;
9 }
但是如果将printBuddies改为：void printBuddies(Pair<? extends Employee> p)，上例中main函数将可以通过编译。<? extends Employee>的语义为所有Employee的子类都可以做printBuddies函数参数的类型参数。对于7-1)中的示例代码，如果改为通配符类型将可以通过编译并正常运行，但是仍然存在一定的限制，见如下代码：
1 publicvoidtest() {
2 Pair<Manager> manager = newPair<Manager>();
3 Pair<? extendsEmployee> employee = manager; //legal here.
4 //由于otherEmployeeButNotManager虽为Employee子类，但可能并非Manager类，
5 //由于setFirst的参数将会声明为void setFirst(? extends Employee),由于
6 //编译器无法确定setFirst参数的实际类型，因此将会直接报告编译错误。
7 employee.setFirst(otherEmployeeButNotManager); //compilation error
8 }
和setFirst相比，getFirst将会正常编译并运行，因为返回值无论是什么子类型，都不会带来影响和破坏。
2) 超类型限定：Pair<? super Manager>表示参数类型一定是Manager的超类。因此和子类型限定刚好相反，setFirst将是合法的，而getFirst将会产生编译错误。
3) 无限定通配符，如Pair<?>，该泛型类型的setFirst(?)方法不能被调用，即便传入的参数是Object，这样是Pair<?>和Pair之间最大的差异。该方法还有一个比较重要的作用就是用于提示泛型函数的调用者，该泛型函数更期望参数是带有类型参数的泛型类型，而不是原始类型，即便原始类型也可能正常的工作，见如下代码：
1 publicclassTestMain {
2 @SuppressWarnings("unchecked")
3 //public static <T> T print(MyClass myclass),同样可以正常的工作，
4 //但是会有编译警告产生。
5 publicstatic<T> T print(MyClass<?> myclass) {
6 myclass.print();
7 return(T)myclass.get();
8 }
9
10 publicstaticvoidmain(String[] args) {
11 Integer ii = newInteger(5);
12 print(newMyClass<Integer>(ii));
13 }
14 }
15
16 classMyClass<T> {
17 publicMyClass(T t) {
18 _t = t;
19 }
20 T get() { return_t;}
21
22 publicvoidprint() {
23 System.out.println(_t);
24 }
25 privateT _t;
26 }
九、集合：
1. Java集合类库中最重要的两个接口Collection<E>和Map<K,V>，其中Collection接口又再次划分为List和Set两大子接口，List中可以包含重复的元素，Set中则不可以。以下列举出一些常用的集合实现类，他们均分别继承自这两个接口：
1) ArrayList: 一种可以动态增长和缩减的索引序列(动态数组，类似于C++中的vector)；
2) LinkedList: 一种可以在任何位置进行高效的插入和删除操作的有序序列(类似于C++中list)；
3) ArrayDeque: 一种用循环数组实现的双端队列(类似于C++中的deque)；
4) HastSet：一种没有重复元素的无序集合(C++的标准库中并未提供hashset集合，但是Windows的VC和Linux平台下的gcc均各自提供了hashset容器)；
5) TreeSet: 一种有序集(类似于C++中的set)；
6) EnumSet: 一种包含枚举类型值的集；
7) LinkedHashSet: 一种可以记住元素插入次序的集，在其内部由LinkedList负责维护插入的次序，HashSet来维护Hash；
8) HashMap：一种存储键值对关联的数据结构(C++的标准库中并未提供hashmap集合，但是Windows的VC和Linux平台下的gcc均各自提供了hashmap容器)；
9) TreeMap：一种键值有序排列的映射表(类似于C++中的map)；
10) EnumMap：一种键值属于枚举类型的映射表；
11) LinkedHashMap：一种可以记住键值项插入次序的映射表；
2. ArrayList：该集合的底层是通过动态数组来实现的，集合构造的时候可以指定一个初始容量，当插入的元素过多导致已有的容量不能容纳新元素是，其底层数组的容量将自动增长原有容量的1.5 倍，这样会带来一定的空间浪费，但是为了避免经常扩张而带来的性能开销，只能是用空间换取时间了。如果在容器的中间添加或者删除一个元素都将会导致后面的元素向后或向前移动一个位置，如果元素数量较多且该操作比较频繁，将会导致系统的性能降低，然而对于容器中元素的随机访问性能较好，以下为ArrayList的常用示例代码：
1 publicstaticvoidshowIterator() {
2 ArrayList<String> list = newArrayList<String>();
3 list.add("Monday");
4 list.add("Tuesdag");
5 list.add("Wednesday");
6 Iterator<String> iterator = null;
7 iterator = list.iterator();
8 //while
9 while(iterator.hasNext()) {
10 String element = iterator.next();
11 System.out.println(element);
12 }
13 //for
14 for(iterator = list.iterator(); iterator.hasNext();) {
15 String element = iterator.next();
16 System.out.println(element);
17 }
18 //for each
19 for(String element : list) {
20 System.out.println(element);
21 }
22 }
23
24 publicstaticvoidshowSetAndGet() {
25 ArrayList<String> nums = newArrayList<String>();
26 nums.clear();
27 nums.add("One");
28 nums.add("Two");
29 nums.add("Three");
30 System.out.println(nums);
31 nums.set(0, "Uno");
32 nums.set(1, "Dos");
33 nums.set(2, "Tres");
34 for(inti = 0; i < nums.size(); ++i)
35 System.out.println(nums.get(i));
36 }
37
38 publicstaticvoidshowRemoveAndSize() {
39 ArrayList<String> al = newArrayList<String>();
40 System.out.println("Initial size of al: " + al.size());
41 al.add("C");
42 al.add("A");
43 al.add("E");
44 al.add("B");
45 al.add(1, "A2");
46 System.out.println("Size of al after additions: " + al.size());
47 System.out.println("Contents of al: " + al);
48 al.remove("F");
49 al.remove(2);
50 System.out.println("Size of al after deletions: " + al.size());
51 System.out.println("Contents of al: " + al);
52 Iterator<String> it = al.iterator();
53 //Notes：remove() must be called after next()
54 it.next();
55 it.remove();
56 System.out.println("Size of al after deletions: " + al.size());
57 System.out.println("Contents of al: " + al);
58 }
59
60 publicstaticvoidshowSubListAndCopyToArray() {
61 ArrayList<String> arrayList = newArrayList<String>();
62 arrayList.add("1");
63 arrayList.add("2");
64 arrayList.add("3");
65 arrayList.add("4");
66 arrayList.add("5");
67 List<String> lst = arrayList.subList(1, 3);
68 for(inti = 0; i < lst.size(); i++)
69 System.out.println(lst.get(i));
70 // remove one element from sub list
71 String obj = lst.remove(0);
72 System.out.println(obj + " is removed");
73 for(String str: arrayList)
74 System.out.println(str);
75 //get object array with normal method
76 Object[] objArray = arrayList.toArray();
77 for(Object obj1 : objArray)
78 System.out.println(obj1);
79 //get object array with generic method
80 String[] strArray = arrayList.toArray(newString[0]);
81 for(String str : strArray)
82 System.out.println(str);
83 }
84
85 publicstaticvoidshowListIterator() {
86 ArrayList<String> aList = newArrayList<String>();
87 aList.add("1");
88 aList.add("2");
89 aList.add("3");
90 aList.add("4");
91 aList.add("5");
92
93 ListIterator<String> listIterator = aList.listIterator();
94 while(listIterator.hasNext()) {
95 System.out.println(listIterator.next());
96 System.out.println("Previous: " + listIterator.previousIndex());
97 System.out.println("Next: " + listIterator.nextIndex());
98 }
99 while(listIterator.hasPrevious()) {
100 System.out.println(listIterator.previous());
101 System.out.println("Previous: " + listIterator.previousIndex());
102 System.out.println("Next: " + listIterator.nextIndex());
103 }
104 listIterator = aList.listIterator(2);
105 listIterator.next();
106 listIterator.set("100");
107 listIterator.next();
108 listIterator.remove();
109 for(String str : aList)
110 System.out.println(str);
111
112 if(aList.contains("4"))
113 System.out.println("True");
114 else
115 System.out.println("False");
116 }
117
118 publicstaticvoidshowFillAndReplace() {
119 ArrayList<String> arrayList = newArrayList<String>();
120 arrayList.add("A");
121 arrayList.add("B");
122 arrayList.add("A");
123 arrayList.add("C");
124 arrayList.add("D");
125 Collections.replaceAll(arrayList, "A", "Replace All");
126 System.out.println(arrayList);
127 Collections.fill(arrayList, "REPLACED");
128 System.out.println(arrayList);
129 }
130
131 publicstaticvoidshowCollectionOperation() {
132 List<String> colours = newArrayList<String>();
133 colours.add("red");
134 colours.add("green");
135 colours.add("blue");
136
137 System.out.println(colours);
138 Collections.swap(colours, 0, 2);
139 System.out.println(colours);
140
141 Collections.reverse(colours);
142 System.out.println(colours);
143
144 Collections.sort(colours);
145 System.out.println(Arrays.toString(colours.toArray()));
146 Collections.sort(colours, Collections.reverseOrder());
147 System.out.println(Arrays.toString(colours.toArray()));
148
149 intindex = Collections.binarySearch(colours, "green");
150 System.out.println("Element found at : " + index);
151 ArrayList<Integer> arrayList = newArrayList<Integer>();
152 arrayList.add(newInteger("3"));
153 arrayList.add(newInteger("1"));
154 arrayList.add(newInteger("8"));
155 arrayList.add(newInteger("3"));
156 arrayList.add(newInteger("5"));
157 System.out.println(Collections.min(arrayList));
158 System.out.println(Collections.max(arrayList));
159 }
160
161 publicstaticvoidshowMinMax() {
162 ArrayList<Integer> arrayList = newArrayList<Integer>();
163 arrayList.add(newInteger("3"));
164 arrayList.add(newInteger("1"));
165 arrayList.add(newInteger("8"));
166 arrayList.add(newInteger("3"));
167 arrayList.add(newInteger("5"));
168 System.out.println(Collections.min(arrayList));
169 System.out.println(Collections.max(arrayList));
170 }
171
172 publicstaticvoidshowSynchronizedList() {
173 ArrayList arrayList = newArrayList();
174 List list = Collections.synchronizedList(arrayList);
175 //list之后的并发操作将不再需要synchronized关键字来进行同步了。
176 }
3. LinkedList: 该集合是通过双向链表来实现的，对于指定位置元素的遍历其内部做了一个小的优化，如果position大于len/2，由于内部的数据结构是双向链表，因此可以从后向前遍历，以减少遍历过程中节点跳转的次数。ArrayList中的大部分代码示例都适用于LinkedList，以下近给出LinkedList特有的常用示例代码：
1 publicstaticvoidshowNewFeatures(String[] args) {
2 LinkedList<String> lList = newLinkedList<String>();
3 lList.add("1");
4 lList.add("2");
5 lList.add("3");
6 lList.add("4");
7 lList.add("5");
8
9 System.out.println("First element of LinkedList is : " + lList.getFirst());
10 System.out.println("Last element of LinkedList is : " + lList.getLast());
11 System.out.println(lList);
12
13 String str = lList.removeFirst();
14 System.out.println(str + " has been removed");
15 System.out.println(lList);
16 str = lList.removeLast();
17 System.out.println(str + " has been removed");
18 System.out.println(lList);
19
20 lList.addFirst("1");
21 System.out.println(lList);
22 lList.addLast("5");
23 System.out.println(lList);
24 }
4. ArrayList和LinkedList的相同点：
1) 都是接口List<E>的实现类；
2) 都可以通过iterator()方法返回Iterator<E>迭代器对象，并可以通过该对象遍历容器中的元素；
3) 如果多个Iterator<E>实例同时引用同一个集合对象，那么当有一个正在遍历，而另外一个修改(add/remove)了集合对象中的元素，对于第一个迭代器再进行迭代时将会引发ConcurrentModificationException异常的发生。
5. ArrayList和LinkedList的不同点：
1) 对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是统一的，分配一个内部Entry对象。
2) 在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。
3) LinkedList不支持高效的随机元素访问。
4) ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间
在C++的标准库中，ArrayList和LinkedList之间的使用差异以及各自的优缺点也同样反映于vector和list。
6. HashSet: 散列表为每个对象计算出一个整数(通过Object缺省的或类重载的hashCode域方法)，称为散列码。在Java中，散列表是使用链表的数组来实现的，每个链表被称为一个哈希桶。如果想在哈希表中查找一个对象，则需要先计算对象的hashCode，之后对表内的桶数取余数，得到的结果就是哈希桶的索引，此时如果该桶为空桶，就可以直接将该对象插入到该桶中，如果已经有对象存在了，则需要逐个进行比较，一旦发现该与该对象相等的对象(equals()返回true)，就会放弃本次插入操作，否则将该对象插入到该桶的末端。HashSet在构造的时候提供两个参数，一个是initialCapacity指定了桶的数量(实际的桶数为2的initialCapacity次幂)，另一个是loadFactortian(0.0--1.0,推荐值为0.75)，当桶的填充百分比达到该值后，哈希表内的哈希桶数将double，重新填充已有对象，该操作被称为rehash，rehash是十分影响效率的操作，因为为了尽可能避免该事件的发生，因可能在构造HashSet的时候给出一个合理的参数。以下为HashSet的常用示例代码：
1 publicstaticvoidshowAddAndIterator() {
2 HashSet<String> hs = newHashSet<String>();
3 hs.add("B");
4 hs.add("A");
5 hs.add("D");
6 hs.add("E");
7 hs.add("C");
8 hs.add("F");
9 System.out.println(hs);
10 Iterator<String> it = hs.iterator();
11 while(it.hasNext())
12 System.out.println(it.next());
13 }
14 publicstaticvoidshowRemoveAndClearAndContains() {
15 HashSet<Integer> hSet = newHashSet<Integer>();
16 hSet.add(newInteger("1"));
17 hSet.add(newInteger("2"));
18 hSet.add(newInteger("3"));
19 System.out.println(hSet.contains(newInteger("3")));
20 System.out.println(hSet);
21 booleanblnRemoved = hSet.remove(newInteger("2"));
22 System.out.println(hSet.contains(newInteger("2")));
23 System.out.println(blnRemoved);
24 System.out.println(hSet);
25 hSet.clear();
26 System.out.println(hSet);
27 System.out.println(hSet.isEmpty());
28 }
29
30 publicstaticvoidshowToArrayListAndArray() {
31 HashSet<String> hs = newHashSet<String>();
32 hs.add("B");
33 hs.add("A");
34 hs.add("D");
35 System.out.println(hs);
36 List<String> list = newArrayList<String>(hs);
37 Object[] objects = list.toArray();
38 for(Object obj : objects)
39 System.out.println("Object = " + obj);
40 String[] strs = list.toArray(newString[0]);
41 for(String str : strs)
42 System.out.println("String = " + str);
43 }
44
45 publicstaticvoidshowToHashSetAndRemoveDuplicate() {
46 Integer[] numbers = { 7, 7, 8, 9, 10, 8, 8, 9, 6, 5, 4 };
47 List<Integer> list = Arrays.asList(numbers);
48 Set<Integer> set = newHashSet<Integer>(list);
49 for(Integer o : set)
50 System.out.print(o + ", ");
51 }
52
53 publicstaticvoidshowMinMax() {
54 HashSet<Long> hashSet = newHashSet<Long>();
55 hashSet.add(newLong("9"));
56 hashSet.add(newLong("4"));
57 hashSet.add(newLong("2"));
58 hashSet.add(newLong("2"));
59 hashSet.add(newLong("3"));
60 Object objMin = Collections.min(hashSet);
61 System.out.println("Minimum Element of Java HashSet is : " + objMin);
62 Object objMax = Collections.max(hashSet);
63 System.out.println("Maximum Element of Java HashSet is : "+ objMax);
64 }
65
66 publicstaticvoidshowSynchronizedSet() {
67 HashSet hashSet = newHashSet();
68 Set set = Collections.synchronizedSet(hashSet);
69 //set之后的并发操作将不再需要synchronized关键字来进行同步了。
70 }
7. TreeSet：该集合为有序集合，数据在插入集合后便按照自定义的排序规则将插入的对象进行排序，该集合主要是通过两种方式排序插入对象的，一种是要求集合元素类必须是Comparable<T>的实现类，这样在插入对象的时候，集合可以根据compareTo方法的返回值来确定新插入对象的位置，另外一种方式是通过在构造该集合对象的时候，传入Comparator<T>的实现类作为参数，之后所有插入的对象都是通过Comparator<T>的compare方法的返回值来决定新对象的位置。该集合是通过RBTree(红黑树)来实现排序的，这一点和C++标准库中的set和map是一致的。由于对象插入集合之后是有序的，因此该集合的插入效率要低于HashSet的插入效率。TreeSet和HashSet相比主要的差异来自于对象的排序规则，以上HashSet的示例代码均适用于TreeSet，下面只是列出对象比较的代码：
1 publicclassItem implementsComparable<Item> {
2 publicintcompareTo(Item other) {
3 returnpartNumber - other.partNumber;
4 }
5 }
6 publicstaticvoidmain(String[] args) {
7 SortedSet<Item> parts = newTreeSet<Item>();
8 parts.add(newItem("Toaster",1234));
9 parts.add(newItem("Widget",4562));
10 parts.add(newItem("Modem",9912));
11 System.out.println(parts);
12
13 SortedSet<Item> sortByDescription = newTreeSet<Item>(newComparator<Item>() {
14 publicintcompare(Item a,Item b) {
15 String descA = a.getDescription();
16 String descB = b.getDescription();
17 returndescA.compareTo(descB);
18 }
19 });
20 sortByDescription.addAll(parts);
21 System.out.println(sortByDescription);
22 }
8. PriorityQueue(优先级对象): 该容器也是有序集合，和TreeSet不同的是，该集合只是保证当从集合的头部取出数据的时候，总是取出队列中最小(优先级最高)的元素。该集合内部是通过"堆"的数据结构实现的，该结构只有第一个元素(头部元素)保证为该集合中最大的或最小的元素，其余元素没有固定的顺序，但是当集合有新的对象从尾部插入或是从头部取出时，集合内部的相关元素会进行比较的比较最终再次决定出谁是最大或最小的元素作为头部元素。在JDK提供的classes中Timer是通过该数据结构实现的，从而保证了Timer每次获取任务时都是最应该被调度的TimerTask，见如下代码：
1 publicclassTestMain {
2 publicstaticvoidmain(String[] args) {
3 PriorityQueue<String> pq = newPriorityQueue<String>();
4 pq.add("1");
5 pq.add("6");
6 pq.add("4");
7 pq.offer("5");
8 pq.offer("3");
9 pq.offer("2");
10 pq.offer("7");
11 //以下输出将以无序的结果输出
12 System.out.println(pq);
13 //以下输出将以有序的结果输出
14 while(pq.peek() != null) {
15 String str = pq.poll();
16 System.out.println(str);
17 }
18 intinitCapacity = 20;
19 PriorityQueue<TestComparator> pq1 = newPriorityQueue<TestComparator>(initCapacity,
20 newComparator<TestComparator>() {
21 publicintcompare(TestComparator t1, TestComparator t2) {
22 returnt1.getID() - t2.getID();
23 }
24 });
25 pq1.offer(newTestComparator(1));
26 pq1.offer(newTestComparator(6));
27 pq1.offer(newTestComparator(4));
28 pq1.offer(newTestComparator(5));
29 pq1.offer(newTestComparator(3));
30 pq1.offer(newTestComparator(2));
31 pq1.offer(newTestComparator(7));
32 System.out.println("The following is for TestComparator.");
33 System.out.println(pq1);
34 while(pq1.peek() != null) {
35 intid = pq1.poll().getID();
36 System.out.println(id);
37 }
38 }
39 }
40
41 classTestComparator {
42 publicTestComparator(intid) {
43 _id = id;
44 }
45 publicintgetID() {
46 return_id;
47 }
48 publicString toString() {
49 returnInteger.toString(_id);
50 }
51 privateint_id;
52 }
9. HashMap：其内部数据结构的逻辑类似于HashSet，只是Map存储的都是key/value的键值映射关系，key相当于HashSet中的对象，value只是附着于key的对象，使用者一般都是通过key的值去HashMap中搜索，找到并返回该key以及相关联的value，其内部实现机制可参考HashSet。在接口方面主要的不同点是Map对象可以生成3个集合的视图(仅仅是视图，没有对象copy，视图的底层容器仍然来自于原映射对象集合，如果在其中任意视图或原集合删除和添加数据都会及时反应与其他视图和映射集合)。该规则同样适用于TreeMap。见以下常用代码示例：
1 publicstaticvoidshowGetAndPut() {
2 HashMap<String, Double> hm = newHashMap<String, Double>();
3 hm.put("A", newDouble(3.34));
4 hm.put("B", newDouble(1.22));
5 hm.put("C", newDouble(1.00));
6 hm.put("D", newDouble(9.22));
7 hm.put("E", newDouble(-19.08));
8 //随机的获取HashMap中的数据
9 Set<Map.Entry<String, Double>> set = hm.entrySet();
10 for(Map.Entry<String, Double> me : set) {
11 System.out.print(me.getKey() + ": ");
12 System.out.println(me.getValue());
13 }
14 doublebalance = hm.get("A");
15 //输出1003.34
16 hm.put("A", balance + 1000);
17 System.out.println(hm.get("A"));
18 }
19
20 publicstaticvoidshowContainsAndRemove() {
21 HashMap<String, String> hashMap = newHashMap<String, String>();
22 hashMap.put("1", "One");
23 hashMap.put("2", "Two");
24 hashMap.put("3", "Three");
25 System.out.println(hashMap.containsValue("Three"));
26 String str = hashMap.remove("2");
27 System.out.println("old value of 2 = " + str);
28 System.out.println(hashMap.containsValue("Two"));
29 Set<String> st = hashMap.keySet();
30 st.remove("1");
31 System.out.println("The size is equal to " + hashMap.size());
32 System.out.println(hashMap.containsKey("3"));
33 }
34 /* 结果如下
35 true
36 old value of 2 = Two
37 false
38 The size is equal to 1
39 true */
40
41 publicstaticvoidshowIterator() {
42 String names[] = { "Mercury", "Venus", "Earth", "Mars", "Jupiter"
43 , "Saturn", "Uranus", "Neptune", "Pluto" };
44 floatdiameters[] = { 4800f, 12103.6f, 12756.3f, 6794f, 142984f
45 , 120536f, 51118f, 49532f, 2274f };
46 Map<String,Float> map = newHashMap<String,Float>();
47 for(inti = 0, n = names.length; i < n; i++)
48 map.put(names[i], newFloat(diameters[i]));
49 Iterator<String> it = map.keySet().iterator();
50 while(it.hasNext()) {
51 String str = it.next();
52 System.out.println(str + ": " + map.get(str));
53 }
54 }
55
56 publicstaticvoidshowSynchronizedMap() {
57 TreeMap<String,String> treeMap = newTreeMap<String,String>();
58 Map<String,String> map = Collections.synchronizedMap(treeMap);
59 //Map之后的并发操作将不再需要synchronized关键字来进行同步了。
60 }
10. TreeMap：TreeMap和TreeSet之间的相似性和主要差异就像HashMap之于HashSet，见以下常用代码示例：
1 publicstaticvoidshowSubMapAndHeadMapAndTailMap() {
2 TreeMap<String, String> sortedMap = newTreeMap<String, String>();
3 sortedMap.put("Adobe", "Mountain View, CA");
4 sortedMap.put("IBM", "White Plains, NY");
5 sortedMap.put("Learning Tree", "Los Angeles, CA");
6 sortedMap.put("Microsoft", "Redmond, WA");
7 sortedMap.put("Netscape", "Mountain View, CA");
8 sortedMap.put("O'Reilly", "Sebastopol, CA");
9 sortedMap.put("Sun", "Mountain View, CA");
10 System.out.println(sortedMap);
11 //firstKey and lastKey 是SortedMap中提供的方法，HashMap中没有。
12 String low = sortedMap.firstKey(), high = sortedMap.lastKey();
13 System.out.println(low);
14 System.out.println(high);
15 Iterator<String> it = sortedMap.keySet().iterator();
16 inti = 0;
17 while(it.hasNext()) {
18 if(i == 3)
19 low = it.next();
20 if(i == 6)
21 high = it.next();
22 else
23 it.next();
24 i++;
25 }
26 System.out.println(low);
27 System.out.println(high);
28 //以下3个方法也是SortedMap中提供的方法，HashMap中没有。
29 System.out.println(sortedMap.subMap(low, high));
30 System.out.println(sortedMap.headMap(high));
31 System.out.println(sortedMap.tailMap(low));
32 }
11. LinkedHashSet和LinkedHashMap：这两个集合与HashSet和HashMap唯一的差异是LinkedHashSet和LinkedHashMap通过内部实现的双向链表保留了集合元素的插入顺序，见如下代码：
1 publicstaticvoidmain(String[] a) {
2 Map<String, String> map = newLinkedHashMap<String, String>();
3 map.put("1", "value1");
4 map.put("2", "value2");
5 map.put("3", "value3");
6 map.put("2", "value4");
7 for(Iterator<String> it = map.keySet().iterator(); it.hasNext();) {
8 String key = it.next();
9 String value = map.get(key);
10 System.out.println(value);
11 }
12 }
13 /* 结果如下：
14 value1
15 value4
16 value3 */
17
18 //基于Values的排序后输出Keys
19 publicstaticvoidmain(String[] a) {
20 Map<String, String> yourMap = newHashMap<String, String>();
21 yourMap.put("1", "one");
22 yourMap.put("2", "two");
23 yourMap.put("3", "three");
24
25 Map<String, String> map = newLinkedHashMap<String, String>();
26 List<String> keyList = newArrayList<String>(yourMap.keySet());
27 List<String> valueList = newArrayList<String>(yourMap.values());
28 Set<String> sortedSet = newTreeSet<String>(valueList);
29 String[] sortedArray = sortedSet.toArray(newString[0]);
30 intsize = sortedArray.length;
31
32 for(inti = 0; i < size; i++)
33 map.put(keyList.get(valueList.indexOf(sortedArray[i])), sortedArray[i]);
34
35 Set<String> ref = map.keySet();
36 Iterator<String> it = ref.iterator();
37 while(it.hasNext()) {
38 String i = (String) it.next();
39 System.out.println(i);
40 }
41 }
12. EnumSet和EnumMap，这两个集合可以看做是类型参数特化后的Set<E extends Enum<E>>和Map<E extends Enum<E>,V>，EnumSet没有显示的构造函数，而是通过一组工厂方法来创建了，见如下代码：
1 enumWeekdays {
2 Monday,Tuesday,Wednesday,Thursday,Friday,Saturday,Sunday
3 }
4 publicstaticvoidmain(String[] a) {
5 EnumSet<Weekdays> es1 = EnumSet.allOf(Weekdays.class);
6 EnumSet<Weekdays> es2 = EnumSet.noneOf(Weekdays.class);
7 EnumSet<Weekdays> es3 = EnumSet.range(Weekdays.Thursday, Weekdays.Sunday);
8 EnumSet<Weekdays> es4 = EnumSet.of(Weekdays.Monday,Weekdays.Saturday);
9 System.out.println("es1 = " + es1);
10 System.out.println("es2 = " + es2);
11 System.out.println("es3 = " + es3);
12 System.out.println("es4 = " + es4);
13 }
14 /* 结果如下：
15 es1 = [Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday]
16 es2 = []
17 es3 = [Thursday, Friday, Saturday, Sunday]
18 es4 = [Monday, Saturday] */
13. 集合视图：顾名思义，所有的集合视图和数据库中的普通视图一样，并不存储真实是的容器元素，而只是建立一套针对原有底层集合数据的引用机制，针对所有视图的操作或底层集合的操作都会同时相互影响，如插入和删除等，但是对于视图而言，插入操作如果作用于其范围之外将会引发异常。对于不同类别的视图其操作也存在不同的限制。
1). subList：获取底层集合中某一范围的元素，如List group2 = staff.asList(10,20); 这第一个索引上的数据是被包含的，第二个索引的数据是不被包含的。如果执行了group2.clear()操作情况了视图中的数据，那么staff中这段范围内的数据也会被连同删除。对于有序集合和映射表(Map)，可以使用排序顺序而不是元素位置建立子范围，如SortedSet接口声明的SortedSet<E> subSet(E from,E to); SortedSet<E> headSet(E to); SortedSet<E> tailSet(E from); 注意这3个参数的类型均不是元素的索引，而是对象本身。SortedMap中也有类似的方法，如SortedMap<K,V> subMap(K from,K to); SortedMap<K,V> headMap(K to); SortedMap<K> tailMap(K from)。在NavigableSet中提供更为丰富的接口，如NavigableSet<E> subSet(E from,boolean fromInclusive,E to,boolean toInclusive); NavigableSet<E> headSet(E to,boolean toInclusive); NavigableSet<E> tailSet(E from,boolean fromInclusive);
2). 不可修改的视图：
Collections.unModifiableCollection();
Collections.unModifiableList(); //用于ArrayList、LinkedList
Collections.unModifiableSet(); //用于HashSet、TreeSet、LinkedHashSet
Collections.unModifiableSortedSet();//用于TreeSet
Collections.unModifiableMap(); //用于HashMap、TreeMap、LinkedHashMap
Collections.unModifiableSortedMap();//用于TreeMap
如List<String> staff = new LinkedList<String>(); List<String> unmodifiableList = new Collections.unmodifiableList(staff); 这里unmodifiableList作为一个List对象，所有访问器的方法均可像普通List一样操作，但是对于更改器方法的调用将会引发UnsupportedOperationException异常。如果确实需要修改数据只能通过原始集合来完成。
3) 同步视图：
Collections.synchronizedList(); //用于ArrayList、LinkedList
Collections.synchronizedSet(); //用于HashSet、TreeSet、LinkedHashSet
Collections.synchronizedSortedMap();//用于TreeMap
Collections.synchronizedSortedSet();//用于TreeSet
Collections.synchronizedMap(); //用于HashMap、TreeMap、LinkedHashMap
之后所有通过同步视图访问底层集合的操作都将是线程安全的，即synchronized关键字就不需要在集合的外部添加了，但是对于底层集合的直接访问仍然是线程不安全。
4) 被检查视图：见以下两种情况，第一种情况将会在集合执行(String)rawList.get()操作时抛出ClassCastException异常，第一种情况则会在rawList.add()操作时就立即抛出ClassCastException。
1 publicvoiduncheckedListTest() {
2 ArrayList<String> strings = newArrayList<String>();
3 ArrayList rawList = strings;
4 rawList.add(newDate()); //no exception is raised here.
5 String ss = (String)rawList.get(0); //exception will be thrown here.
6 }
7
8 publicvoidcheckedListTest() {
9 ArrayList<String> strings = newArrayList<String>();
10 ArrayList<String> safeStrings = Collections.checkedList(strings,String.class);
11 ArrayList rawList = safeStrings;
12 rawList.add(newDate()); //exception will be thrown here.
13 }
注：从集合框架的整体设计技巧、扩展性、效率等方面综合比较，Java在此方面和C++的stl相比还是存在一定的差距。特别是扩展性和效率方面，C++的标准库定义了更多更灵活的模参扩展。由于标准库都是通过模板的方式实现的，因此其执行效率要明显优于基于虚函数的虚指针和虚表的这种动态绑定的多态方式，其不足只是编译速度稍微慢罢了。
14. 算法：
在C++中提供了一套泛型算法，主要涵盖排序、搜索和比较等通用操作，由于这些泛型算法完全基于各种集合提供的迭代器(iterator)统一接口，因此可以达到一种高度的泛型操作，以及算法函数和集合之间的完全松耦合。见如下C++代码：
1 #include <algorithm>
2 #include <set>
3 #include <vector>
4 usingnamespacestd;
5 intmain()
6 {
7 vector<int> v1;
8 for(inti = 0; i < 10; ++i)
9 v1.push_back(i);
10 set<int> s1;
11 for(inti = 0; i < 20; ++i)
12 s1.insert(i);
13 sort(v1.begin(),v1.end());
14 binary_search(v1.begin(),v1.end(),5);
15 binary_search(s1.begin(),s1.end(),5);
16 return0;
17 }
在Java中同样提供了这样的泛型算法，不同的是这些算法函数都是Collections中静态方法。见如下Java代码：
1 publicstaticvoidmain(String[] args) {
2 List<Integer> v1 = newArrayList<Integer>();
3 for(inti = 0; i < 10; ++i)
4 v1.add(i);
5
6 List<Integer> l1 = newLinkedList<Integer>();
7 for(inti = 0; i < 20; ++i)
8 l1.add(i);
9
10 Collections.sort(v1);
11 Collections.sort(l1);
12 Collections.binarySearch(v1, 5);
13 Collections.binarySearch(l1, 5);
14 }
- 文章
- 推荐
- 热门新闻