第11章持有对象

1.向上转型也可作用于泛型（当指定了某个确切类型作为类型参数时，不仅可以使用该确切类型，还可以使用该类型的子类类型）

2.容器分为Collection和Map两大类

（1）Collection，是一个元素序列，这些元素都服从一条或多条规则。list必须按照插入的顺序保存元素，Set不能有重复元素
（2）Map，表示一组成对的“键值对”对象。

3.所有的Collection都可以用foreach语法遍历；

4.迭代器，它是一个对象，它的工作是遍历并选择序列中的对象。而且它是个轻量级的对象，创建它的代价比较小。

5.java的Iterator只能单向移动，它的功能：

  (1).使用方法Iterator()要求容器返回一个Iterator对象。
  (2).next()方法获取序列中的下一个元素。


java.util.Iterator接口的相关方法
public interface Iterator<E>
1)
next

E next()

    Returns the next element in the iteration. Calling this method repeatedly until the hasNext() method returns false will return each

element in the underlying collection exactly once.

    Returns:
        the next element in the iteration.

2)
hasNext

boolean hasNext()

    Returns true if the iteration has more elements. (In other words, returns true if next would return an element rather than throwing

an exception.)

    Returns:
        true if the iterator has more elements.
3)
remove

void remove()

    Removes from the underlying collection the last element returned by the iterator (optional operation). This method can be called

only once per call to next. The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is

in progress in any way other than by calling this method.
注意：这个删除方法最终会删除产生此迭代对象的容器中的对象。


6.
public class CrossContainerIteration {
public static void display(Iterator<Pet> it) {
while (it.hasNext()) {
Pet p = it.next();
System.out.print(p.id() + ":" + p + " ");
}
System.out.println();
}

public static void main(String[] args) {
ArrayList<Pet> pets = Pets.arrayList(8);
LinkedList<Pet> petsLL = new LinkedList<Pet>(pets);
HashSet<Pet> petsHS = new HashSet<Pet>(pets);
TreeSet<Pet> petsTS = new TreeSet<Pet>(pets);
display(pets.iterator());
display(petsLL.iterator());
display(petsHS.iterator());
display(petsTS.iterator());
}
}

从上面的例子可以看到，display方法不包含任何有关它所遍历的序列的类型信息，这展示了Iterator的真正威力：能够建遍历序列的操作与序列底层的结构分离。迭代器统一了对容器的访问方式。

7.ListIterator是一个更加强大的Iterator的子类型，它只能用于各种List类的访问。普通的Iterator只能向前移动，但是ListIterator可以双向移动。
import java.util.List;
import java.util.ListIterator;

public class ListIteration {
public static void main(String[] args) {
List<Pet> pets = Pets.arrayList(8);
ListIterator<Pet> it = pets.listIterator();
while(it.hasNext()){
System.out.print(it.next()+",");
}
    System.out.println();
it = pets.listIterator(3);
while(it.hasNext()){
System.out.print(it.next()+",");
}
System.out.println();
while(it.hasPrevious()){
System.out.print(it.previous()+",");
}
System.out.println();
while (it.hasNext()) {
it.next();
    it.set(new Pug());
}
System.out.println(pets);
}
}
//outputs下面有相关方法的使用介绍
Rat,Manx,Cymric,Mutt,Pug,Cymric,Pug,Manx,
Mutt,Pug,Cymric,Pug,Manx,
Manx,Pug,Cymric,Pug,Mutt,Cymric,Manx,Rat,
[Pug, Pug, Pug, Pug, Pug, Pug, Pug, Pug]
对迭代器的操作，最终会影响到产生此迭代器的容器

接口
public interface ListIterator<E>
extends Iterator<E>

An iterator for lists that allows the programmer to traverse the list in either direction, modify the list during iteration, and obtain

the iterator's current position in the list. A ListIterator has no current element; its cursor position always lies between the element

that would be returned by a call to previous() and the element that would be returned by a call to next(). In a list of length n, there

are n+1 valid index values, from 0 to n, inclusive.

          Element(0)   Element(1)   Element(2)   ... Element(n)  
        ^            ^            ^            ^               ^
Index: 0            1            2            3               n+1
相关方法：
1）hasNext

boolean hasNext()

    Returns true if this list iterator has more elements when traversing the list in the forward direction. (In other words, returns

true if next would return an element rather than throwing an exception.)
2）next

E next()

    Returns the next element in the list. This method may be called repeatedly to iterate through the list, or intermixed with calls to

previous to go back and forth. (Note that alternating calls to next and previous will return the same element repeatedly.)

3）
hasPrevious

boolean hasPrevious()

    Returns true if this list iterator has more elements when traversing the list in the reverse direction. (In other words, returns

true if previous would return an element rather than throwing an exception.)
4）previous

E previous()

    Returns the previous element in the list. This method may be called repeatedly to iterate through the list backwards, or intermixed

with calls to next to go back and forth. (Note that alternating calls to next and previous will return the same element repeatedly.)

    Returns:
        the previous element in the list.
5）nextIndex

int nextIndex()

    Returns the index of the element that would be returned by a subsequent call to next. (Returns list size if the list iterator is at

the end of the list.)

    Returns:
        the index of the element that would be returned by a subsequent call to next, or list size if list iterator is at end of list.

6）previousIndex

int previousIndex()

    Returns the index of the element that would be returned by a subsequent call to previous. (Returns -1 if the list iterator is at the

beginning of the list.)

7)set

void set(E o)

    Replaces the last element returned by next or previous with the specified element (optional operation). This call can be made only

if neither ListIterator.remove nor ListIterator.add have been called after the last call to next or previous.

    Parameters:
        o - the element with which to replace the last element returned by next or previous.


8.java.util.List接口的方法
listIterator

ListIterator<E> listIterator(int index)

    Returns a list iterator of the elements in this list (in proper sequence), starting at the specified position in this list. The

specified index indicates the first element that would be returned by an initial call to the next method. An initial call to the

previous method would return the element with the specified index minus one.

Parameters:
    index - index of first element to be returned from the list iterator (by a call to the next method).

Returns:
    a list iterator of the elements in this list (in proper sequence), starting at the specified position in this list.

9.List接口在Collection接口的基础上添加了大量的方法，有两种基本类型的List

1）ArrayList，擅长于随机访问元素，但是插入、删除较慢；
2）LinkedList,擅长于插入、删除元素，随机访问比较慢；

10.LinkedList还添加了可以使其用作栈、队列或双端队列的方法，例如：

该类相关方法说明：
1）getFirst

public E getFirst()

    Returns the first element in this list.

    Returns:
        the first element in this list
2）element

public E element()

    Retrieves, but does not remove, the head (first element) of this list.

    Returns:
        the head of this queue.
3）peek

public E peek()

    Retrieves, but does not remove, the head (first element) of this list.

    Returns:
        the head of this queue, or null if this queue is empty.
4）remove

public E remove(int index)

    Removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts one from their

indices). Returns the element that was removed from the list.
Parameters:
    index - the index of the element to removed.
Returns:
    the element previously at the specified position.
5）removeFirst

public E removeFirst()

    Removes and returns the first element from this list.

    Returns:
        the first element from this list.
6）poll

public E poll()

    Retrieves and removes the head (first element) of this list.
Returns:
    the head of this queue, or null if this queue is empty.
7）offer

public boolean offer(E o)

    Adds the specified element as the tail (last element) of this list.

    Parameters:
        o - the element to add.
    Returns:
        true (as per the general contract of Queue.offer)
8）addLast

public void addLast(E o)

    Appends the given element to the end of this list. (Identical in function to the add method; included only for consistency.)

    Parameters:
        o - the element to be inserted at the end of this list.

9）removeLast

public E removeLast()

    Removes and returns the last element from this list.

    Returns:
        the last element from this list.

11.用linkedlist实现栈
public class Stack<T> {
  private LinkedList<T> storage = new LinkedList<T>();
  public void push(T v) { storage.addFirst(v); }
  public T peek() { return storage.getFirst(); }
  public T pop() { return storage.removeFirst(); }
  public boolean empty() { return storage.isEmpty(); }
  public String toString() { return storage.toString(); }
}
这里最后不要使用继承，这样会产生具有LinkedList行为的类，还是用组合比较好。
尽管已经有java.util.Stack，但是LinkedList可以产生更好的Stack，首先使用LinkedList实现的Stack。

12.Set不保存重复的元素。因此，可以很容易地询问某个元素是否在Set中。正因为这样，查找就成了Set中最重要的操作。而HashSet对快速查找进行了优化。Set根Collection具有完全一样的接口，因此没有任何额外的功能

13.如果想对结果进行排序，可以使用TreeSet而不是HashSet，例如：
public class SortedSetOfInteger {
  public static void main(String[] args) {
    Random rand = new Random(47);
    SortedSet<Integer> intset = new TreeSet<Integer>();
    for(int i = 0; i < 10000; i++)
      intset.add(rand.nextInt(30));
    System.out.println(intset);
  }

java.util.Set接口的相关方法：
1）contains

boolean contains(Object o)

    Returns true if this set contains the specified element. More formally, returns true if and only if this set contains an element e

such that (o==null ? e==null : o.equals(e)).
Parameters:
    o - element whose presence in this set is to be tested.
Returns:
    true if this set contains the specified element.
2）containsAll

boolean containsAll(Collection<?> c)

    Returns true if this set contains all of the elements of the specified collection. If the specified collection is also a set, this

method returns true if it is a subset of this set.

3）removeAll

boolean removeAll(Collection<?> c)

    Removes from this set all of its elements that are contained in the specified collection (optional operation). If the specified

collection is also a set, this operation effectively modifies this set so that its value is the asymmetric set difference of the two

sets.
4）addAll

boolean addAll(Collection<? extends E> c)

    Adds all of the elements in the specified collection to this set if they're not already present (optional operation). If the

specified collection is also a set, the addAll operation effectively modifies this set so that its value is the union of the two sets.

The behavior of this operation is unspecified if the specified collection is modified while the operation is in progress.

    Parameters:
        c - collection whose elements are to be added to this set.
    Returns:
        true if this set changed as a result of the call.

14.
Map可以将对象映射到其他对象上。下面的例子很容易地用Map将随机数产生的次数纪录了下来
public class Statistics {
public static void main(String[] args) {
Random rand = new Random(47);
Map<Integer, Integer> m = new HashMap<Integer, Integer>();
for (int i = 0; i < 10000; i++) {
// Produce a number between 0 and 20:
int r = rand.nextInt(20);
Integer freq = m.get(r);
m.put(r, freq == null ? 1 : freq + 1);
}
System.out.println(m);
}
}
map接口的相关方法：
1）get

V get(Object key)

    Returns the value to which this map maps the specified key. Returns null if the map contains no mapping for this key. A return value

of null does not necessarily indicate that the map contains no mapping for the key; it's also possible that the map explicitly maps the

key to null. The containsKey operation may be used to distinguish these two cases.

    More formally, if this map contains a mapping from a key k to a value v such that (key==null ? k==null : key.equals(k)), then this

method returns v; otherwise it returns null. (There can be at most one such mapping.)

    Parameters:
        key - key whose associated value is to be returned.
    Returns:
        the value to which this map maps the specified key, or null if the map contains no mapping for this key.
2）put

V put(K key,
      V value)

    Associates the specified value with the specified key in this map (optional operation). If the map previously contained a mapping

for this key, the old value is replaced by the specified value. (A map m is said to contain a mapping for a key k if and only if

m.containsKey(k) would return true.))

    Parameters:
        key - key with which the specified value is to be associated.
        value - value to be associated with the specified key.
    Returns:
        previous value associated with specified key, or null if there was no mapping for key. A null return can also indicate that the

map previously associated null with the specified key, if the implementation supports null values.


15.Map接口相关方法：
public class PetMap {
public static void main(String[] args) {
Map<String, Pet> petMap = new HashMap<String, Pet>();
petMap.put("My Cat", new Cat("Molly"));
petMap.put("My Dog", new Dog("Ginger"));
petMap.put("My Hamster", new Hamster("Bosco"));
System.out.println(petMap);
Pet dog = petMap.get("My Dog");
System.out.println(dog);
System.out.println(petMap.containsKey("My Dog"));
System.out.println(petMap.containsValue(dog));
}
}
1）containsKey

boolean containsKey(Object key)

    Returns true if this map contains a mapping for the specified key. More formally, returns true if and only if this map contains a

mapping for a key k such that (key==null ? k==null : key.equals(k)). (There can be at most one such mapping.)

    Parameters:
        key - key whose presence in this map is to be tested.
    Returns:
        true if this map contains a mapping for the specified key.

2）containsValue

boolean containsValue(Object value)

    Returns true if this map maps one or more keys to the specified value. More formally, returns true if and only if this map contains

at least one mapping to a value v such that (value==null ? v==null : value.equals(v)). This operation will probably require time linear

in the map size for most implementations of the Map interface.

    Parameters:
        value - value whose presence in this map is to be tested.
    Returns:
        true if this map maps one or more keys to the specified value.

16.Map的值可以是其他容器，甚至是其他Map值

public class MapOfList {
public static Map<Person, List<? extends Pet>> petPeople = new HashMap<Person, List<? extends Pet>>();
static {
petPeople.put(new Person("Dawn"), Arrays.asList(new Cymric("Molly"),
new Mutt("Spot")));
petPeople.put(new Person("Kate"), Arrays.asList(new Cat("Shackleton"),
new Cat("Elsie May"), new Dog("Margrett")));
petPeople.put(new Person("Marilyn"), Arrays.asList(new Pug(
"Louie aka Louis Snorkelstein Dupree"), new Cat(
"Stanford aka Stinky el Negro"), new Cat("Pinkola")));
petPeople.put(new Person("Luke"), Arrays.asList(new Rat("Fuzzy"),
new Rat("Fizzy")));
petPeople.put(new Person("Isaac"), Arrays.asList(new Rat("Freckly")));
}

public static void main(String[] args) {
System.out.println("People: " + petPeople.keySet());
System.out.println("Pets: " + petPeople.values());
for (Person person : petPeople.keySet()) {
System.out.println(person + " has:");
for (Pet pet : petPeople.get(person))
System.out.println("    " + pet);
}
}
}
相关方法：
1）keySet

Set<K> keySet()

    Returns a set view of the keys contained in this map. The set is backed by the map, so changes to the map are reflected in the set,

and vice-versa. If the map is modified while an iteration over the set is in progress (except through the iterator's own remove

operation), the results of the iteration are undefined. The set supports element removal, which removes the corresponding mapping from

the map, via the Iterator.remove, Set.remove, removeAll retainAll, and clear operations. It does not support the add or addAll

operations.

    Returns:
        a set view of the keys contained in this map.
2）values

Collection<V> values()

    Returns a collection view of the values contained in this map. The collection is backed by the map, so changes to the map are

reflected in the collection, and vice-versa. If the map is modified while an iteration over the collection is in progress (except

through the iterator's own remove operation), the results of the iteration are undefined. The collection supports element removal, which

removes the corresponding mapping from the map, via the Iterator.remove, Collection.remove, removeAll, retainAll and clear operations.

It does not support the add or addAll operations.

    Returns:
        a collection view of the values contained in this map.


17.
public class MapOfList {
public static Map<String, String> petPeople = new HashMap<String, String>();
static {
petPeople.put("1","Dawn");
petPeople.put("2","Kate");
petPeople.put("3","Marilyn");

}

public static void main(String[] args) {
System.out.println("People: " + petPeople.keySet());
System.out.println("Pets: " + petPeople.values());
Set<Map.Entry<String, String>> s=petPeople.entrySet();
System.out.println(s);


}
}
Map可以返回它的键的Set,它的值的Collection，或者它的键值对的Set

Map.entrySet()返回的是 Map.Entry<K,V>的集合。Map.Entry本身不是Collection。java.util.Map.Entry接口主要就是在遍历map的时候用到。

18.队列是一个先进先出的容器。LinkedList实现了Queue接口因此它可以用作Queue的一种实现，例如：
public class QueueDemo {
public static void printQ(Queue queue) {
while (queue.peek() != null)
System.out.print(queue.remove() + " ");
System.out.println();
}

public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<Integer>();
Random rand = new Random(47);
for (int i = 0; i < 10; i++)
queue.offer(rand.nextInt(i + 10));
printQ(queue);
Queue<Character> qc = new LinkedList<Character>();
for (char c : "Brontosaurus".toCharArray())
qc.offer(c);
printQ(qc);
}
}

19.优先级队列声明下一个弹出元素是最需要的元素（具有最高的优先级）。