Description:

We’ll continue with the second collection of Dart syntax. Although collections were covered pretty well in the first article, we’ll cover collections in Dart more fully in this article, since we’ve just covered lists, sets, maps in Dart: Core packages, The dart: Collection package is also available in dart. If you have seen the source code of the dart: Core package, you will know that the dart: Collection package is actually delegated to the DART: Collection package, so I will try to connect the two from a source perspective. Of course, only a few commonly used collections will be selected here.

A, List

The List collection in DART is a collection of indexable objects with length that does not delegate to the collection implementation in the DART: Collection package and is implemented entirely internally.

  • Initialize the

    
main() {
      // Initializer 1: directly use the [] form to initialize
      List<String> colorList1 = ['red'.'yellow'.'blue'.'green'];

      Var + generics
      var colorList2 = <String> ['red'.'yellow'.'blue'.'green'];

      // Initialize the set of fixed length
      List<String> colorList3 = List(4);// initialize the set with size 4,
      colorList3.add('deepOrange');// Note: Once the collection length is specified, the add method Cannot be called, otherwise Cannot add to a fixed-length list will be thrown. It's also easy to understand because a set of fixed length can't be extended any further.
     print(colorList3[2]);// all four elements are initialized with null by default

     // Initialize four: initialize an empty set of variable length
     List<String> colorList4 = List(a);List
        
          colorList4 = []
        
     colorList4[2] = 'white';[]= is an operator overload that changes the element whose index is 2 to white, but whose length is 0 so it can't find the element whose index is 2, so an IndexOutOfRangeException is thrown

}
Copy the code

  • traverse

    main() {
      List<String> colorList = ['red'.'yellow'.'blue'.'green'];
      / / for the -i traversal
      for(var i = 0; i < colorList.length; i++) {// You can use var or int
          print(colorList[i]);        
      }
      / / forEach traversal
      colorList.forEach((color) => print(color));//forEach takes the argument Function. => using the arrow Function
      / / the for - the in traverse
      for(var color in colorList) {
          print(color);
      }
      // While +iterator iterates, similar to Java's iteator
      while(colorList.iterator.moveNext()) {
          print(colorList.iterator.current); }}Copy the code

  • Common functions

    main() {
      List<String> colorList = ['red'.'yellow'.'blue'.'green'];
      colorList.add('white');// Like Kotlin, add a new element
      List<String> newColorList = ['white'.'black'];
      colorList.addAll(newColorList);//addAll adds batch elements
      print(colorList[2]);// Like Kotlin, you can access elements directly using array subscripts
      print(colorList.length);// Get the length of the set. Kotlin is different. Kotlin uses size
      colorList.insert(1.'black');// Inserts the specified element at the specified index position in the collection
      colorList.removeAt(2);// Remove the element specified by index=2, the third element
      colorList.clear();// Clear all elements
      print(colorList.sublist(1.3));// Intercepts subsets
      print(colorList.getRange(1.3));// Gets a range element in the collection
      print(colorList.join('< -- - >'));// Similar to the joinToString method in Kotlin, output: red<-- >yellow<-- >blue<-- >green
      print(colorList.isEmpty);
      print(colorList.contains('green'));    
}
Copy the code

  • Constructor source code analysis

    The List in DART has many constructors, a primary constructor and multiple named constructors. There is an optional length argument in the main constructor.

    external factory List([int length]);// The main constructor, passing the optional length argument, defaults to 0

external factory List.filled(int length, E fill, {bool growable = false});// the filled name constructor can only declare arrays of fixed length

external factory List.from(可迭代 elements, {bool growable = true});

factory List.of(可迭代<E> elements, {bool growable = true}) = >List<E>.from(elements, growable: growable);// Delegate to the list. from constructor

external factory List.unmodifiable(可迭代 elements);  
Copy the code

  • Exteranl keyword (interlude)

    Note: The problem is that you may be confused when you see the List source code. The constructor does not have a concrete implementation. I don’t know if I noticed the exteranl keyword. External-modified functions have a property that implements function declaration and implementation body separation. That should make sense, that the corresponding implementation is somewhere else. In fact, you can find it in DartSDK source code. List, for example, corresponds to SDK /sdk_nnbd/lib/_internal/ VM /lib/array_patch.dart, and the corresponding external implementation has an @patch annotation.

@patch
class List<E> {
  // Corresponds to the implementation of the List main constructor
  @patch
  factory List([int length]) native "List_new";Runtime /lib/array.cc runtime/lib/array.cc

 // This corresponds to the implementation of the list. filled constructor. Fill is the value of the element that needs to be filled, and growable is false by default
  @patch
  factory List.filled(int length, E fill, {bool growable: false{})var result = growable ? new _GrowableList<E>(length) : new _List<E>(length);// You can see that a _GrowableList is created if it is variable, otherwise an internal private _List is created
    if(fill ! =null) {// If the value of the fill element is not null, return the set of length filled with the value fill
      for (int i = 0; i < length; i++) { result[i] = fill; }}return result;// Return an empty set of the corresponding length
  }

 // Implements the list. from constructor, which adds the collection of Iterable to a new collection. Growable is true by default, and expands by default
  @patch
  factory List.from(可迭代 elements, {bool growable: true{})if (elements is EfficientLengthIterable<E>) {
      int length = elements.length;
      var list = growable ? new _GrowableList<E>(length) : new _List<E>(length);// If it is variable, a _GrowableList is created, otherwise an internal private _List is created
      if (length > 0) {
        // Create iterator only if necessary
        int i = 0;
        for (var element inelements) { list[i++] = element; }}return list;
    }

    // If elements is an Iterable
      
       , there is no need to type test each element
      
    // Because in general, if elements are Iterable
      
       , the type tests for each element are replaced with a single type test before the loop begins. But note: wait, I noticed that there is something wrong with the following source code, or my eyes are not good, if and else internal execution code.
      
    if (elements is 可迭代<E>) {
      Create a _GrowableList
      List<E> list = new _GrowableList<E>(0);
      // Iterate over elements to add each element back to _GrowableList
      for (E e in elements) {
        list.add(e);
      }
      // Return the list if the length is variable
      if (growable) return list;
      // otherwise calling makeListFixedLength makes the collection a fixed-length collection, actually calling the c++ implementation of the native layer
      return makeListFixedLength(list);
    } else {
      List<E> list = new _GrowableList<E>(0);
      for (E e in elements) {
        list.add(e);
      }
      if (growable) return list;
      returnmakeListFixedLength(list); }}// The corresponding implementation of the list. unmodifiable constructor
  @patch
  factory List.unmodifiable(可迭代 elements) {
    final result = new List<E>.from(elements, growable: false);
    // We use the list. from constructor to create a set of fixed length result
    returnmakeFixedListUnmodifiable(result); }... }Copy the code

Corresponding List. From SDK source code parsing

/ / SDK/lib / _internal/vm/lib/internal_patch makeListFixedLength of dart
@patch
List<T> makeListFixedLength<T>(List<T> growableList)
 native "Internal_makeListFixedLength";

/ / the runtime/lib/growable_array Internal_makeListFixedLength in cc
DEFINE_NATIVE_ENTRY(Internal_makeListFixedLength, 0.1) {
 GET_NON_NULL_NATIVE_ARGUMENT(GrowableObjectArray, array,
 arguments->NativeArgAt(0));
 return Array::MakeFixedLength(array, /* unique = */ true);// call the Array::MakeFixedLength C++ method to change it to a fixed-length collection
}

// Runtime /vm/object.cc Array::MakeFixedLength returns a RawArray
RawArray* Array::MakeFixedLength(const GrowableObjectArray& growable_array, boolunique) { ASSERT(! growable_array.IsNull()); Thread* thread = Thread::Current(); Zone* zone = thread->zone(); intptr_t used_len = growable_array.Length();// Take the generic type parameters and prepare to copy them
 const TypeArguments& type_arguments =
 TypeArguments::Handle(growable_array.GetTypeArguments());

 // If the set is empty
 if (used_len == 0) {
 // If type_arguments is empty, it is a native List with no generic type arguments
    if(type_arguments.IsNull() && ! unique) {// This is a collection of native List(no generic type arguments) and non-unique, returning an empty array
         return Object::empty_array().raw();
    }
 // Create a new empty array based on the generic type argument passed to List
    Heap::Space space = thread->IsMutatorThread() ? Heap::kNew : Heap::kOld;// Create a new memory space if it is a MutatorThread or reuse the old one
    Array& array = Array::Handle(zone, Array::New(0, space));// Create an empty array array
    array.SetTypeArguments(type_arguments);// Set the type parameters to get
    return array.raw();// Returns a new array of the same generic parameters
 }

 // If the collection is not empty, fetch the data array from growable_array and return a new array with data
 const Array& array = Array::Handle(zone, growable_array.data());
    ASSERT(array.IsArray());
    array.SetTypeArguments(type_arguments);// Set the type parameters to get
    Return growable_array to 0 and the internal data array to an empty array
    growable_array.SetLength(0);
    growable_array.SetData(Object::empty_array());
    // The Truncate method is called to Truncate the USED_len length
    array.Truncate(used_len);
    return array.raw();// Last return array.raw()
}
Copy the code

Iterate

is used for elements with no generic arguments, as well as for nonunique elements. For example, Iterate

is used for elements with no generic arguments, as well as for nonunique elements. If there is an empty set with generic parameters, a new empty set is created and returned with the original generic parameters; If it’s a non-empty set with generic parameters, it takes the data array, creates a new set that copies the original data and returns it with the original generic parameters, and then truncates the array to its original length.

  • Exteranl Function

The key is that it can implement declaration and implementation separation, so that it can reuse the same set of external API declaration, and then corresponding to multiple sets of multi-platform implementation, if interested in source partners will find the same API declaration in JS also have another set of implementation, Both dart for Web and DART for VM are apis that are transparent to upper-level developers.

Second, the Set

The Set Set in the DART: Core package is actually delegated to the LinkedHashSet in the DART: Collection. The difference between a Set and a List is that the elements in a Set cannot be repeated. False is returned for adding duplicate elements, indicating unsuccessful addition.

  • Set Initialization mode

    main() {
    Set<String> colorSet= {'red'.'yellow'.'blue'.'green'};// Initialize directly with the {} form
    var colorList = <String> {'red'.'yellow'.'blue'.'green'};
}
Copy the code

  • There is no API for calculating intersection, union, and complement of sets directly in Kotlin

    main() {
    var colorSet1 = {'red'.'yellow'.'blue'.'green'};
    var colorSet2 = {'black'.'yellow'.'blue'.'green'.'white'};
    print(colorSet1.intersection(colorSet2));// Intersection --> output: {'yellow', 'blue', 'green'}
    print(colorSet1.union(colorSet2));/ / and set - > output: {' black ', 'red', 'yellow', 'blue', 'green', 'white'}
    print(colorSet1.difference(colorSet2));// Complement --> output: {'red'}
}
Copy the code

  • Set traversal (same as List)

      main() {
    Set<String> colorSet = {'red'.'yellow'.'blue'.'green'};
    / / for the -i traversal
    for (var i = 0; i < colorSet.length; i++) {
      // You can use var or int
      print(colorSet[i]);
    }
    / / forEach traversal
    colorSet.forEach((color) => print(color)); //forEach takes the argument Function. => using the arrow Function
    / / the for - the in traverse
    for (var color in colorSet) {
      print(color);
    }
    // While +iterator iterates, similar to Java's iteator
    while (colorSet.iterator.moveNext()) {
      print(colorSet.iterator.current); }}Copy the code

  • Constructor source code analysis

    factory Set() = LinkedHashSet<E>; // The primary constructor delegates to the LinkedHashSet primary constructor
factory Set.identity() = LinkedHashSet<E>.identity; // The Set's named constructor identity delegates to the identity of LinkedHashSet
factory Set.from(可迭代 elements) = LinkedHashSet<E>.from;// Delegate the named constructor from Set to the from of LinkedHashSet
factory Set.of(可迭代<E> elements) = LinkedHashSet<E>.of;// The named constructor of Set delegates to the of of LinkedHashSet
Copy the code

  • Corresponding LinkedHashSet source code analysis, space is limited interested in in-depth study

    abstract class LinkedHashSet<E> implements Set<E> {
  // The LinkedHashSet main constructor declaration takes three function type parameters as optional arguments, again with exteranl implementation declaration and implementation separation, to find the corresponding @patch implementation
  external factory LinkedHashSet(
      {bool equals(E e1, E e2),
      int hashCode(E e),
      bool isValidKey(potentialKey)});

  //LinkedHashSet names the constructor from
  factory LinkedHashSet.from(可迭代 elements) {
  // Internally create a LinkedHashSet object directly
    LinkedHashSet<E> result = LinkedHashSet<E>();
    // Add elements traversal to the LinkedHashSet
    for (final element in elements) {
      result.add(element);
    }
    return result;
  }

  //LinkedHashSet names the constructor of, first creating a LinkedHashSet object and adding elements directly to elements through the addAll method via a cascading operation
  factory LinkedHashSet.of(可迭代<E> elements) => LinkedHashSet<E>().. addAll(elements);void forEach(void action(E element));

  Iterator<E> get iterator;
}
Copy the code

  • The corresponding SDK/lib / _internal/vm/lib/collection_patch. @ Patch in the dart LinkedHashSet

    @patch
class LinkedHashSet<E> {
  @patch
  factory LinkedHashSet(
      {bool equals(E e1, E e2),
      int hashCode(E e),
      bool isValidKey(potentialKey)}) {
    if (isValidKey == null) {
      if (hashCode == null) {
        if (equals == null) {
          return new _CompactLinkedHashSet<E>(); // All optional arguments are null and _CompactLinkedHashSet is created by default
        }
        hashCode = _defaultHashCode;
      } else {
        if (identical(identityHashCode, hashCode) &&
            identical(identical, equals)) {
          return new _CompactLinkedIdentityHashSet<E>();/ / create _CompactLinkedIdentityHashSet
        }
        equals ??= _defaultEquals;
      }
    } else{ hashCode ?? = _defaultHashCode; equals ?? = _defaultEquals; }return new _CompactLinkedCustomHashSet<E>(equals, hashCode, isValidKey);/ / optional parameters are identical, create _CompactLinkedCustomHashSet by default
  }

  @patch
  factory LinkedHashSet.identity() => new _CompactLinkedIdentityHashSet<E>();
}
Copy the code

Third, the Map

The collection of maps in the DART: Core package is actually delegated to the LinkedHashMap in the DART: Collection. A collection Map is similar to Kotlin in that it is stored as a key-value, and the keys in a Map object cannot be duplicated

  • Map initialization mode

    main() {
    Map<String.int> colorMap = {'white': 0xffffffff.'black':0xff000000};// Initialize with {key:value}
 var colorMap = <String.int> {'white': 0xffffffff.'black':0xff000000};
 var colorMap = Map<String.int> ();// Create an empty Map collection
 // This is actually equivalent to the following code, which will be explained in the source code
 var colorMap = LinkedHashMap<String.int> (); }Copy the code

  • Commonly used functions in Map

    main() {
    Map<String.int> colorMap = {'white': 0xffffffff.'black':0xff000000};
    print(colorMap.containsKey('green'));//false
    print(colorMap.containsValue(0xff000000));//true
    print(colorMap.keys.toList());//['white','black']
    print(colorMap.values.toList());//[0xffffffff, 0xff000000]
    colorMap['white'] = 0xfffff000;// Modify the element with the specified key
    colorMap.remove('black');// Remove the element with the specified key
}
Copy the code

  • Map traversal mode

    main() {
    Map<String.int> colorMap = {'white': 0xffffffff.'black':0xff000000};
    //for-each key-value
    colorMap.forEach((key, value) => print('color is $key, color value is $value'));
}
Copy the code

  • Map.fromIterables Converts a List collection to a Map

    main() {
    List<String> colorKeys = ['white'.'black'];
    List<int> colorValues = [0xffffffff.0xff000000];
    Map<String.int> colorMap = Map.fromIterables(colorKeys, colorValues);
}
Copy the code

  • Constructor source code analysis

    external factory Map(a);// The main constructor is delegated to an external @patch implementation, which is actually delegated to LinkedHashMap

factory Map.from(Map other) = LinkedHashMap<K, V>.from;// The Map's named constructor from delegates to the LinkedHashMap's from

factory Map.of(Map<K, V> other) = LinkedHashMap<K, V>.of;// The Map's named constructor of delegates to the of of LinkedHashMap

external factory Map.unmodifiable(Map other);// Unmodifiable constructor feeds into @patch

factory Map.identity() = LinkedHashMap<K, V>.identity;//Map's named constructor identity is implemented externally at @patch

factory Map.fromIterable(可迭代 iterable,
      {K key(element), V value(element)}) = LinkedHashMap<K, V>.fromIterable;// The Map's named constructor fromIterable delegates to LinkedHashMap's fromIterable

factory Map.fromIterables(可迭代<K> keys, 可迭代<V> values) =
      LinkedHashMap<K, V>.fromIterables;//Map's named constructor fromIterables delegates to LinkedHashMap's fromIterables
Copy the code

  • Corresponding LinkedHashMap constructor source analysis

    abstract class LinkedHashMap<K.V> implements Map<K.V> {
  // The main constructor is implemented externally by @patch
  external factory LinkedHashMap(
      {bool equals(K key1, K key2),
      int hashCode(K key),
      bool isValidKey(potentialKey)});

  //LinkedHashMap naming constructor identity is implemented externally at @patch
  external factory LinkedHashMap.identity();

  //LinkedHashMap's named constructor from
  factory LinkedHashMap.from(Map other) {
    Create a new LinkedHashMap object
    LinkedHashMap<K, V> result = LinkedHashMap<K, V>();
    // Iterate over the elements in Other and add to the new LinkedHashMap object
    other.forEach((k, v) {
      result[k] = v;
    });
    return result;
  }

  // The LinkedHashMap named constructor of creates a new LinkedHashMap object and adds maps to the new LinkedHashMap in batches by calling addAll in the cascading operator
  factory LinkedHashMap.of(Map<K, V> other) => LinkedHashMap<K, V>().. addAll(other);// The LinkedHashMap named constructor fromIterable takes two optional arguments, the iterable, the key, and the value
  factory LinkedHashMap.fromIterable(可迭代 iterable,
      {K key(element), V value(element)}) {
    / / create a new LinkedHashMap object, by the method of the static MapBase _fillMapWithMappedIterable, add elements to the new map
    LinkedHashMap<K, V> map = LinkedHashMap<K, V>();
    MapBase._fillMapWithMappedIterable(map, iterable, key, value);
    return map;
  }

  //LinkedHashMap's named constructor fromIterables
  factory LinkedHashMap.fromIterables(可迭代<K> keys, 可迭代<V> values) {
  // Create a new LinkedHashMap object and add elements to the new map using the static method _fillMapWithIterables in MapBase
    LinkedHashMap<K, V> map = LinkedHashMap<K, V>();
    MapBase._fillMapWithIterables(map, keys, values);
    returnmap; }}/ / the _fillMapWithMappedIterable MapBase
 static void _fillMapWithMappedIterable(
      Map map, 可迭代iterable, key(element), value(element)) { key ?? = _id; value ?? = _id;for (var element in iterable) {// Iterate over iterable and copy the mapmap[key(element)] = value(element); }}// _fillMapWithIterables in MapBase
  static void _fillMapWithIterables(Map map, 可迭代 keys, 可迭代 values) {
    Iterator keyIterator = keys.iterator;// Get keys iterator
    Iterator valueIterator = values.iterator;// Get values iterator

    bool hasNextKey = keyIterator.moveNext();// Is there a NextKey
    bool hasNextValue = valueIterator.moveNext();// Whether there is NextValue

    while (hasNextKey && hasNextValue) {// iterate over keys, values
      map[keyIterator.current] = valueIterator.current;
      hasNextKey = keyIterator.moveNext();
      hasNextValue = valueIterator.moveNext();
    }

    if (hasNextKey || hasNextValue) {// If only one of them is true, the length of the key and value are inconsistent, and an exception is thrown
      throw ArgumentError("Iterables do not have same length."); }}Copy the code

  • The @patch Map is implemented in SDK /lib/_internal/ VM /lib/map_patch.dart

    @patch
class Map<K.V> {
  @patch
  factory Map.unmodifiable(Map other) {
    return new UnmodifiableMapView<K, V>(new Map<K, V>.from(other));
  }

  @patch
  factory Map() = >new LinkedHashMap<K, V>(); LinkedHashMap
        ,>
}
Copy the code

Fourth, the Queue

Queue, as the name implies, is a fifO data structure. Dart also provides support for queues, which are actually implemented by delegation to ListQueue. Queue EfficientLengthIterable

interface, then EfficientLengthIterable

interface inherit Iterable

interface. This means that a Queue can use rich operation functions like a List. And from Queue comes DoubleLinkedQueue and ListQueue


  • Initialize the

    import 'dart:collection';// Note that Queue is in dart: Collection and needs to be guided

main() {
  // Initialize through the primary constructor
  var queueColors = Queue();
  queueColors.addFirst('red');
  queueColors.addLast('yellow');
  queueColors.add('blue');
  // Initialize with the from named constructor
  var queueColors2 = Queue.from(['red'.'yellow'.'blue']);
  // Initialize with the of named constructor
  var queueColors3 = Queue.of(['red'.'yellow'.'blue']);
}
Copy the code

  • Common functions

    import 'dart:collection';// Note that Queue is in dart: Collection and needs to be guided
main() {
 varqueueColors = Queue() .. addFirst('red')
 ..addLast('yellow')
 ..add('blue')
 ..addAll(['white'.'black'])
 ..remove('black')
 ..clear();
}
Copy the code

  • traverse

    import 'dart:collection'; // Note that Queue is in dart: Collection and needs to be guided

main() {
  Queue<String> colorQueue = Queue.from(['red'.'yellow'.'blue'.'green']);
  / / for the -i traversal
  for (var i = 0; i < colorQueue.length; i++) {
    // You can use var or int
    print(colorQueue.elementAt(i)); // Note: We do not use colorQueue[I] to get the elements in the Queue, because the [] operator is not overloaded inside the Queue
  }
  / / forEach traversal
  colorQueue.forEach((color) => print(color)); //forEach takes the argument Function. => using the arrow Function
  / / the for - the in traverse
  for (var color in colorQueue) {
    print(color); }}Copy the code

  • Constructor source code analysis

      factory Queue() = ListQueue<E>;// Delegate to the ListQueue
        
          main constructor
        

  factory Queue.from(可迭代 elements) = ListQueue<E>.from;// Delegate the named constructor from to ListQueue
        

  factory Queue.of(可迭代<E> elements) = ListQueue<E>.of;// Delegate to the named constructor of ListQueue
        
Copy the code

  • Corresponding ListQueue source analysis

    class ListQueue<E> extends ListIterable<E> implements Queue<E> {
  static const int _INITIAL_CAPACITY = 8;// The default queue initialization capacity is 8
  List<E? > _table;int _head;
  int _tail;
  int _modificationCount = 0;

  ListQueue([int? initialCapacity])
      : _head = 0,
        _tail = 0,
        _table = List<E? >(_calculateCapacity(initialCapacity));// It is interesting to see that ListQueque's internal implementation is a List
        
          set, E? A generic type is nullable, but dart's nullable feature is still experimental, but you can see it already in use in the source code.
        ?>

  // Calculate the capacity required by the queue
  static int _calculateCapacity(int? initialCapacity) {
    // if initialCapacity is null or the specified initialCapacity is smaller than the default capacity, the default capacity is used
    if (initialCapacity == null || initialCapacity < _INITIAL_CAPACITY) {

          return _INITIAL_CAPACITY;
    } else if(! _isPowerOf2(initialCapacity)) {// The capacity is not a power of 2
      return _nextPowerOf2(initialCapacity);// Find a number whose size is close to the 2nd power of number
    }
    assert(_isPowerOf2(initialCapacity));// Assertion check
    return initialCapacity;// initialCapacity is finally returned, which must be a power of 2
  }

  // Check whether the capacity is a power of 2
  static bool _isPowerOf2(int number) => (number & (number - 1)) = =0;

  // Find a number whose size is close to the second power of number
  static int _nextPowerOf2(int number) {
    assert(number > 0);
    number = (number << 1) - 1;
    for (;;) {
      int nextNumber = number & (number - 1);
      if (nextNumber == 0) returnnumber; number = nextNumber; }}// The named constructor of ListQueue from
  factory ListQueue.from(可迭代<dynamic> elements) {
    Elements is of type List
        
    if (elements is List<dynamic>) {
      int length = elements.length;// Retrieve the length
      ListQueue<E> queue = ListQueue<E>(length + 1);// Create a ListQueue with length + 1
      assert(queue._table.length > length);// The length of the newly created queue must be greater than the length of elements passed in
      for (int i = 0; i < length; i++) {
        queue._table[i] = elements[i] as E;// Then assign the elements in the new queue to the generic type E
      }
      queue._tail = length;// Finally move the tail subscript of the queue, because the actual length may be greater than the actual element length
      return queue;
    } else {
      int capacity = _INITIAL_CAPACITY;
      if (elements is EfficientLengthIterable) {// If the value is EfficientLengthIterable, then the elements length is EfficientLengthIterable
        capacity = elements.length;
      }
      ListQueue<E> result = ListQueue<E>(capacity);
      for (final element in elements) {
        result.addLast(element as E);// Insert from the end of the queue with addLast
      }
      return result;// Finally returns result}}// The named constructor of ListQueue
  factory ListQueue.of(可迭代<E> elements) => ListQueue<E>().. addAll(elements);// Create a new ListQueue
        
         () and add elements to the new ListQueue with addAll
        . }Copy the code

Fifth, LinkedList

The LinkedList is special in DART. It is not a generic set because the upper bound of its generic type is LinkedListEntry. The internal data structure implementation is a double-linked list whose nodes are subclasses of LinkedListEntry. And _next and _previous Pointers are maintained internally. It also does not implement the List interface

  • Initialize the

    import 'dart:collection'; // Note: LinkedList is located in the Dart: Collection package
main() {
  var linkedList = LinkedList<LinkedListEntryImpl<int> > ();var prevLinkedEntry = LinkedListEntryImpl<int> (99);
  var currentLinkedEntry = LinkedListEntryImpl<int> (100);
  var nextLinkedEntry = LinkedListEntryImpl<int> (101);
  linkedList.add(currentLinkedEntry);
  currentLinkedEntry.insertBefore(prevLinkedEntry);// Insert a new node before the current one
  currentLinkedEntry.insertAfter(nextLinkedEntry);// Insert a new node after the current one
  linkedList.forEach((entry) => print('${entry.value}'));
}

// You need to define a LinkedListEntry subclass
class LinkedListEntryImpl<T> extends LinkedListEntry<LinkedListEntryImpl<T>> {
  final T value;

  LinkedListEntryImpl(this.value);

  @override
  String toString() {
    return "value is $value"; }}Copy the code

  • Common functions

    currentLinkedEntry.insertBefore(prevLinkedEntry);// Insert a new node before the current one
currentLinkedEntry.insertAfter(nextLinkedEntry);// Insert a new node after the current one
currentLinkedEntry.previous;// Get the previous node of the current node
currentLinkedEntry.next;// Get the last node of the current node
currentLinkedEntry.list;/ / get LinkedList
currentLinkedEntry.unlink();// Delete the current entry from LinkedList
Copy the code

  • traverse

     / / forEach iteration
 linkedList.forEach((entry) => print('${entry.value}'));
 / / for the -i iteration
 for (var i = 0; i < linkedList.length; i++) {
     print('${linkedList.elementAt(i).value}');
 }
 / / the for - in the iteration
 for (var element in linkedList) {
     print('${element.value}');
 }
Copy the code

Six, HashMap

  • Initialize the

    import 'dart:collection'; // Note that HashMap is in dart: Collection and needs to be guided
main() {
  var hashMap = HashMap();// initialize via the HashMap primary constructor
  hashMap['a'] = 1;
  hashMap['b'] = 2;
  hashMap['c'] = 3;
  var hashMap2 = HashMap.from(hashMap);// Initialize by naming the constructor from with HashMap
  var hashMap3 = HashMap.of(hashMap);// Initialize with the HashMap named constructor of
  var keys = ['a'.'b'.'c'];
  var values = [1.2.3]
  var hashMap4 = HashMap.fromIterables(keys, values);// Initialize with the HashMap named constructor fromIterables

  hashMap2.forEach((key, value) => print('key: $key value: $value'));
}
Copy the code

  • Common functions

    import 'dart:collection'; // Note that HashMap is in dart: Collection and needs to be guided
main() {
   var hashMap = HashMap();// initialize via the HashMap primary constructor
   hashMap['a'] = 1;
   hashMap['b'] = 2;
   hashMap['c'] = 3;
   print(hashMap.containsKey('a'));//false
   print(hashMap.containsValue(2));//true
   print(hashMap.keys.toList());//['a','b','c']
   print(hashMap.values.toList());/ / [1, 2, 3]
   hashMap['a'] = 55;// Modify the element with the specified key
   hashMap.remove('b');// Remove the element with the specified key
}
Copy the code

  • traverse

    import 'dart:collection'; // Note that HashMap is in dart: Collection and needs to be guided
main() {
   var hashMap = HashMap();// initialize via the HashMap primary constructor
   hashMap['a'] = 1;
   hashMap['b'] = 2;
   hashMap['c'] = 3;
   //for-each key-value
   hashMap.forEach((key, value) => print('key is $key, value is $value'));
}
Copy the code

  • Constructor source code analysis

    // The main constructor is implemented externally by @patch
external factory HashMap(
      {bool equals(K key1, K key2),
      int hashCode(K key),
      bool isValidKey(potentialKey)});

// The HashMap naming constructor identity is implemented externally by @patch
external factory HashMap.identity();

//HashMap names the constructor from
factory HashMap.from(Map other) {
    Create a HashMap object
    Map<K, V> result = HashMap<K, V>();
    // Iterate over the Other collection and assign elements to the new HashMap object
    other.forEach((k, v) {
      result[k] = v;
    });
    return result;
 }

// The HashMap naming constructor of adds other to the newly created HashMap object
factory HashMap.of(Map<K, V> other) => HashMap<K, V>().. addAll(other);// The HashMap named constructor fromIterable
factory HashMap.fromIterable(可迭代 iterable,
      {K key(element), V value(element)}) {
    Map<K, V> map = HashMap<K, V>();Create a new HashMap object
    MapBase._fillMapWithMappedIterable(map, iterable, key, value);/ / by MapBase _fillMapWithMappedIterable assigned to new HashMap object
    return map;
}

//HashMap named constructor fromIterables
factory HashMap.fromIterables(可迭代<K> keys, 可迭代<V> values) {
    Map<K, V> map = HashMap<K, V>();Create a new HashMap object
    MapBase._fillMapWithIterables(map, keys, values);// Assign to the new HashMap object via _fillMapWithIterables in MapBase
    return map;
}
Copy the code

  • HashMap corresponding @ Patch source implementation, the SDK/lib / _internal/vm/lib/collection_patch dart

    @patch
class HashMap<K.V> {
  @patch
  factory HashMap(
      {bool equals(K key1, K key2),
      int hashCode(K key),
      bool isValidKey(potentialKey)}) {
    if (isValidKey == null) {
      if (hashCode == null) {
        if (equals == null) {
          return new _HashMap<K, V>();// Create private _HashMap objects
        }
        hashCode = _defaultHashCode;
      } else {
        if (identical(identityHashCode, hashCode) &&
            identical(identical, equals)) {
          return new _IdentityHashMap<K, V>();Create a private _IdentityHashMap object
        }
        equals ??= _defaultEquals;
      }
    } else{ hashCode ?? = _defaultHashCode; equals ?? = _defaultEquals; }return new _CustomHashMap<K, V>(equals, hashCode, isValidKey);// Create a private _CustomHashMap object
  }

  @patch
  factory HashMap.identity() => new _IdentityHashMap<K, V>();

  Set<K> _newKeySet();
}
Copy the code

7. Map, HashMap, LinkedHashMap, SplayTreeMap

There is also a SplayTreeMap in Dart that has similar initialization, common functions, and traversal to the use of LinkedHashMap and HashMap. But what’s the difference between a Map, a HashMap, a LinkedHashMap, and a SplayTreeMap?

  • Map

    A Map is a collection of key-value pairs. Each item in the Map in Dart can be iterated. The order of iteration depends on the implementation of HashMap, LinkedHashMap, or SplayTreeMap. If you create an instance using the Map constructor, a LinkedHashMap is created by default.

  • HashMap

    HashMap does not guarantee insertion order. If you insert an element with key A and then another element with key B, it is possible to get element B first when traversing the Map.

  • LinkedHashMap

    LinkedHashMap ensures insertion order. Sort the data stored in the LinkedHashMap by insertion order. If the element with key A is inserted first and then another element with key B is inserted, the Map is always iterated with the element with key A followed by the element with key B.

  • SplayTreeMap

    SplayTreeMap is a self-balancing binary tree that allows faster access to the most recently accessed elements. Basic operations such as insert, find, and delete can be done in order (log (n)) time complexity. It performs tree rotation by bringing frequently visited elements close to the root of the tree. Therefore, if you need to access certain elements more frequently, using SplayTreeMap is a good choice. However, using SplayTreeMap is not useful if all elements have nearly the same frequency of data access.

Naming constructors from and of

As you can see from the above collection source, almost every collection (List, Set, LinkedHashSet, LinkedHashMap, Map, HashMap, etc.) has from and of named constructors. Some people may have questions, what are the differences between them, their application scenarios. In fact, the answer is seen from the source code. For example, from and of in List,Map.

main() {
  var map = {'a': 1.'b': 2.'c': 3};
  var fromMap = Map.from(map); // Return type is Map
      ,>
  var ofMap = Map.of(map); // Return type is Map
      ,>

  var list = [1.2.3.4];
  var fromList = List.from(list); // The return type is List
      
  var ofList = List.of(list); // The return type is List
      
}
Copy the code

List

and Map

and the of function returns the corresponding set of generic types which are actually List

and Map

. We all know that Dynamic is an indeterminable type, which is not checked at compile time, but only checked at the runtime, whereas concrete types are checked at compile time. And as you can see from the source code, the FROM function tends to deal with more complex logic such as iterating through the incoming collection and adding elements to the new collection, whereas the OF function just creates a new object and adds elements to the incoming collection in bulk through the addAll function.
,>

;>

So here’s a tip for code efficiency: if you pass in an existing set element type, try to create a new set using the of function, otherwise consider using the FROM function.

conclusion

This concludes the second part of our DART syntax series. We believe that this article has given you a comprehensive understanding of dart collections. We will continue to study DART and Flutter.

My official account

Dart, Flutter and Kotlin are the latest articles on Flutter and their translations