11.1 Lists and Sets
11.1.1 List
之前来说我们已经做好了 ALists
和 SLList
但是我们现在讲用 java 已经内置的 List interface 和 ArrayList
import java.util.List;
import java.util.ArrayList;
public class SimpleBuiltInListExample {
public static void main(String[] args) {
List<Integer> L = new ArrayList<>();
L.add(5);
L.add(10);
L.add(15);
System.out.println(L);
}
}
11.1.2 Set
Set<String> S = new HashSet<>();
S.add("Tokyo");
S.add("Beijing");
S.add("Lagos");
S.add("São Paulo");
System.out.println(S.contains("Tokyo"));
s = set()
s.add("Tokyo")
s.add("Beijing")
s.add("Lagos")
s.add("São Paulo")
print("Tokyo" in s)
11.2 Exceptions
package lec11_inheritance4;
public class CopyArraySet<T> {
private T[] items;
private int size; // the next item to be added will be at position size
public CopyArraySet(){
items = (T[])new Object[100];
size = 0;
}
public boolean contains(T x) {
for (int i = 0; i < size; i++) {
if (items[i].equals(x)) {
// 注意这里需要写的是 .equals() 而不是 ==
// why : use == operators for reference comparison (address comparison)
// and .equals() method for content comparison.
// In simple words, == checks if both objects point to the same memory location
// whereas .equals() evaluates to the comparison of values in the objects.
return true;
}
}
return false;
}
public void add(T x){
if(contains(x)) return;
items[size] = x;
size++;
}
public int size(){
return size;
}
public static void main(String[] args) {
CopyArraySet<String> set = new CopyArraySet<>();
set.add(null);
set.add("horse");
set.add(null);
set.add("cat");
set.add("dog");
System.out.println(set.contains("cat"));
System.out.println(set.size);
}
}
public void add(T x){
if (x == null) {
throw new IllegalArgumentException("null");
}
if(contains(x)) return;
items[size] = x;
size++;
}
11.3 Iteration
public static void main(String[] args) {
CopyArraySet<Integer> set = new CopyArraySet<>();
set.add(1);
set.add(7);
set.add(42);
Set<Integer> set2 = new HashSet<>();
set2.add(1);
set2.add(7);
set2.add(42);
for ( int i :set2){
System.out.println(i);
}
}
然而我们尝试用 set
来整活:
java: for-each 不适用于表达式类型
要求: 数组或 java.lang.Iterable
找到: lec11_inheritance4.CopyArraySet<java.lang.Integer>
所以我们拆解 for-each :
Set<Integer> javaset =
new HashSet<Integer>();
...
for (int x : javaset) {
System.out.println(x);
}
Set<Integer> javaset =
new HashSet<Integer>();
...
Iterator<Integer> seer
= javaset.iterator();
while (seer.hasNext()) {
System.out.println(seer.next());
}
那么问题来了:
The secret: The code on the left is just shorthand for the code on the right. For code on right to compile, which checks does the compiler need to do?
- Does the Set interface have an iterator() method?
- Does the Set interface have next/hasNext() methods?
- Does the Iterator interface have an iterator method?
- Does the Iterator interface have next/hasNext() methods?
所以我们要想支持这样的代码,需要
- Add an iterator() method to ArraySet that returns an Iterator.
- The Iterator that we return should have a useful hasNext() and next() method.
public Iterator<T> iterator(){
return new CopyArraySetIterator();
}
private class CopyArraySetIterator implements Iterator<T>{
private int Pos;
public CopyArraySetIterator(){
Pos = 0;
}
public boolean hasNext(){
return Pos < size;
}
public T next(){
T res = items[Pos];
Pos++;
return res;
}
}
然而此时
for(int i: set){
System.out.println(i);
}
依然是无法执行的,这时候需要
public class CopyArraySet<T> implements Iterable<T>{
11.4 toString and Equals
所谓 : ”All classes are hyponyms of Object.“:
- String toString()
- boolean equals(Object obj)
- Class getClass()
- int hashCode()
- protected Object clone()
- protected void finalize()
- void notify()
- void notifyAll()
- void wait()
- void wait(long timeout)
- void wait(long timeout, int nanos)
11.4.1 toSting
The toString() method provides a string representation of an object.
为了达成以下的结果
Set<Integer> javaset = new HashSet<>();
javaset.add(5);
javaset.add(23);
javaset.add(42);
System.out.println(javaset);
$ java JavaSetPrintDemo
[5, 23, 42]
得加钱,得加重载方法:
@Override
public String toString(){
String returnString ="{";
for(T item: this){
returnString += item.toString();
returnString += ", ";
}
returnString += "}";
return returnString;
}
{1, 7, 42, }
然而执行结果并不如人意,得改:
@Override
public String toString(){
String returnString ="{";
for(int i = 0; i < size-1; i++){
returnString += items[i].toString();
returnString += ", ";
}
returnString += items[size-1].toString();
returnString += "}";
return returnString;
}
{1, 7, 42}
虽然成功,但是这样会非常缓慢(String 会不停的创建),所以我们可以使用 StringBuilder
:
@Override
public String toString(){
StringBuilder returnString = new StringBuilder("{");
for(int i = 0; i < size-1; i++){
returnString.append(items[i].toString());
returnString.append(", ");
}
returnString.append(items[size - 1].toString());
returnString.append("}");
return returnString.toString();
}
11.4.2 Equals
关于 Equals 和 ==
- == compares the bits. For references, == means “referencing the same object.”
@Override
public boolean equals(Object other){ // 注意 是 Object 而不是 CopyArraySet<T>
if(this == other) return true;
if(other == null) return false;
if(other.getClass() != this.getClass()) return false;
CopyArraySet o = (CopyArraySet<T>) other;
if(o.size() != size) return false;
for(T item : this){
if(!o.contains(item)) return false;
}
return true;
}
11.5 扩展 改进方法
11.5.1 改进 toSting
@Override
public String toString() {
List<String> listOfItems = new ArrayList<>();
for(T x : this){
listOfItems.add(x.toString());
}
return "{"+String.join(",",listOfItems)+"}";
}
11.5.2 of()
public static <Glerp> CopyArraySet<Glerp> of(Glerp... stuff){
CopyArraySet<Glerp> returnset = new CopyArraySet<>();
for(Glerp x : stuff){
returnset.add(x);
}
return returnset;
}
CopyArraySet<String> set1 = CopyArraySet.of("a", "b", "c");