indigo. tools.list| Created | 23.04.2005 | | Last modified | 10.08.2005 |
Contains a generic list. See List for details. Summary | | | Implements a random-access-iterator for List. | | | | Type of container this iterator works on. | | Type of values this iterator references. | | | | Returns the value pointed to by the iterator. | | Returns a pointer of the value pointed to by the iterator. | | | | Sets the value pointed to by the iterator to val. | | | | Moves the iterator one item forward in the list, and returns the previous item. | | Moves the iterator one item backward in the list, and returns the next item. | | Creates a copy of this iterator, moves it delta items forward in the list, and returns the resulting iterator. | | Creates a copy of this iterator, moves it delta items backward in the list, and returns the resulting iterator. | | Calculates the number of items this iterator is ahead of iter. | | Moves the iterator delta items forward in the list. | | Moves the iterator delta items backward in the list. | | Returns a value < 0 if this iterator points to an item before iter, 0 if they are equal, and a value > 0 otherwise. | | | | | | Alias for the type of the values the list stores. | | A random-access-iterator for the list. | | | | | | Returns the number of items in the list. | | Returns the number of items in the list. | | Returns the number of items in the list. | | Returns true if the list has length 0, otherwise false. | | Returns true if the list has length 0. | | Returns the first item in the list. | | Returns the last item in the list. | | Returns the first item in the list. | | Returns the last item in the list. | | Returns an iterator pointing to the first item in the list. | | Returns an iterator pointing behind the last item of the list. | | Returns a list with a copy of this list’s data. | | | | Constructs a list with a copy of all items in vec. | | Returns the item at position i in the list. | | Returns a pointer to the item at position i in the list. | | Returns the item at position i in the list. | | Returns the item at position i in the vector. | | Returns true if the list contains value, otherwise false. | | Returns the number of occurences of value in the list. | | Returns the position of the first occurence of value in the list, beginning at position from. | | Returns the position of the last occurence of value in the list, beginning before position before. | | Returns a list containing the first count items of the list. | | Returns a list containing the items from position i to the end of the list. | | Returns a list containing count items of the list, beginning from position i. | | Returns a list containing the count last items of the list. | | Removes all elements from the list. | | Releases unused internal storage to the garbage collector. | | This removes all elements from the list and makes the internal storage reavailable to the garbage collector. | | Inserts value at the end of the list. | | Inserts vec at the end of the list. | | Inserts list at the end of this list. | | Appends all arguments to the list. | | Inserts value at the beginning of the list. | | Inserts the contents of vec at the beginning of the list. | | Inserts the contents of list at the beginning of the list. | | | | | | Inserts value before the item at position i. | | Inserts value before the item pointed to by i. | | Inserts count times value before the item at position i. | | Inserts count times value before the item pointed to by i. | | Inserts vec before the item at position i. | | Inserts vec before the item pointed to by i. | | Inserts list before the item at position i. | | Inserts list before the item pointed to by i. | | Assigns value to the item at position i. | | Exchanges the item at position i with the item at position j. | | Moves the item at position from to index position to. | | Removes count items, beginning at position i. | | Removes the item pointed to by i. | | Removes all items from begin up to, but not including end. | | | | Removes the first item of the list. | | Removes the first count items of the list. | | Removes the last item of the list. | | Removes the last count items of the list. | | | | | | Removes all occurences of value in the list. | | Removes the first element of the list, and returns its value. | | Removes the last element of the list, and returns its value. | | Removes the item at position i from the list, and returns its value. | | Reverses the contents of the list in place. | | | | The same as append(T), and returning the list. | | Creates a copy of the list and appends vec. | | Creates a copy of vec and appends the list. | | Creates a copy of this list and appends list. | | Applies dg to all elements in the list, or until dg returns a nonzero value. | | Returns true if the list contains only one item which is equal to value. | | Returns true if vec has the same length and contents as the list, false otherwise. | | Returns true if list has the same length and contents as the list, false otherwise. | | This is the same as at(). | | Assigns value to the item at position i. | | Compares the contents of the list with vec. | | Compares the contents of the list with list. | | | | Sorts the contents of the list in place, and returns the list. | | Sorts the contents of the list in place, using the comparison function lessThan. | | Sorts the list using the specified lessThan function (see insertionSort() for information on it and how to instantiate the template). | | Serializes this list and all its items into the DataStream st. | | |
ListIteratorImplements a random-access-iterator for List. Obtain an iterator from a list with List.begin or List.end. You can then navigate through the list with the arithmetic operators, and compare iterators with each other. The value property can be used to obtain/change the value the iterator points to (note that you cannot use operator * for this purpose). The ptr property returns a pointer to the item, which is useful for structs as items. NoteThe iterator will not check for list bounds, not even in debug mode. You always have to ensure it points to a valid item in a list, or to List.end. Summary | | | Type of container this iterator works on. | | Type of values this iterator references. | | | | Returns the value pointed to by the iterator. | | Returns a pointer of the value pointed to by the iterator. | | | | Sets the value pointed to by the iterator to val. | | | | Moves the iterator one item forward in the list, and returns the previous item. | | Moves the iterator one item backward in the list, and returns the next item. | | Creates a copy of this iterator, moves it delta items forward in the list, and returns the resulting iterator. | | Creates a copy of this iterator, moves it delta items backward in the list, and returns the resulting iterator. | | Calculates the number of items this iterator is ahead of iter. | | Moves the iterator delta items forward in the list. | | Moves the iterator delta items backward in the list. | | Returns a value < 0 if this iterator points to an item before iter, 0 if they are equal, and a value > 0 otherwise. |
ContainerTypeType of container this iterator works on. ValueTypeType of values this iterator references. valueReadReturns the value pointed to by the iterator. The iterator has to point to a valid item in a list. If the list contains structs, you cannot use this function to call a member function of the struct which needs to change the struct. Use ptr for this purpose, it may also be faster. WriteSets the value pointed to by the iterator to val. The iterator has to point to a valid item in a list. ptrReturns a pointer of the value pointed to by the iterator. The iterator has to point to a valid item in a list. See also value. setValue()Sets the value pointed to by the iterator to val. The iterator has to point to a valid item in a list. opPostInc()Moves the iterator one item forward in the list, and returns the previous item. Use the prefix form if possible, it may be faster. opPostDec()Moves the iterator one item backward in the list, and returns the next item. Use the prefix form if possible, it may be faster. opAdd()| ListIterator opAdd( | ptrdiff_t | delta | ) |
|
Creates a copy of this iterator, moves it delta items forward in the list, and returns the resulting iterator. opSub()| ListIterator opSub( | ptrdiff_t | delta | ) |
|
Creates a copy of this iterator, moves it delta items backward in the list, and returns the resulting iterator. opSub()| ptrdiff_t opSub( | ListIterator | iter | ) |
|
Calculates the number of items this iterator is ahead of iter. They must both belong to the same list. opAddAssign()| ListIterator opAddAssign( | ptrdiff_t | delta | ) |
|
Moves the iterator delta items forward in the list. opSubAssign()| ListIterator opSubAssign( | ptrdiff_t | delta | ) |
|
Moves the iterator delta items backward in the list. opCmp()| ptrdiff_t opCmp( | ListIterator | iter | ) |
|
Returns a value < 0 if this iterator points to an item before iter, 0 if they are equal, and a value > 0 otherwise. The iterators must point to the same list. ListProvides a datastructure that is a mixture of a Vector and a LinkedList. It corresponds to the QList class (http://doc.trolltech.com/4.0/qlist.html). Internally it is represented as an array of pointers to the items, unless the size of the items is not greater than that of a pointer or the items are dynamic arrays (they cannot be created with operator new ─ to work around that, box them in a struct). There are some hints on which container to choose (Container types). Besides these details, List tries to behave like a Vector and thus like a built-in array. It automatically handles allocation of needed space quite efficiently, provides fast index-based access and fast insertions and removals, and a lot of convenience functions. It needs 16 bytes on a 32 bit machine. The List is “automagically” instantiated with or without support for comparisons and sorting, depending on the type you supply. List!(int) sortableList;
List!(structWithoutOpCmp) unsortableList;
To access items, use operator [], at(), ptrAt() or value(size_t). To find all occurences of a particular value in a list, use indexOf() or lastIndexOf(). Both return the index of the matching item, or length if they could not find one. If you simply want to check whether the list contains a value, use contains(). Use count(T) to count the number of occurences. To change the contents of the list, there are the functions insert(size_t, T), remove(size_t), prepend(T) and append(T). While append(T) and prepend(T) are fast (constant time), the others can be slow for large lists (over a thousand items). Use LinkedList if you need fast insertions/deletions. If you need to concatenate a number of vectors, arrays or items, use appendAll(). For operations at either end of the list there are removeFirst(), removeLast(), takeFirst() and takeLast(). If you want to remove all occurences of a given value in the list, use removeAll(). List also provides iterator-based access with Iterator. These are random-access-iterators with full operator overloads. The only difference is that you cannot use operator * to retrieve the value the iterator points to. Use ListIterator.value instead: List!(int) list;
// ...
for (list.Iterator iter = list.begin, endIter = list.end; iter != endIter; ++iter)
printf("%i\n", iter.value);
NoteIf you store objects (i.e. instances of a class) in a list, the list only stores references to the objects. They are initialized with null by default. Functions like contains() always compare on identity (with is). If you store pointers, object references or dynamic arrays in the container, they will not get nullified automatically when deleting items. This may lead to space waste because the garbage collector thinks they are still being used. Call squeeze() to get rid of them. Summary | | | Alias for the type of the values the list stores. | | A random-access-iterator for the list. | | | | | | Returns the number of items in the list. | | Returns the number of items in the list. | | Returns the number of items in the list. | | Returns true if the list has length 0, otherwise false. | | Returns true if the list has length 0. | | Returns the first item in the list. | | Returns the last item in the list. | | Returns the first item in the list. | | Returns the last item in the list. | | Returns an iterator pointing to the first item in the list. | | Returns an iterator pointing behind the last item of the list. | | Returns a list with a copy of this list’s data. | | | | Constructs a list with a copy of all items in vec. | | Returns the item at position i in the list. | | Returns a pointer to the item at position i in the list. | | Returns the item at position i in the list. | | Returns the item at position i in the vector. | | Returns true if the list contains value, otherwise false. | | Returns the number of occurences of value in the list. | | Returns the position of the first occurence of value in the list, beginning at position from. | | Returns the position of the last occurence of value in the list, beginning before position before. | | Returns a list containing the first count items of the list. | | Returns a list containing the items from position i to the end of the list. | | Returns a list containing count items of the list, beginning from position i. | | Returns a list containing the count last items of the list. | | Removes all elements from the list. | | Releases unused internal storage to the garbage collector. | | This removes all elements from the list and makes the internal storage reavailable to the garbage collector. | | Inserts value at the end of the list. | | Inserts vec at the end of the list. | | Inserts list at the end of this list. | | Appends all arguments to the list. | | Inserts value at the beginning of the list. | | Inserts the contents of vec at the beginning of the list. | | Inserts the contents of list at the beginning of the list. | | | | | | Inserts value before the item at position i. | | Inserts value before the item pointed to by i. | | Inserts count times value before the item at position i. | | Inserts count times value before the item pointed to by i. | | Inserts vec before the item at position i. | | Inserts vec before the item pointed to by i. | | Inserts list before the item at position i. | | Inserts list before the item pointed to by i. | | Assigns value to the item at position i. | | Exchanges the item at position i with the item at position j. | | Moves the item at position from to index position to. | | Removes count items, beginning at position i. | | Removes the item pointed to by i. | | Removes all items from begin up to, but not including end. | | | | Removes the first item of the list. | | Removes the first count items of the list. | | Removes the last item of the list. | | Removes the last count items of the list. | | | | | | Removes all occurences of value in the list. | | Removes the first element of the list, and returns its value. | | Removes the last element of the list, and returns its value. | | Removes the item at position i from the list, and returns its value. | | Reverses the contents of the list in place. | | | | The same as append(T), and returning the list. | | Creates a copy of the list and appends vec. | | Creates a copy of vec and appends the list. | | Creates a copy of this list and appends list. | | Applies dg to all elements in the list, or until dg returns a nonzero value. | | Returns true if the list contains only one item which is equal to value. | | Returns true if vec has the same length and contents as the list, false otherwise. | | Returns true if list has the same length and contents as the list, false otherwise. | | This is the same as at(). | | Assigns value to the item at position i. | | Compares the contents of the list with vec. | | Compares the contents of the list with list. | | | | Sorts the contents of the list in place, and returns the list. | | Sorts the contents of the list in place, using the comparison function lessThan. | | Sorts the list using the specified lessThan function (see insertionSort() for information on it and how to instantiate the template). | | Serializes this list and all its items into the DataStream st. | | |
ValueTypeAlias for the type of the values the list stores. IteratorA random-access-iterator for the list. See ListIterator. iteratorAlias for Iterator. Provided for STL compatibility. lengthReturns the number of items in the list. countReturns the number of items in the list. Synonym for length. You cannot use count as a writable property like length, because there are overloads of it that have a different meaning. sizeReturns the number of items in the list. Synonym for length. isEmptyReturns true if the list has length 0, otherwise false. emptyReturns true if the list has length 0. Alias for isEmpty. Included for STL compatibility. firstReadReturns the first item in the list. It assumes that the list is not empty. Note that you cannot use this function to call a member function of the value that needs to change the value. This also applies to setting the length of a dynamic array. WriteReplaces the first element with value. The list must not be empty. See also last. lastReadReturns the last item in the list. It assumes that the list is not empty. Note that you cannot use this function to call a member function of the value that needs to change the value. This also applies to setting the length of a dynamic array. WriteReplaces the last element with value. The list must not be empty. See also first. frontReturns the first item in the list. Alias for first. backReturns the last item in the list. Alias for last. beginReturns an iterator pointing to the first item in the list. If the list is empty, this is the same as end. See also end. endReturns an iterator pointing behind the last item of the list. See also begin. dupReturns a list with a copy of this list’s data. fromArray()| static List fromArray( | T[] | vec | ) |
|
Constructs a list with a copy of all items in vec. It is not possible to construct a list without copying the items ─ use Vector to achieve that. at()Returns the item at position i in the list. i must be a valid position in the list. Note that you cannot use this function to call a member function of the value that needs to change the value. This also applies to setting the length of a dynamic array. See also value(size_t), ptrAt(). ptrAt()Returns a pointer to the item at position i in the list. i must be a valid position in the list. This function must be used if you want to call member functions of the value that change it. See also value(size_t), at(). value(size_t)Returns the item at position i in the list. If i is not a valid position, it returns a default initialized item. Note that you cannot use this function to call a member function of the value that needs to change the value. This also applies to setting the length of a dynamic array. See also at(), ptrAt(). value(size_t, T)| T value( | size_t | i, | | T | defValue | ) |
|
Returns the item at position i in the vector. If i is not a valid position, it returns defValue. Overloaded function ─ see above for other details. contains()Returns true if the list contains value, otherwise false. If the list stores objects, these are compared on identity, not equality. See also count(T), indexOf(). count(T)Returns the number of occurences of value in the list. If the list stores objects, these are compared on identity, not equality. See also contains(). indexOf()| size_t indexOf( | T | value, | | | | size_t | from | = | 0 | ) |
|
Returns the position of the first occurence of value in the list, beginning at position from. If value could not be found, length is returned. If the list stores objects, these are compared on identity, not equality. See also contains(), lastIndexOf(). lastIndexOf()| size_t lastIndexOf( | T | value, | | size_t | before | ) |
|
Returns the position of the last occurence of value in the list, beginning before position before. If value could not be found, length is returned. If the list stores objects, these are compared on identity, not equality. list.lastIndexOf(5, 1) // will search only the first item.
list.lastIndexOf(5, vec.length-1) // will search all but the last item.
See also indexOf(). left()Returns a list containing the first count items of the list. count must not be greater than length. The data is copied. See also mid(size_t), right(). mid(size_t)Returns a list containing the items from position i to the end of the list. i must be a valid position in the list. The data is copied. See also left(), right(). mid(size_t, size_t)| List mid( | size_t | i, | | size_t | count | ) |
|
Returns a list containing count items of the list, beginning from position i. Overloaded function ─ see above for other details. right()Returns a list containing the count last items of the list. count must not be greater than length(). The data is copied. See also left(), mid(size_t). clear()Removes all elements from the list. Note that the internal storage is not freed with this operation, therefore the list can still occupy a large memory block. Use free() to release it as well. squeeze()Releases unused internal storage to the garbage collector. This will not affect the items in the list. Call this function after deleting a lot of items, and if you are sure you will not insert new items again. NoteCurrently it is not possible to release a part of a dynamic array to the garbage collector. This function only does something if the list stores pointers, arrays or object references: they are all set to null to signal the garbage collector that the referenced memory is no longer needed by the list. See also free(). free()This removes all elements from the list and makes the internal storage reavailable to the garbage collector. Note that this storage will only be available again after a garbage collection, and if the list contains objects their destructors will not be called until the collection. To immediately delete the objects, use deleteAll() before free(). See also squeeze(). append(T[])Inserts vec at the end of the list. Overloaded function ─ see above for other details. append(List)Inserts list at the end of this list. Overloaded function ─ see above for other details. appendAll()Appends all arguments to the list. There must be at least 2 arguments (otherwise use append(T), it is faster), and they can be of type T, T[] or List. The function calculates the resulting length at first to avoid unnecessary allocation. Use it instead of statements like these: list = list1 ~ 'x' ~ array2;
// or
list.append(list1);
list.append('x');
list.append(array2);
// Better:
list.appendAll(list1, 'x', array2);
|