Download Reference Manual
The Developer's Library for D
About Wiki Forums Source Search Contact

Changes between Version 34 and Version 35 of ChapterStorage

Show
Ignore:
Author:
keinfarbton (IP: 85.180.21.52)
Timestamp:
10/06/08 20:43:13 (15 years ago)
Comment:

start of container doc

Legend:

Unmodified
Added
Removed
Modified
  • ChapterStorage

    v34 v35  
    11[[TOC()]] 
    2 = The collection classes = 
    3 Tango provides a number of collection classes, sometimes also called container classes. 
    4 In tango they are located in the '''tango.util.collection''' package, 
     2= The container classes = 
     3Tango provides a number of container classes. 
     4In tango they are located in the '''tango.util.container''' package, 
    55which is home to a variety of templated containers. 
    66 
    7 Collection classes store ''things'', and do so in different ways. 
     7Container classes store ''things'', and do so in different ways. 
    88For example, the user can choose between a list and an array to store the same 
    99information - each storage mechanism has its own pros and cons. 
    1111for the ''things'' to  be stored. 
    1212 
    13 It is good practice to define an alias for the type one wants to use 
    14  
    15 {{{ 
    16 #!d 
    17 alias LinkSeq!(int) MyIntList; 
    18  
    19 auto list = new MyIntList; 
    20 list.append(1); 
    21 }}} 
    22  
    2313== Types of containers == 
    2414 
    2616 
    2717||            || '''Array''' || '''Link''' || '''Tree''' || '''Hash''' ||  
    28 || Bag        || [[docs(ArrayBag,tango.util.collection.ArrayBag.html,)]]    ||            || [[docs(TreeBag,tango.util.collection.TreeBag.html,)]]    ||            || 
    29 || Set        ||             ||            ||            || [[docs(HashSet,tango.util.collection.HashSet.html,)]]   || 
    30 || Sequence   || [[docs(ArraySeq,tango.util.collection.ArraySeq.html,)]]   || [[docs(LinkSeq,tango.util.collection.LinkSeq.html,)]], [[docs(CircularSeq,tango.util.collection.CircularSeq.html,)]] ||  ||            || 
    31 || Map        ||             || [[docs(LinkMap,tango.util.collection.LinkMap.html,)]]    || [[docs(TreeMap,tango.util.collection.TreeMap.html,)]]   || [[docs(HashMap,tango.util.collection.HashMap.html,)]]   || 
    32  
     18|| Bag        ||             ||            ||            ||            || 
     19|| Set        ||             ||            ||            ||  [[docs(HashSet,tango.util.container.HashSet.html,)]] || 
     20|| Sequence   ||             || [[docs(LinkedList,tango.util.container.LinkedList.html,)]], [[docs(CircularList,tango.util.container.CircularList.html,)]] ||  ||            || 
     21|| Map        ||             ||  || [[docs(SortedMap,tango.util.container.SortedMap.html,)]] || [[docs(HashMap,tango.util.container.HashMap.html,)]]   || 
    3322 
    3423'''Bag''' 
    3524  This is the simplest container. Throw everything in.  
    36   The sequence of elements is not defined.  
     25  The sequence of elements is not defined. Duplicates allowed. 
    3726 
    3827'''Set''' 
    39   In a set there are no duplicates. The distinction between Set and Bag is that the latter may have duplicates
     28  Same like Bag, but no duplicates. If the implementation is using 'Hash' and the element type is object, the sequence on iterating over the contain may changes in each run. To avoid this, either have a content based hash for the element type, or use sorted container
    4029 
    4130'''Sequence''' 
    5847  requires iteration over the list. For big data collections, this is very slow. 
    5948 
     49  !LinkedList vs. !CircularList: The !LinkedList is a singly linked list. That means, that search can 
     50  only be made in the forward direction. So every method that wants to access the elements at the end, 
     51  has to iterate over the whole list. On the other hand, the !CircularList is a double linked List,  
     52  that can iterate in both directions. This come with a bit more memory consumption and a bit more  
     53  overhead for pointer controlling, but some operations can be faster, because they can access the end 
     54  of the list directly. 
     55 
     56 
    6057'''Trees''' 
    6158  Containers that use a binary tree to access their members.  
    6663  Also the elements need to support a good '''toHash()''' implementation. 
    6764 
    68 == Model and Method Overview == 
    69  * [http://www.dsource.org/projects/tango/browser/trunk/doc/images/collection.png?format=raw Relationships between the collection classes] 
    70  * [http://www.dsource.org/projects/tango/browser/trunk/doc/images/methods.png?format=raw Methods exposed by the collection classes] 
    71  
    72 == Create collections == 
     65== Create containers == 
    7366 
    7467The easiest form is to instantiate directly and use an auto variable to hold the reference. 
    7568{{{ 
    7669#!d 
    77     auto list2 = new LinkSeq!( int ); 
    78 }}} 
    79  
    80 In most cases a collection type is use more than once. 
    81 So it is good to have an alias. 
    82 {{{ 
    83 #!d 
    84     alias LinkSeq!( char[] ) StrList; 
    85     StrList list1 = new StrList; 
     70    auto list1 = new LinkedList!( int ); 
     71}}} 
     72 
     73In most cases a container type is used more than once. 
     74So it is good practice to have an alias. 
     75{{{ 
     76#!d 
     77    alias CircularList!( char[] ) StrList; 
     78    auto list2 = new StrList; 
    8679}}} 
    8780 
    9184{{{ 
    9285#!d 
    93     list1.append( "The first item in list1" ); 
    94     list2.prepend( 2 ); 
    95 }}} 
    96 See the [http://www.dsource.org/projects/tango/browser/trunk/doc/images/methods.png?format=raw Methods exposed by the collection classes] to get a good overview. 
    97  
     86    list1.prepend( 2 ); 
     87    list1.append( 3 ); 
     88    list1.append( 4 ); 
     89    list2.append( "The first item in list1" ); 
     90}}} 
     91 
     92{{{ 
     93#!d 
     94    int oldValue = list1.removeHead(); // removes the '2' 
     95}}} 
    9896 
    9997== Visiting contained elements == 
    100  
     98''This section is not completed yet and is a copy of the collection doc''[[br]] 
    10199The typical, and simplest pattern is 
    102100 
    104102#!d 
    105103    foreach (key, value; map) 
    106              Stdout.formatln ("Key: {0}, Value: {1}", key, value); 
     104             Stdout.formatln ("Key: {}, Value: {}", key, value); 
    107105}}} 
    108106 
    123121          char[] key;  
    124122          auto value = it.get(key); 
    125           Stdout.formatln ("Key: {0}, Value:{1}", key, value); 
     123          Stdout.formatln ("Key: {}, Value:{}", key, value); 
    126124    } 
    127125}}} 
    132130 
    133131=== Asynchronous mutation during iteration === 
     132''This section is not completed yet and is a copy of the collection doc''[[br]] 
    134133 
    135134Iterators are sensitive to container changes whilst they operate, and will throw an exception when this occurs. This it to ensure the client sees a consistent view of the container for the lifetime of the iterator. 
    136135 
    137136=== Caution with iterators === 
     137''This section is not completed yet and is a copy of the collection doc''[[br]] 
    138138 
    139139It is currently not possible to modify the container while iterating over it with ''foreach'' or an iterator. To delete certain elements from a container it is necessary to do it in two steps. First find the elements to delete, then do the deletion 
    159159 
    160160== !InterleavingIterator == 
     161''This section is not completed yet and is a copy of the collection doc''[[br]] 
    161162 
    162163This more complex ''Iterator'' shows why iterators are still useful, even if we have the ''foreach'' construct. 
    197198 
    198199== !FilteringIterator == 
     200''This section is not completed yet and is a copy of the collection doc''[[br]] 
    199201 
    200202'''[[docs(FilteringIterators,tango.util.collection.iterator.FilteringIterator.html,)]]''' allow you to filter out elements from other enumerations before they are seen by their ''consumers'' (i.e. the callers of '''get'''). 
    231233 
    232234== Comparators == 
     235''This section is not completed yet and is a copy of the collection doc''[[br]] 
    233236 
    234237Sorted containers like trees, need to compare the elements. The algorithm that is used for this comparison can be user specified. E.g. strings can be sorted in different ways. If you want a bag to have its addIf using your compare method, this can be done like this 
    250253 
    251254== Screeners == 
     255''This section is not completed yet and is a copy of the collection doc''[[br]] 
    252256 
    253257Each container has the possibility to have a predicate as a so called screener. The definition can be found in the '''Collection''' class. 
    284288 
    285289== Bag and Set == 
     290''This section is not completed yet and is a copy of the collection doc''[[br]] 
    286291 
    287292[[docs(Bags,tango.util.collection.model.Bag.html,)]] are collections supporting multiple occurrences of elements. 
    297302 
    298303== Sequence, the ordered storage == 
     304''This section is not completed yet and is a copy of the collection doc''[[br]] 
    299305Sequences are indexed, sequentially ordered collections. Indices are always in the range 0 .. size() -1. All accesses by index are checked, raising exceptions if the index falls out of range. 
    300306 
    307313 
    308314== Map, the associative Storage == 
     315''This section is not completed yet and is a copy of the collection doc''[[br]] 
    309316[[docs(Maps,tango.util.collection.model.Map.html,)]] maintain keyed elements. Any kind of Object or primitive type may serve as a key for an element. Each key is unique and is associated with one value. 
    310317 
    322329 
    323330= Hash vs Tree = 
     331''This section is not completed yet and is a copy of the collection doc''[[br]] 
    324332'''Sets''' and '''Maps''' are available with tree or hash implementation. When should one choose which?  
    325333 
    331339 
    332340= D builtin arrays and hashes vs. !ArraySeq and !HashMap = 
     341''This section is not completed yet and is a copy of the collection doc''[[br]] 
    333342 
    334343D already supports builtin dynamic arrays and hashes.  
    358367== Illustrations == 
    359368 
    360 [[Image(source:/trunk/doc/images/collection.png)]] 
    361  
    362  
    363  
    364 [[Image(source:/trunk/doc/images/methods.png)]] 
    365  
    366369== User Comments == 
    367370