|
- 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 |
|
1 | 1 | [[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 = |
---|
| 3 | Tango provides a number of container classes. |
---|
| 4 | In tango they are located in the '''tango.util.container''' package, |
---|
5 | 5 | which is home to a variety of templated containers. |
---|
6 | 6 | |
---|
7 | | Collection classes store ''things'', and do so in different ways. |
---|
| 7 | Container classes store ''things'', and do so in different ways. |
---|
8 | 8 | For example, the user can choose between a list and an array to store the same |
---|
9 | 9 | information - each storage mechanism has its own pros and cons. |
---|
11 | 11 | for the ''things'' to be stored. |
---|
12 | 12 | |
---|
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 | | |
---|
23 | 13 | == Types of containers == |
---|
24 | 14 | |
---|
26 | 16 | |
---|
27 | 17 | || || '''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,)]] || |
---|
33 | 22 | |
---|
34 | 23 | '''Bag''' |
---|
35 | 24 | 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. |
---|
37 | 26 | |
---|
38 | 27 | '''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. |
---|
40 | 29 | |
---|
41 | 30 | '''Sequence''' |
---|
58 | 47 | requires iteration over the list. For big data collections, this is very slow. |
---|
59 | 48 | |
---|
| 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 | |
---|
60 | 57 | '''Trees''' |
---|
61 | 58 | Containers that use a binary tree to access their members. |
---|
66 | 63 | Also the elements need to support a good '''toHash()''' implementation. |
---|
67 | 64 | |
---|
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 == |
---|
73 | 66 | |
---|
74 | 67 | The easiest form is to instantiate directly and use an auto variable to hold the reference. |
---|
75 | 68 | {{{ |
---|
76 | 69 | #!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 | |
---|
| 73 | In most cases a container type is used more than once. |
---|
| 74 | So it is good practice to have an alias. |
---|
| 75 | {{{ |
---|
| 76 | #!d |
---|
| 77 | alias CircularList!( char[] ) StrList; |
---|
| 78 | auto list2 = new StrList; |
---|
86 | 79 | }}} |
---|
87 | 80 | |
---|
91 | 84 | {{{ |
---|
92 | 85 | #!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 | }}} |
---|
98 | 96 | |
---|
99 | 97 | == Visiting contained elements == |
---|
100 | | |
---|
| 98 | ''This section is not completed yet and is a copy of the collection doc''[[br]] |
---|
101 | 99 | The typical, and simplest pattern is |
---|
102 | 100 | |
---|
104 | 102 | #!d |
---|
105 | 103 | foreach (key, value; map) |
---|
106 | | Stdout.formatln ("Key: {0}, Value: {1}", key, value); |
---|
| 104 | Stdout.formatln ("Key: {}, Value: {}", key, value); |
---|
107 | 105 | }}} |
---|
108 | 106 | |
---|
123 | 121 | char[] key; |
---|
124 | 122 | auto value = it.get(key); |
---|
125 | | Stdout.formatln ("Key: {0}, Value:{1}", key, value); |
---|
| 123 | Stdout.formatln ("Key: {}, Value:{}", key, value); |
---|
126 | 124 | } |
---|
127 | 125 | }}} |
---|
132 | 130 | |
---|
133 | 131 | === Asynchronous mutation during iteration === |
---|
| 132 | ''This section is not completed yet and is a copy of the collection doc''[[br]] |
---|
134 | 133 | |
---|
135 | 134 | Iterators 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. |
---|
136 | 135 | |
---|
137 | 136 | === Caution with iterators === |
---|
| 137 | ''This section is not completed yet and is a copy of the collection doc''[[br]] |
---|
138 | 138 | |
---|
139 | 139 | It 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 |
---|
159 | 159 | |
---|
160 | 160 | == !InterleavingIterator == |
---|
| 161 | ''This section is not completed yet and is a copy of the collection doc''[[br]] |
---|
161 | 162 | |
---|
162 | 163 | This more complex ''Iterator'' shows why iterators are still useful, even if we have the ''foreach'' construct. |
---|
197 | 198 | |
---|
198 | 199 | == !FilteringIterator == |
---|
| 200 | ''This section is not completed yet and is a copy of the collection doc''[[br]] |
---|
199 | 201 | |
---|
200 | 202 | '''[[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'''). |
---|
231 | 233 | |
---|
232 | 234 | == Comparators == |
---|
| 235 | ''This section is not completed yet and is a copy of the collection doc''[[br]] |
---|
233 | 236 | |
---|
234 | 237 | Sorted 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 |
---|
250 | 253 | |
---|
251 | 254 | == Screeners == |
---|
| 255 | ''This section is not completed yet and is a copy of the collection doc''[[br]] |
---|
252 | 256 | |
---|
253 | 257 | Each container has the possibility to have a predicate as a so called screener. The definition can be found in the '''Collection''' class. |
---|
284 | 288 | |
---|
285 | 289 | == Bag and Set == |
---|
| 290 | ''This section is not completed yet and is a copy of the collection doc''[[br]] |
---|
286 | 291 | |
---|
287 | 292 | [[docs(Bags,tango.util.collection.model.Bag.html,)]] are collections supporting multiple occurrences of elements. |
---|
297 | 302 | |
---|
298 | 303 | == Sequence, the ordered storage == |
---|
| 304 | ''This section is not completed yet and is a copy of the collection doc''[[br]] |
---|
299 | 305 | Sequences 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. |
---|
300 | 306 | |
---|
307 | 313 | |
---|
308 | 314 | == Map, the associative Storage == |
---|
| 315 | ''This section is not completed yet and is a copy of the collection doc''[[br]] |
---|
309 | 316 | [[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. |
---|
310 | 317 | |
---|
322 | 329 | |
---|
323 | 330 | = Hash vs Tree = |
---|
| 331 | ''This section is not completed yet and is a copy of the collection doc''[[br]] |
---|
324 | 332 | '''Sets''' and '''Maps''' are available with tree or hash implementation. When should one choose which? |
---|
325 | 333 | |
---|
331 | 339 | |
---|
332 | 340 | = 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]] |
---|
333 | 342 | |
---|
334 | 343 | D already supports builtin dynamic arrays and hashes. |
---|
358 | 367 | == Illustrations == |
---|
359 | 368 | |
---|
360 | | [[Image(source:/trunk/doc/images/collection.png)]] |
---|
361 | | |
---|
362 | | |
---|
363 | | |
---|
364 | | [[Image(source:/trunk/doc/images/methods.png)]] |
---|
365 | | |
---|
366 | 369 | == User Comments == |
---|
367 | 370 | |
|
|