Position and overview in the system of Collection

TreeSet inherits AbstractSet class and implements NavigableSet, Serializable, Cloneable, RandomAccess interfaces. It is characterized by unique, unordered storage elements (input and output unordered). TreeSet is implemented based on TreeMap by default and encapsulates TreeMap. By default, as with TreeMap, the compareTo method Comparable, the internal comparator of elements, is used to compare the size of elements. If you don’t use an internal Comparator, you pass in an implementation class of the Comparator externally to compare. Because the TreeMap implementation uses red-black tree implementation, the time complexity of the Add, Remove, and CONTAINS methods guarantees log(n) in the worst case.

Member variables

Private TRANSIENT NavigableMap<E,Object> m; private transient NavigableMap<E,Object> m; Dummy value to associate with an Object in the backing Map // Dummy value to associate with an Object in the backing Map Private static final Object PRESENT = New Object();Copy the code

3. Construction method

TreeSet(NavigableMap<E,Object> m) {this.m = m; } public TreeSet() {this(new TreeMap<E,Object>()); } // Create a new TreeMap in custom sort, // create a TreeSet based on the TreeSet, // use the TreeMap key to save the Set element. super E> comparator) { this(new TreeMap<>(comparator)); } public TreeSet(Collection<? Extends E> c) {// Creates a TreeSet with TreeMap to hold the collection element this(); // addAll elements from Collection c to TreeSet; } public TreeSet(SortedSet<E> s) {public TreeSet(SortedSet<E> s) {public TreeSet(SortedSet<E> s) { // addAll elements of SortedSet s to TreeSet; }Copy the code

This involves the addAll method:

Public Boolean addAll(Collection<? Extends E> c) {// Use linear-time version if applicable If (m.size()==0 && c.size() > 0 && c instanceof SortedSet && m instanceof TreeMap) { SortedSet<? extends E> set = (SortedSet<? extends E>) c; TreeMap<E,Object> map = (TreeMap<E, Object>) m; Comparator<? > cc = set.comparator(); // Get the Comparator<? super E> mc = map.comparator(); / / get the comparator if (cc = = MC | | (cc! = null && cc.equals(MC))) {// If the set comparator is the same as the parameter set comparator map.addAllForTreeSet(set, PRESENT); // Use TreeMap's addAllForTreeSet method to add all elements of the parameter set to this set. Return true; } } return super.addAll(c); // AbstractCollection superclass addAll method to add}Copy the code

It involves the addAllForTreeSet method for TreeMap. Check out my previous blog.

4. Common APIS

1. Add elements

Public Boolean add(E E) {// Call TreeMap put method add return m.put(E, PRESENT)==null; } public Boolean addAll(Collection<? Extends E> c) {// Use linear-time version if applicable If (m.size()==0 && c.size() > 0 && c instanceof SortedSet && m instanceof TreeMap) { SortedSet<? extends E> set = (SortedSet<? extends E>) c; TreeMap<E,Object> map = (TreeMap<E, Object>) m; Comparator<? > cc = set.comparator(); // Get the Comparator<? super E> mc = map.comparator(); / / get the comparator if (cc = = MC | | (cc! = null && cc.equals(MC))) {// If the set comparator is the same as the parameter set comparator map.addAllForTreeSet(set, PRESENT); // Use TreeMap's addAllForTreeSet method to add all elements of the parameter set to this set. Return true; } } return super.addAll(c); // AbstractCollection superclass addAll method to add}Copy the code

2. Delete elements

Public void clear() {// call TreeMap to clear m.clear(); } public Boolean remove(Object o) {return m.emove (o)==PRESENT; }Copy the code

3. Traversal operations

Public Iterator<E> Iterator () {// Call TreeMap to clear return m.avigableKeySet ().iterator(); }Copy the code

Five, the summary

TreeSet source code has few methods, because it is the wrapper object of TreeMap. I won’t go into the details here.