Collections
Collections are abstractions to represent sets of values. In statically-typed languages, the values are typically of a common data type.
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
Create a collection, and add a few values to it.
Ada
Ada 95 and earlier offers arrays. Ada 2005 adds the Ada.Containers package and its children. Examples of Doubly Linked Lists and Vectors are given. Ada 2005 also provides hashed and ordered Maps and Sets (not shown).
anonymous arrays
In Ada, arrays can be indexed on any range of discrete values. The example below creates an anonymous array indexed from -3 to -1. It initializes the three elements of the array at declaration. Then it reverses their order in the array.
Anonymous arrays have no type associated with them that is accessible to the programmer. This means that anonymous arrays cannot be compared in the aggregate to other arrays (even those with the same index structure and contained type) or passed as a parameter to a subprogram. For these reasons, anonymous arrays are best used as singletons and global constants.
<lang Ada>procedure Array_Collection is
A : array (-3 .. -1) of Integer := (1, 2, 3);
begin
A (-3) := 3; A (-2) := 2; A (-1) := 1;
end Array_Collection;</lang>
array types
Because of the limitations of anonymous arrays noted above, arrays are more typically defined in Ada as array types, as in the example below.
<lang Ada>procedure Array_Collection is
type Array_Type is array (1 .. 3) of Integer; A : Array_Type := (1, 2, 3);
begin
A (1) := 3; A (2) := 2; A (3) := 1;
end Array_Collection;</lang>
unconstrained arrays
Dynamic arrays can be created through the use of pointers to unconstrained arrays. While an unconstrained array's index type is defined, it does not have a pre-defined range of indices - they are specified at the time of declaration or, as would be the case in a dynamic array, at the time the memory for the array is allocated. The creation of a dynamic array is not shown here, but below is an example declaration of an unconstrained array in Ada.
<lang Ada>procedure Array_Collection is
type Array_Type is array (positive range <>) of Integer; -- may be indexed with any positive -- Integer value A : Array_Type(1 .. 3); -- creates an array of three integers, indexed from 1 to 3
begin
A (1) := 3; A (2) := 2; A (3) := 1;
end Array_Collection;</lang>
doubly linked lists
<lang Ada>with Ada.Containers.Doubly_Linked_Lists; use Ada.Containers;
procedure Doubly_Linked_List is
package DL_List_Pkg is new Doubly_Linked_Lists (Integer); use DL_List_Pkg; DL_List : List;
begin
DL_List.Append (1); DL_List.Append (2); DL_List.Append (3);
end Doubly_Linked_List;</lang>
vectors
<lang Ada>with Ada.Containers.Vectors; use Ada.Containers;
procedure Vector_Example is
package Vector_Pkg is new Vectors (Natural, Integer); use Vector_Pkg; V : Vector;
begin
V.Append (1); V.Append (2); V.Append (3);
end Vector_Example;</lang>
AutoHotkey
Objects
Documentation <lang AutoHotkey>myCol := Object() mycol.mykey := "my value!" mycol["mykey"] := "new val!" MsgBox % mycol.mykey ; new val</lang>
Pseudo-arrays
Documentation: http://www.autohotkey.com/docs/misc/Arrays.htm <lang AutoHotkey>Loop 3
array%A_Index% := A_Index * 9
MsgBox % array1 " " array2 " " array3 ; 9 18 27</lang>
Structs
Structs are not natively supported in AutoHotkey, however they are often required in DllCalls to C++ Dlls. This shows how to retrieve values from a RECT structure in AutoHotkey (from the DllCall documentation at http://www.autohotkey.com/docs/commands/DllCall.htm) <lang AutoHotkey>VarSetCapacity(Rect, 16) ; A RECT is a struct consisting of four 32-bit integers (i.e. 4*4=16). DllCall("GetWindowRect", UInt, WinExist(), UInt, &Rect) ; WinExist() returns an HWND. MsgBox % "Left " . NumGet(Rect, 0, true) . " Top " . NumGet(Rect, 4, true)
. " Right " . NumGet(Rect, 8, true) . " Bottom " . NumGet(Rect, 12, true)</lang>
AWK
In awk, the closest thing to collections would be arrays. They are created when needed at assignment <lang awk>a[0]="hello"</lang> or by splitting a string <lang awk>split("one two three",a)</lang> Single elements are accessible with the bracket notation, like in C: <lang awk>print a[0]</lang> One can iterate over the elements of an array: <lang awk>for(i in a) print i":"a[i]</lang>
C
One thing in C language proper that can be said to be a collection is array type. An array has a length known at compile time. <lang c>#define cSize( a ) ( sizeof(a)/sizeof(a[0]) ) /* a.size() */ int ar[10]; /* Collection<Integer> ar = new Collection<Integer>(10); */ ar[0] = 1; /* ar.set(0, 1); */ ar[1] = 2;
int* p; /* Iterator<Integer> p; Integer pValue; */ for (p=ar; /* for( p = ar.itereator(), pValue=p.next(); */
p<(ar+cSize(ar)); /* p.hasNext(); */ p++) { /* pValue=p.next() ) { */ printf("%d\n",*p); /* System.out.println(pValue); */
} /* } */</lang> Please note that c built-in pointer-arithmatic support which helps this logic. An integer may be 4 bytes, and a char 1 byte: the plus operator (+) is overloaded to multiply a incement by 4 for integer pointers and by 1 for char pointers (etc).
Another construct which can be seen as a collection is a malloced array. A malloced array's size is not known at compile time. <lang c> int* ar; /* Collection<Integer> ar; */ int arSize; arSize = (rand () % 6) + 1; ar = calloc(arSize, sizeof(int) ); /* ar = new ArrayList<Integer>(arSize); */ ar[0] = 1; /* ar.set(0, 1); */
int* p; /* Iterator<Integer> p; Integer pValue; */ for (p=ar; /* p=ar.itereator(); for( pValue=p.next(); */
p<(ar+arSize); /* p.hasNext(); */ p++) { /* pValue=p.next() ) { */ printf("%d\n",*p); /* System.out.println(pValue); */
} /* } */</lang>
A string is another C language construct (when looked at with its standard libraries) that behaves like a collection. A C language string is an array of char, and it's size may or may not be known at compile time, however a c string is terminated with a ASCII NUL (which may be stated as a constant, '\0' or ((char)0) in the C language). The String standard library "class" has many "methods", however instead of being called String.method(), they are usually called strmethod().
Arbitrarily complex data structures can be constructed, normally via language fetures struct
and pointers. They are everywhere, but not provided by the C language itself per se.
C++
C++ has a range of different collections optimized for different use cases. Note that in C++, objects of user-defined types are mostly treated just like objects of built-in types; especially there's no different treatment for collections. Thus all collections can simply be demonstrated with the built-in type int. For user-defined types, just replace int with the user-defined type. Any type which goes into a collection must be copyable and assignable (which in general is automatically the case unless you explicitly disallow it).
Note however that C++ collections store copies of the objects given to them, so you'll lose any polymorphic behaviour. If you need polymorphism, use a collection of pointers (or smart pointers like boost::shared_ptr).
built-in array
The simplest collection in C++ is the built-in array. Built-in arrays have a fixed size, and except for POD types (i.e. basically any type you culd also write in C), the members are all initialized at array creation time (if no explicit initialization is done, the default constructr is used).
<lang cpp>int a[5]; // array of 5 ints (since int is POD, the members are not initialized) a[0] = 1; // indexes start at 0
int primes[10] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 }; // arrays can be initialized on creation
- include <string>
std::string strings[4]; // std::string is no POD, therefore all array members are default-initialized
// (for std::string this means initialized with empty strings)</lang>
vector
A vector is basically a resizable array. It is optimized for adding/removing elements on the end, and fast access to elements anywhere. Inserting elements at the beginning or in the middle is possible, but in general inefficient.
<lang cpp>#include <vector>
std::vector<int> v; // empty vector v.push_back(5); // insert a 5 at the end v.insert(v.begin(), 7); // insert a 7 at the beginning</lang>
deque
A deque is optimized for appending and removing elements on both ends ofd the array. Accessing random elements is still efficient, but slightly less than with vector.
<lang cpp>#include <deque>
std::deque<int> d; // empty deque d.push_back(5); // insert a 5 at the end d.push_front(7); // insert a 7 at the beginning d.insert(v.begin()+1, 6); // insert a 6 in the middle</lang>
list
A list is optimized for insertion at an arbitrary place (provided you already have an iterator pointing to that place). Element access is efficient only in linear order.
<lang cpp>#include <list>
std::list<int> l; // empty list l.push_back(5); // insert a 5 at the end l.push_front(7); // insert a 7 at the beginning std::list::iterator i = l.begin(); ++l; l.insert(i, 6); // insert a 6 in the middle</lang>
set
A set keeps the inserted elements sorted, and also makes sure that each element occurs only once. Of course, if you want to put something into a set, it must be less-than-comparable, i.e. you must be able to compare which of two objects a and b is smaller using a<b (there's also a way to define sets with an user-defined order, in which case this restriction doesn't apply).
<lang cpp>#include <set>
std::set<int> s; // empty set s.insert(5); // insert a 5 s.insert(7); // insert a 7 (automatically placed after the 5) s.insert(5); // try to insert another 5 (will not change the set)</lang>
multiset
A multiset is like a set, except the same element may occur multiple times.
<lang cpp>#include <multiset>
std::multiset<int> m; // empty multiset m.insert(5); // insert a 5 m.insert(7); // insert a 7 (automatically placed after the 5) m.insert(5); // insert a second 5 (now m contains two 5s, followed by one 7)</lang>
C#
Arrays
<lang csharp> // Creates and initializes a new integer Array int[] intArray = new int[5] { 1, 2, 3, 4, 5 }; //same as int[] intArray = new int[]{ 1, 2, 3, 4, 5 }; //same as int[] intArray = { 1, 2, 3, 4, 5 };
//Arrays are zero-based string[] stringArr = new string[5]; stringArr[0] = "string"; </lang>
ArrayList and List
The size of ArrayList is dynamically increased as required. ArrayLists are zero-based. <lang csharp> //Create and initialize ArrayList ArrayList myAl = new ArrayList { "Hello", "World", "!" };
//Create ArrayList and add some values ArrayList myAL = new ArrayList();
myAL.Add("Hello"); myAL.Add("World"); myAL.Add("!");
</lang>
The List class is the generic equivalent of the ArrayList class. A List is a strongly typed list of objects that can be accessed by index ( zero-based again). <lang csharp> //Create and initialize List List<string> myList = new List<string> { "Hello", "World", "!" };
//Create List and add some values List<string> myList2 = new List<string>();
myList2.Add("Hello"); myList2.Add("World"); myList2.Add("!");
</lang>
Hashtable and Dictionary
Hashtables represent a collection of key/value pairs that are organized based on the hash code of the key. Keys must be unique. <lang csharp> //Create an initialize Hashtable Hashtable myHt = new Hashtable() { { "Hello", "World" }, { "Key", "Value" } };
//Create Hashtable and add some Key-Value pairs. Hashtable myHt2 = new Hashtable(); myHt2.Add("Hello", "World"); myHt2.Add("Key", "Value"); </lang> Dictionary is a generic class.It represents a collection of key/value pairs. Keys must be unique. <lang csharp> //Create an initialize Dictionary Dictionary<string, string> dict = new Dictionary<string, string>() { { "Hello", "World" }, { "Key", "Value" } }; //Create Dictionary and add some Key-Value pairs. Dictionary<string, string> dict2 = new Dictionary<string, string>(); dict2.Add("Hello", "World"); dict2.Add("Key", "Value"); </lang>
Clojure
Clojure's collections are immutable: rather than modifying an existing collection, you create a new collection based on a previous one but with changes, for example an additional element.
Hash maps
<lang Clojure>{1 "a", "Q" 10} ; commas are treated as whitespace (hash-map 1 "a" "Q" 10) ; equivalent to the above (let [my-map {1 "a"}]
(assoc my-map "Q" 10)) ; "adding" an element</lang>
Lists
<lang Clojure>'(1 4 7) ; a linked list (list 1 4 7) (cons 1 (cons 4 '(7)))</lang>
Vectors
<lang Clojure>['a 4 11] ; somewhere between array and list (vector 'a 4 11) (cons ['a 4] 11) ; vectors add at the *end*</lang>
Sets
<lang Clojure>#{:pig :dog :bear} (assoc #{:pig :bear} :dog) (set [:pig :bear :dog])</lang>
Common Lisp
hashing
<lang lisp>CL-USER> (let ((list '())
(hash-table (make-hash-table))) (push 1 list) (push 2 list) (push 3 list) (format t "~S~%" (reverse list)) (setf (gethash 'foo hash-table) 42) (setf (gethash 'bar hash-table) 69) (maphash (lambda (key value) (format t "~S => ~S~%" key value)) hash-table) ;; or print the hash-table in readable form ;; (inplementation-dependent) (write hash-table :readably t) ;; or describe it (describe hash-table) ;; describe the list as well (describe list))
- FORMAT on a list
(1 2 3)
- FORMAT on a hash-table
FOO => 42 BAR => 69
- WRITE
- readably t on a hash-table
- .(SB-IMPL::%STUFF-HASH-TABLE
(MAKE-HASH-TABLE :TEST 'EQL :SIZE '16 :REHASH-SIZE '1.5 :REHASH-THRESHOLD '1.0 :WEAKNESS 'NIL) '((BAR . 69) (FOO . 42)))
- DESCRIBE on a hash-table
- <HASH-TABLE :TEST EQL :COUNT 2 {1002B6F391}>
[hash-table]
Occupancy: 0.1 Rehash-threshold: 1.0 Rehash-size: 1.5 Size: 16 Synchronized: no
- DESCRIBE on a list
(3 2 1)
[list]
- No value</lang>
deque
In Lisp, a deque can be represented using two list variables which are understood to be opposite to each other. That is to say, the list links (cons cell cdr pointers) go inward into the deque from both ends. For instance the deque (1 2 3 4 5 6) can be represented using (1 2 3) and (6 5 4). Then, it is easy to push items on either end using ordinary list push operations. Popping is also simple, except when the case occurs that either piece runs out of items. A Lisp macro can be provided which takes care of this situation. The implementation below handles the underflow in one deque piece by transferring about one half of the elements from the opposite piece. This keeps the amortized cost for pushes and pops O(1), and prevents the degenerate behavior of bouncing all the elements from one side to the other when pops are requested which alternate between the two ends of the deque.
<lang lisp>
- Obtained from Usenet,
- Message-ID
- <b3b1cc90-2e2b-43c3-b7d9-785ae29870e7@e23g2000prf.googlegroups.com>
- Posting by Kaz Kylheku, February 28, 2008.
(eval-when (:compile-toplevel :load-toplevel :execute)
(defun bisect-list (list &optional (minimum-length 0)) (do ((double-skipper (cddr list) (cddr double-skipper)) (single-skipper list (cdr single-skipper)) (length 2 (+ length (if (cdr double-skipper) 2 1)))) ((null double-skipper) (cond ((< length minimum-length) (values list nil)) ((consp single-skipper) (multiple-value-prog1 (values list (cdr single-skipper)) (setf (cdr single-skipper) nil))) (t (values list nil))))))
(defun pop-deque-helper (facing-piece other-piece) (if (null facing-piece) (multiple-value-bind (head tail) (bisect-list other-piece 10) (let ((remaining (if tail head)) (moved (nreverse (or tail head)))) (values (first moved) (rest moved) remaining))) (values (first facing-piece) (rest facing-piece) other-piece))))
(defmacro pop-deque (facing-piece other-piece)
(let ((result (gensym)) (new-facing (gensym)) (new-other (gensym))) `(multiple-value-bind (,result ,new-facing ,new-other) (pop-deque-helper ,facing-piece ,other-piece) (psetf ,facing-piece ,new-facing ,other-piece ,new-other) ,result)))
</lang>
Demo:
[1]> (defvar *front* nil) *FRONT* [2]> (defvar *back* nil) *BACK* [3]> (push 1 *front*) (1) [4]> (push 2 *front*) (2 1) [5]> (push 5 *back*) (5) [6]> (push 6 *back*) (6 5) [7]> (append *front* (reverse *back*)) ;; display the deque! (2 1 5 6) [8]> (pop-deque *front* *back*) 2 [9]> (append *front* (reverse *back*)) ;; display the deque! (1 5 6) [10]> (pop-deque *back* *front*) 6 [11]> (append *front* (reverse *back*)) ;; display the deque! (1 5) [12]> (pop-deque *back* *front*) 5 [13]> (append *front* (reverse *back*)) ;; display the deque! (1) [14]> *front* (1) [15]> *back* NIL [16]> (pop-deque *back* *front*) 1 [17]> *front* NIL [18]> *back* NIL
D
D has static arrays. <lang d>int[3] array; array[0] = 5; // array.length = 4; // compile-time error</lang>
D has dynamic arrays. <lang d>int[] array; array ~= 5; // append 5 array.length = 3; array[3] = 17; // runtime error: out of bounds. check removed in release mode. array = [2, 17, 3]; writefln(array.sort); // 2, 3, 17</lang>
D has associative arrays. <lang d>int[int] array; // array ~= 5; // it doesn't work that way! array[5] = 17; array[6] = 20; // prints "[5, 6]" -> "[17, 20]" - although the order is not specified. writefln(array.keys, " -> ", array.values); assert(5 in array); // returns a pointer, by the way if (auto ptr = 6 in array) writefln(*ptr); // 20</lang>
E
E has both mutable and immutable builtin collections; the common types are list (array), map (hash table), and set (hash table). This interactive session shows mutable lists and immutable collections of all three types. See also Arrays#E.
<lang e>? def constList := [1,2,3,4,5]
- value: [1, 2, 3, 4, 5]
? constList.with(6)
- value: [1, 2, 3, 4, 5, 6]
? def flexList := constList.diverge()
- value: [1, 2, 3, 4, 5].diverge()
? flexList.push(6) ? flexList
- value: [1, 2, 3, 4, 5, 6].diverge()
? constList
- value: [1, 2, 3, 4, 5]
? def constMap := [1 => 2, 3 => 4]
- value: [1 => 2, 3 => 4]
? constMap[1]
- value: 2
? def constSet := [1, 2, 3, 2].asSet()
- value: [1, 2, 3].asSet()
? constSet.contains(3)
- value: true</lang>
Fancy
array
<lang fancy>
- creating an empty array and adding values
a = [] # => [] a[0]: 1 # => [1] a[3]: 2 # => [1, nil, nil, 2]
- creating an array with the constructor
a = Array new # => [] </lang>
hash
<lang fancy># creating an empty hash
h = <[]> # => <[]> h["a"]: 1 # => <["a" => 1]> h["test"]: 2.4 # => <["a" => 1, "test" => 2.4]> h[3]: "Hello" # => <["a" => 1, "test" => 2.4, 3 => "Hello"]>
- creating a hash with the constructor
h = Hash new # => <[]> </lang>
Forth
Array
<lang forth>include ffl/car.fs
10 car-create ar \ create a dynamic array with initial size 10
2 0 ar car-set \ ar[0] = 2 3 1 ar car-set \ ar[1] = 3 1 0 ar car-insert \ ar[0] = 1 ar[1] = 2 ar[2] = 3 </lang>
Double linked list
<lang forth>include ffl/dcl.fs
dcl-create dl \ create a double linked list
3 dl dcl-append 1 dl dcl-prepend 2 1 dl dcl-insert \ dl[0] = 1 dl[1] = 2 dl[2] = 3 </lang>
Hashtable
<lang forth>include ffl/hct.fs
10 hct-create ht \ create a hashtable with initial size 10
1 s" one" ht hct-insert \ ht["one"] = 1 2 s" two" ht hct-insert \ ht["two"] = 2 3 s" three" ht hct-insert \ ht["three"] = 3 </lang>
Go
Built in, resizable
- Slices
- Maps
Built in resizable collections are slices and maps. The value type for these collections can be any Go type, including interface. An empty interface can reference an object of any type, providing a kind of polymorphic collection. Here the variable a is a slice of interface{} objects. <lang go>package main
import "fmt"
func main() {
var a []interface{} a = append(a, 3) a = append(a, "apples", "oranges") fmt.Println(a)
}</lang> Output:
[3 apples oranges]
Built in, less conventional
- Go has arrays that can be used as collections, but arrays are declared with constant size and cannot be resized.
- Strings are a special case of slice. Strings are immutable and are handled specially in other ways.
- A struct with a number of members might be considered a collection in some sense.
- A buffered channel might be closer to the familiar concept of a collection, as it represents a FIFO queue. Buffered channels have a fixed size and cannot be resized after creation.
Library
- The container directory of the standard library has the packages heap, list, and ring.
- Anything that implements bufio.ReadWriter can be used as a FIFO queue. This includes bytes.Buffer, which makes a useful in-memory collection.
- The sort package also contains search functions which perform a binary search on a sorted collection. For these functions the collection implementation is abstracted through sort.Interface. It is typically a slice, but could be anything that is indexable with an integer index.
Groovy
Lists are just variable-length, integer-indexed arrays. <lang groovy>def emptyList = [] assert emptyList.isEmpty() : "These are not the items you're looking for" assert emptyList.size() == 0 : "Empty list has size 0" assert ! emptyList : "Empty list evaluates as boolean 'false'"
def initializedList = [ 1, "b", java.awt.Color.BLUE ] assert initializedList.size() == 3 assert initializedList : "Non-empty list evaluates as boolean 'true'" assert initializedList[2] == java.awt.Color.BLUE : "referencing a single element (zero-based indexing)" assert initializedList[-1] == java.awt.Color.BLUE : "referencing a single element (reverse indexing of last element)"
def combinedList = initializedList + [ "more stuff", "even more stuff" ] assert combinedList.size() == 5 assert combinedList[1..3] == ["b", java.awt.Color.BLUE, "more stuff"] : "referencing a range of elements"
combinedList << "even more stuff" assert combinedList.size() == 6 assert combinedList[-1..-3] == \
["even more stuff", "even more stuff", "more stuff"] \ : "reverse referencing last 3 elements"
println ([combinedList: combinedList])</lang>
Output:
[combinedList:[1, b, java.awt.Color[r=0,g=0,b=255], more stuff, even more stuff, even more stuff]]
Maps are just variable-length, associative arrays. They are not necessarily order preserving. <lang groovy>def emptyMap = [:] assert emptyMap.isEmpty() : "These are not the items you're looking for" assert emptyMap.size() == 0 : "Empty map has size 0" assert ! emptyMap : "Empty map evaluates as boolean 'false'"
def initializedMap = [ count: 1, initial: "B", eyes: java.awt.Color.BLUE ] assert initializedMap.size() == 3 assert initializedMap : "Non-empty map evaluates as boolean 'true'" assert initializedMap["eyes"] == java.awt.Color.BLUE : "referencing a single element (array syntax)" assert initializedMap.eyes == java.awt.Color.BLUE : "referencing a single element (member syntax)" assert initializedMap.height == null : \
"references to non-existant keys generally evaluate to null (implementation dependent)"
def combinedMap = initializedMap \
+ [hair: java.awt.Color.BLACK, birthdate: Date.parse("yyyy-MM-dd", "1960-05-17") ]
assert combinedMap.size() == 5
combinedMap["weight"] = 185 // array syntax combinedMap.lastName = "Smith" // member syntax combinedMap << [firstName: "Joe"] // entry syntax assert combinedMap.size() == 8 assert combinedMap.keySet().containsAll(
["lastName", "count", "eyes", "hair", "weight", "initial", "firstName", "birthdate"])
println ([combinedMap: combinedMap])</lang>
Output:
[combinedMap:[count:1, initial:B, eyes:java.awt.Color[r=0,g=0,b=255], hair:java.awt.Color[r=0,g=0,b=0], birthdate:Tue May 17 00:00:00 CDT 1960, weight:185, lastName:Smith, firstName:Joe]]
Sets are unique, not indexed at all (contents can only be discovered by traversal), and are not necessarily order preserving. There is no particular special language support for denoting a Set, although a Set may be initialized from a List, and Sets share many of the same operations and methods that are available in Lists. <lang groovy>def emptySet = new HashSet() assert emptySet.isEmpty() : "These are not the items you're looking for" assert emptySet.size() == 0 : "Empty set has size 0" assert ! emptySet : "Empty set evaluates as boolean 'false'"
def initializedSet = new HashSet([ 1, "b", java.awt.Color.BLUE ]) assert initializedSet.size() == 3 assert initializedSet : "Non-empty list evaluates as boolean 'true'" //assert initializedSet[2] == java.awt.Color.BLUE // SYNTAX ERROR!!! No indexing of set elements!
def combinedSet = initializedSet + new HashSet([ "more stuff", "even more stuff" ]) assert combinedSet.size() == 5
combinedSet << "even more stuff" assert combinedSet.size() == 5 : "No duplicate elements allowed!" println ([combinedSet: combinedSet])</lang>
Output:
[combinedSet:[1, java.awt.Color[r=0,g=0,b=255], b, even more stuff, more stuff]]
Haskell
Lists are written like so:
<lang haskell>[1, 2, 3, 4, 5]</lang>
To prepend a single element to a list, use the :
operator:
<lang haskell>1 : [2, 3, 4]</lang>
To concatenate two lists, use ++
:
<lang haskell>[1, 2] ++ [3, 4]</lang>
To concatenate a whole list of lists, use concat
:
<lang haskell>concat [[1, 2], [3, 4], [5, 6, 7]]</lang>
The list is by far Haskell's most important collection type, but there are others; see, for example, the Data
hierarchy of GHC's standard library. New collection types may be defined with data
.
Icon and Unicon
Icon and Unicon have a number of different types that could be considered collections. For more information see Introduction to Icon and Unicon on Rosetta - Data Types.
Several data types could be considered collections: <lang Icon># Creation of collections:
s := "abccd" # string, an ordered collection of characters, immutable c := 'abcd' # cset, an unordered collection of characters, immutable S := set() # set, an unordered collection of unique values, mutable, contents may be of any type T := table() # table, an associative array of values accessed via unordered keys, mutable, contents may be of any type L := [] # list, an ordered collection of values indexed by position 1..n or as stack/queue, mutable, contents may be of any type record constructorname(field1,field2,fieldetc) # record, a collection of values stored in named fields, mutable, contents may be of any type (declare outside procedures) R := constructorname() # record (creation)</lang>
Adding to these collections can be accomplished as follows: <lang Icon>
s ||:= "xyz" # concatenation c ++:= 'xyz' # union insert(S,"abc") # insert T["abc"] := "xyz" # insert create/overwrite put(L,1) # put (extend), also push R.field1 := "xyz" # overwrite</lang>
Additionally, the following operations apply: <lang Icon>
S := S ++ S2 # union of two sets or two csets S ++:= S2 # augmented assignment L := L ||| L2 # list concatenation L |||:= L2 # augmented assignment</lang>
J
J is an array-oriented language -- it treats all data as collections and processes collections natively. Its built in (primitive) functions are specifically designed to handle collections.
J will, when possible without losing significance of the original value, implicitly convert values to a type which allows them represented in a homogeneous fashion in a collection. Heterogeneous collections are possible via "boxing" (analogous to a "variant" data type).
<lang j> c =: 0 10 20 30 40 NB. A collection
c, 50 NB. Append 50 to the collection
0 10 20 30 40 50
_20 _10 , c NB. Prepend _20 _10 to the collection
_20 _10 0 10 20 30 40
,~ c NB. Self-append
0 10 20 30 40 0 10 20 30 40
,:~ c NB. Duplicate
0 10 20 30 40 0 10 20 30 40
30 e. c NB. Is 30 in the collection?
1
30 i.~c NB. Where?
3
30 80 e. c NB. Don't change anything to test multiple values -- collections are native.
1 0
2 1 4 2 { c NB. From the collection, give me items two, one, four, and two again.
20 10 40 20
|.c NB. Reverse the collection
40 30 20 10 0
1+c NB. Increment the collection
1 11 21 31 41
c%10 NB. Decimate the collection (divide by 10)
0 1 2 3 4
{. c NB. Give me the first item
0
{: c NB. And the last
40
3{.c NB. Give me the first 3 items
0 10 20
3}.c NB. Throw away the first 3 items
30 40
_3{.c NB. Give me the last 3 items
20 30 40
_3}.c NB. (Guess)
0 10
keys_map_ =: 'one';'two';'three' vals_map_ =: 'alpha';'beta';'gamma' lookup_map_ =: a:& $: : (dyad def ' (keys i. y) { vals,x')&boxopen exists_map_ =: verb def 'y e. keys'&boxopen
exists_map_ 'bad key'
0
exists_map_ 'two';'bad key'
1 0
lookup_map_ 'one'
+-----+ |alpha| +-----+
lookup_map_ 'three';'one';'two';'one'
+-----+-----+----+-----+ |gamma|alpha|beta|alpha| +-----+-----+----+-----+
lookup_map_ 'bad key'
++ || ++
'some other default' lookup_map_ 'bad key'
+------------------+ |some other default| +------------------+
'some other default' lookup_map_ 'two';'bad key'
+----+------------------+ |beta|some other default| +----+------------------+
+/ c NB. Sum of collection
100
*/ c NB. Product of collection
0
i.5 NB. Generate the first 5 nonnegative integers
0 1 2 3 4
10*i.5 NB. Looks familiar
0 10 20 30 40
c = 10*i.5 NB. Test each for equality
1 1 1 1 1
c -: 10 i.5 NB. Test for identicality
1</lang>
Java
When creating a List of any kind in Java (Arraylist or LinkedList), the type of the variable is a style choice. It is sometimes considered good practice to make the pointer of type List and the new object of a List subclass. Doing this will ensure two things: if you need to change the type of list you want you only need to change one line and all of your methods will still work, and you will not be able to use any methods that are specific to the List type you chose. So in this example, all instances of "ArrayList" can be changed to "LinkedList" and it will still work, but you will not be able to use a method like "ensureCapactiy()" because the variable is of type List.
<lang java5>List arrayList = new ArrayList(); arrayList.add(new Integer(0)); // alternative with primitive autoboxed to an Integer object automatically arrayList.add(0);
//other features of ArrayList //define the type in the arraylist, you can substitute a proprietary class in the "<>" List<Integer> myarrlist = new ArrayList<Integer>();
//add several values to the arraylist to be summed later int sum; for(int i = 0; i < 10; i++) {
myarrlist.add(i);
}</lang>
<lang java5>//loop through myarrlist to sum each entry for ( i = 0; i < myarrlist.size(); i++) {
sum += myarrlist.get(i);
}</lang> or <lang java5>for(int i : myarrlist) {
sum += i;
}</lang>
<lang java5>//remove the last entry in the ArrayList myarrlist.remove(myarrlist.size()-1)
//clear the ArrayList
myarrlist.clear();</lang>
Here is a reference table for characteristics of commonly used Collections
classes:
Collection class | random access | order | iterator direction |
---|---|---|---|
HashMap | by key | hash | forward (separate iterators for entries, keys and values) |
TreeMap | by key | ascending(key) | forward (separate iterators for entries, keys and values) |
LinkedHashMap | by key | insertion | forward (separate iterators for entries, keys and values) |
LinkedList | by index | insertion/to index | both |
ArrayList | by index | insertion/to index (ArrayList also has a defined but expandable size) | both |
HashSet | only remove (returns the element that was removed) | hash | forward |
TreeSet | only remove (returns the element that was removed) | ascending(element) | forward |
JavaScript
<lang javascript>var array = []; array.push('abc'); array.push(123); array.push(new MyClass); alert( array[2] );</lang>
<lang javascript>var map = {}; map['foo'] = 'xyz'; //equivalent to: map.foo = 'xyz'; map['bar'] = new MyClass; //equivalent to: map.bar = new MyClass; map['1x; ~~:-b'] = 'text'; //no equivalent alert( map['1x; ~~:-b'] );</lang>
Lisaac
vector
<lang Lisaac>+ vector : ARRAY[INTEGER]; vector := ARRAY[INTEGER].create_with_capacity 32 lower 0; vector.add_last 1; vector.add_last 2;</lang>
hashed set
<lang Lisaac>+ set : HASHED_SET[INTEGER]; set := HASHED_SET[INTEGER].create; set.add 1; set.add 2;</lang>
linked list
<lang Lisaac>+ list : LINKED_LIST[INTEGER]; list := LINKED_LIST[INTEGER].create; list.add_last 1; list.add_last 2;</lang>
hashed dictionary
<lang Lisaac>+ dict : HASHED_DICTIONARY[INTEGER/*value*/, STRING_CONSTANT/*key*/]; dict := HASHED_DICTIONARY[INTEGER, STRING_CONSTANT].create; dict.put 1 to "one"; dict.put 2 to "two";</lang>
Logo
Logo has a list-like protocol (first, butfirst, etc.) which works on three different data types:
- members of a list: [one two three]
- items in an array: {one two three}
- characters in a word: "123
Lua
Lua has only one type of collection, the table. But Lua's table has features of both, traditional arrays and hash maps (dictionaries). You can even mix both within one table. Note, that the numeric indices of Lua's table start at 1, not at 0 as with most other languages.
<lang lua>collection = {0, '1'} print(collection[1]) -- prints 0
collection = {["foo"] = 0, ["bar"] = '1'} -- a collection of key/value pairs print(collection["foo"]) -- prints 0 print(collection.foo) -- syntactic sugar, also prints 0
collection = {0, '1', ["foo"] = 0, ["bar"] = '1'}</lang>
It is idiomatic in Lua to represent a Set data structure with a table of keys to the true value.
Mathematica
<lang Mathematica>Lst = {3, 4, 5, 6} ->{3, 4, 5, 6}
PrependTo[ Lst, 2] ->{2, 3, 4, 5, 6} PrependTo[ Lst, 1] ->{1, 2, 3, 4, 5, 6}
Lst ->{1, 2, 3, 4, 5, 6}
Insert[ Lst, X, 4] ->{1, 2, 3, X, 4, 5, 6}</lang>
MATLAB / Octave
MATLAB cell-arrays perform this function. They are indexed like arrays, but are able to hold any data type. In any cell simultaneously with any other data type. In essence they cell-arrays are sets.
Sample Usage: <lang MATLAB>>> A = {2,'TPS Report'} %Declare cell-array and initialize
A =
[2] 'TPS Report'
>> A{2} = struct('make','honda','year',2003)
A =
[2] [1x1 struct]
>> A{3} = {3,'HOVA'} %Create and assign A{3}
A =
[2] [1x1 struct] {1x2 cell}
>> A{2} %Get A{2}
ans =
make: 'honda' year: 2003</lang>
Bold text
Objective-C
OpenStep (and derivates like GNUstep and Cocoa) has several collection classes; here we show
- a set: a collection of unique elements (like mathematical set). Possible operations on a set are not shown;
- a counted set (also known as bag): each elements have a counter that says how many time that element appears;
- a dictionary: pairs key-value.
Arrays (indexed by an integer), which are also collections, are not shown here.
<lang objc>#import <Foundation/Foundation.h>
void show_collection(id coll) {
id el; NSEnumerator *en; if ( [coll respondsToSelector: @selector(keyEnumerator)] ) { en = [coll keyEnumerator]; } else { en = [coll objectEnumerator]; } while( (el = [en nextObject]) != nil) { if ( [coll respondsToSelector: @selector(countForObject:)] ) { NSLog(@"%@ appears %d times", el, [coll countForObject: el]); } else if ( [coll isKindOfClass: [NSDictionary class]] ) { NSLog(@"%@ -> %@", el, [coll valueForKey: el]); } else { NSLog(@"%@", el); } } printf("\n");
}
int main() {
NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init]; // create an empty set NSMutableSet *set = [[NSMutableSet alloc] init]; // populate it [set addObject: @"one"]; [set addObject: [NSNumber numberWithInt: 10]]; [set addObjectsFromArray: [NSArray arrayWithObjects: @"one",
[NSNumber numberWithInt: 20], [NSNumber numberWithInt: 10], @"two", nil] ];
// let's show it show_collection(set);
// create an empty counted set (a bag) NSCountedSet *cset = [[NSCountedSet alloc] init]; // populate it [cset addObject: @"one"]; [cset addObject: @"one"]; [cset addObject: @"two"]; // show it show_collection(cset);
// create a dictionary NSMutableDictionary *dict = [[NSMutableDictionary alloc] init]; // populate it [dict setValue: [NSNumber numberWithInt: 4] forKey: @"four"]; [dict setValue: [NSNumber numberWithInt: 8] forKey: @"eight"]; // show it show_collection(dict);
[pool release]; return EXIT_SUCCESS;
}</lang>
Output (stripped the left-sided log info):
two 20 10 one two appears 1 times one appears 2 times eight -> 8 four -> 4
Objeck
vector
<lang objeck> values := IntVector->New(); values->AddBack(7); values->AddBack(3); values->AddBack(10); </lang>
linked list
<lang objeck> values := IntList->New(); values->AddBack(7); values->AddBack(3); values->AddBack(10); </lang>
hash
<lang objeck> values := StringHash->New(); values->Insert("seven", IntHolder->New(7)); values->Insert("three", IntHolder->New(3)); values->Insert("ten", IntHolder->New(10)); </lang>
stack
<lang objeck> values := IntStack->New(); values->Push(7); values->Push(3); values->Push(10); </lang>
OCaml
Lists are written like so: <lang ocaml>[1; 2; 3; 4; 5]</lang>
To prepend a single element to a list, use the :: operator: <lang ocaml>1 :: [2; 3; 4; 5]</lang>
To concatenate two lists, use @: <lang ocaml>[1; 2] @ [3; 4; 5]</lang>
To concatenate a whole list of lists, use List.flatten:
<lang ocaml># List.flatten [[1; 2]; [3; 4]; [5; 6; 7]] ;; - : int list = [1; 2; 3; 4; 5; 6; 7]</lang>
Being a functional programming language, the list is one of the most important collection type. And being an impure functional programming language there are also imperative collection type, as for example, arrays: <lang ocaml>[| 1; 2; 3; 4; 5 |]</lang>
Oz
The most important collection types are lists, records, dictionaries and arrays: <lang oz>declare
%% Lists (immutable, recursive) Xs = [1 2 3 4] %% Add element at the front (cons) Xs0 = 0|Xs {Show {Length Xs}} %% output: 4
%% Records (immutable maps with a label) Rec = label(1:2 symbol:3) {Show Rec} %% output: label(2 symbol:3) {Show Rec.1} %% output: 2 %% create a new record with an added field Rec2 = {AdjoinAt Rec 2 value} {Show Rec2} %% output: label(2 value symbol:3)
%% Dictionaries (mutable maps) Dict = {Dictionary.new} Dict.1 := 1 Dict.symbol := 3 {Show Dict.1} %% output: 1
%% Arrays (mutable with integer keys) Arr = {Array.new 1 10 initValue} Arr.1 := 3 {Show Arr.1} %% output: 3</lang>
There are also tuples (records with consecutive integer keys starting with 1), weak dictionaries, queues and stacks.
PARI/GP
Pari has vectors, column vectors, matrices, sets, lists, and small vectors. <lang parigp>v = vector(0); v = []; cv = vectorv(0); cv = []~; m = matrix(1,1); s = Set(v); l = List(v); vs = vectorsmall(0);</lang> Adding members: <lang parigp>listput(l, "hello world") v=concat(v, [1,2,3]); v=concat(v, 4);</lang>
Perl
Perl has array and hashes.
<lang perl>use strict; my @c = (); # create an empty "array" collection
- fill it
push @c, 10, 11, 12; push @c, 65;
- print it
print join(" ",@c) . "\n";
- create an empty hash
my %h = ();
- add some pair
$h{'one'} = 1; $h{'two'} = 2;
- print it
foreach my $i ( keys %h ) {
print $i . " -> " . $h{$i} . "\n";
}</lang>
Perl 6
Perl 6 has both mutable and immutable containers of various sorts. Here are some of the more common ones:
Array (mutable)
<lang perl6>my @array = 1,2,3; @array.push: 4,5,6;</lang>
Hash (mutable)
<lang perl6>my %hash = a => 1, b => 2; %hash<c d> = 3,4; %hash.push: e => 5, f => 6;</lang>
List (immutable)
<lang perl6>my @list := 1,2,3; my @newlist := @list, 4,5,6;</lang>
Set (immutable)
<lang perl6>my $set = set <a b c>; my $newset = $set ∪ <d e f>;</lang>
KeySet (mutable)
<lang perl6>my $s = KeySet.new: <a b c>; $s ∪= <d e f>;</lang>
Bag (immutable)
<lang perl6>my $bag = bag ; my $newbag = $bag ∪ ;</lang>
KeyBag (mutable)
<lang perl6>my $b = KeySet.new: ; $b ∪= <d e f>;</lang>
Pair list (cons list)
<lang perl6>my $tail = d => e => f => Nil; my $new = a => b => c => $tail;</lang>
P6opaque object (immutable in structure)
<lang perl6>my $obj = Something.new: foo => 1, bar => 2; my $newobj = $obj but role { has $.baz = 3 } # anonymous mixin</lang>
PHP
PHP has associative arrays as collection
<lang php><?php $a = array();
- add elements "at the end"
array_push($a, 55, 10, 20); print_r($a);
- using an explicit key
$a['one'] = 1; $a['two'] = 2; print_r($a); ?></lang>
Output:
Array ( [0] => 55 [1] => 10 [2] => 20 ) Array ( [0] => 55 [1] => 10 [2] => 20 [one] => 1 [two] => 2 )
PicoLisp
The direct way in PicoLisp is a linear list (other possibilities could involve index trees or property lists). <lang PicoLisp>: (setq Lst (3 4 5 6)) -> (3 4 5 6)
- (push 'Lst 2)
-> 2
- (push 'Lst 1)
-> 1
- Lst
-> (1 2 3 4 5 6)
- (insert 4 Lst 'X)
-> (1 2 3 X 4 5 6)</lang>
PureBasic
Arrays
Creating an Array of 10 strings (could be any type). PureBasic starts the index with element 0. <lang PureBasic>Dim Text.s(9)
Text(3)="Hello" Text(7)="World!"</lang>
Linked Lists
Create a Linked List for strings (could be any type), then add two elements. <lang PureBasic>NewList Cars.s()
AddElement(Cars()): Cars()="Volvo" AddElement(Cars()): Cars()="BMV"</lang>
Hash table
Create a Map, e.g. a hash table that could be any type. The size of the dictionary can be defined as needed, otherwise a default value is used. <lang PureBasic>NewMap Capitals.s()
Capitals("USA") = "Washington" Capitals("Sweden")= "Stockholm"</lang>
Python
Python supports lists, tuples, dictionaries and now sets as built-in collection types. See http://docs.python.org/tut/node7.html for further details. <lang python>collection = [0, '1'] # Lists are mutable (editable) and can be sorted in place x = collection[0] # accessing an item (which happens to be a numeric 0 (zero) collection.append(2) # adding something to the end of the list collection.insert(0, '-1') # inserting a value into the beginning y = collection[0] # now returns a string of "-1" collection.extend([2,'3']) # same as [collection.append(i) for i in [2,'3']] ... but faster collection += [2,'3'] # same as previous line collection[2:6] # a "slice" (collection of the list elements from the third up to but not including the sixth) len(collection) # get the length of (number of elements in) the collection collection = (0, 1) # Tuples are immutable (not editable) collection[:] # ... slices work on these too; and this is equivalent to collection[0:len(collection)] collection[-4:-1] # negative slices count from the end of the string collection[::2] # slices can also specify a stride --- this returns all even elements of the collection collection="some string" # strings are treated as sequences of characters x = collection[::-1] # slice with negative step returns reversed sequence (string in this case). collection[::2] == "some string"[::2] # True, literal objects don't need to be bound to name/variable to access slices or object methods collection.__getitem__(slice(0,len(collection),2)) # same as previous expressions. collection = {0: "zero", 1: "one"} # Dictionaries (Hash) collection['zero'] = 2 # Dictionary members accessed using same syntax as list/array indexes. collection = set([0, '1']) # sets (Hash)</lang>
In addition Python classes support a number of methods allowing them to implement indexing, slicing, and attribute management features as collections. Thus many modules in the Python standard libraries allow one to treat files contents, databases, and other data using the same syntax as the native collection types. Some Python modules (such as Numeric and NumPy) provide low-level implementations of additional collections (such as efficient n-dimensional arrays).
R
R has several types that can be considered collections.
Vectors
Numeric (floating point) <lang R>numeric(5) 1:10 c(1, 3, 6, 10, 7 + 8, sqrt(441))</lang>
[1] 0 0 0 0 0 [1] 1 2 3 4 5 6 7 8 9 10 [1] 1 3 6 10 15 21
Integer <lang R>integer(5) c(1L, -2L, 99L);</lang>
[1] 0 0 0 0 0 [1] 1 -2 99
Logical <lang R>logical(5) c(TRUE, FALSE)</lang>
[1] FALSE FALSE FALSE FALSE FALSE [1] TRUE FALSE
Character <lang R>character(5) c("abc", "defg", "")</lang>
[1] "" "" "" "" "" [1] "abc" "defg" ""
Arrays and Matrices
These are essentially vectors with a dimension attribute. Matrices are just arrays with two dimensions (and a different class). <lang R>matrix(1:12, nrow=3)
array(1:24, dim=c(2,3,4)) #output not shown</lang>
[,1] [,2] [,3] [,4] [1,] 1 4 7 10 [2,] 2 5 8 11 [3,] 3 6 9 12
Lists
Lists are collections of other variables (that can include other lists). <lang R>list(a=123, b="abc", TRUE, 1:5, c=list(d=runif(5), e=5+6))</lang> <lang r>$a [1] 123 $b [1] "abc" 3 [1] TRUE 4 [1] 1 2 3 4 5 $c $c$d [1] 0.6013157 0.5011909 0.7106448 0.3882265 0.1274939 $c$e [1] 11</lang>
Data Frames
Data frames are like a cross between a list and a matrix. Each row represents one "record", or a collection of variables. <lang R>data.frame(name=c("Alice", "Bob", "Carol"), age=c(23, 35, 17))</lang>
name age 1 Alice 23 2 Bob 35 3 Carol 17
Raven
Numerically indexed List:
<lang raven>[ 1 2 3 'abc' ] as a_list a_list print
list (4 items)
0 => 1 1 => 2 2 => 3 3 => "abc"</lang>
String key indexed Hash:
<lang raven>{ 'a' 1 'b' 2 } as a_hash a_hash print
hash (2 items)
a => 1 b => 2</lang>
Set items:
<lang raven>17 a_list 1 set # set second item 42 a_hash 'b' set # set item with key 'b' 42 a_hash:b # shorthand</lang>
Get items:
<lang raven>a_list 1 get # get second item a_hash 'b' get # get item with key 'b' a_hash.b # shorthand</lang>
Other stuff:
<lang raven>42 a_list push # append an item a_list pop # remove last item 42 a_list shove # prepend an item a_list shift # remove first item 42 a_list 1 insert # insert item second, shuffling others down a_list 1 remove # retrieve second item, shuffling others up</lang>
REXX
There are several ways to store collections in REXX:
- stemmed arrays
- lists or vectors
- sparse stemmed arrays
stemmed arrays
To store (say) a collection of numbers (or anything, for that matter) into a stemmed array: <lang rexx>pr.=0 /*define a default for all elements for the stemmed array.*/ pr.1 =2 pr.2 =3 pr.3 =5 pr.4 =7 pr.6 =11 pr.6 =13 pr.7 =17 pr.8 =19 pr.9 =23 pr.10=29 pr.11=31 pr.12=37 pr.13=41 pr.14=43</lang> Most often, programmers will assign the zeroeth entry to the number of elements in the stemmed array: <lang ress> pr.0=14 /*number of entries in the stemmed array.*/</lang> Programatically, a simple test could be performed to detect the end of the array: <lang rexx> do j=1 while pr.j\==0
say 'prime' j 'is' pr.j end /*at this point, J=15. */
j=j-1 /*J now has the count of primes stored.*/</lang>
lists or vectors
To store (say) a collection of numbers (or anything, for that matter) into a list: <lang rexx>primeList='2 3 5 7 11 13 17 19 23 29 31 37 41 43' /* or ... */ primeList= 2 3 5 7 11 13 17 19 23 29 31 37 41 43
/*in this case, the quotes (') can be dropped. */
primes=words(primeList)
do j=1 for primes /*can also be coded: do j=1 to primes */ say 'prime' j 'is' word(primeList,j) end</lang>
sparse stemmed arrays
To store (say) a collection of numbers (or anything, for that matter) into a sparse stemmed array: <lang rexx>pr.=0 /*define a default for all elements for the stemmed array.*/ pr.2 =1 pr.3 =1 pr.5 =1 pr.7 =1 pr.11=1 pr.13=1 pr.17=1 pr.19=1 pr.23=1 pr.29=1 pr.31=1 pr.37=1 pr.41=1 pr.43=1 primes=0
do j=1 for 10000 /*this method isn't very efficent*/ if pr.j==0 then iterate primes=primes+1 end
say '# of primes in list:' primes
Ps=0 /*another inefficient method. */
do j=1 for 10000 /*this method isn't very efficent*/ Ps = Ps + (pn.j\==0) /*more obtuse, if ya like that. */ say 'prime' Ps "is:" j /*might as well echo the prime #.*/ end
say 'number of primes found in the list is' Ps</lang>
Ruby
array
<lang ruby># creating an empty array and adding values
a = [] # => [] a[0] = 1 # => [1] a[3] = 2 # => [1, nil, nil, 2]
- creating an array with the constructor
a = Array.new # => []</lang>
hash
<lang ruby># creating an empty hash
h = {} # => {} h["a"] = 1 # => {"a" => 1} h["test"] = 2.4 # => {"a" => 1, "test" => 2.4} h[3] = "Hello" # => {"a" => 1, "test" => 2.4, 3 => "Hello"}
- creating a hash with the constructor
h = Hash.new # => {}</lang>
Scala
All the code below was written with a nightly build of Scala 2.8. That version, when it comes out, will introduce a completely revised collection librarya and, because of that, the examples may not work on Scala 2.7.
These examples were taken from a Scala REPL session.
<lang scala>scala> // Immutable collections do not change the original object scala> // A List scala> val list = Nil // Empty List list: scala.collection.immutable.Nil.type = List() scala> val list2 = List(1, 2) // List with two elements list2: List[Int] = List(1, 2) scala> val list3 = 3 :: list2 // prepend 3 to list2, using a special operator list3: List[Int] = List(3, 1, 2) scala> // A Set scala> val set = Set.empty[Char] // Empty Set of Char type set: scala.collection.immutable.Set[Char] = Set() scala> val set1 = set + 'c' // add an element set1: scala.collection.immutable.Set[Char] = Set(c) scala> // A Map scala> val map = Map(1 -> "A") map: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> A) scala> val map1 = map + (2 -> "Map") map1: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> A, 2 -> Map) scala> // Mutable collections can be modified scala> val queue = new scala.collection.mutable.Queue[Int] queue: scala.collection.mutable.Queue[Int] = Queue() scala> queue += 4 res0: queue.type = Queue(4) scala> queue += 5 res1: queue.type = Queue(4, 5) scala> queue res2: scala.collection.mutable.Queue[Int] = Queue(4, 5) scala> val set = scala.collection.mutable.Set('a') set: scala.collection.mutable.Set[Char] = Set(a) scala> set += 'b' res3: set.type = Set(b, a) scala> val map = scala.collection.mutable.Map(1 -> "one") map: scala.collection.mutable.Map[Int,java.lang.String] = Map(1 -> one) scala> map += (2 -> "two") res4: map.type = Map(2 -> two, 1 -> one) scala> map res5: scala.collection.mutable.Map[Int,java.lang.String] = Map(2 -> two, 1 -> one)</lang>
Scheme
list
<lang scheme>(list obj ...)</lang> returns a newly allocated list of its arguments.
Example: <lang scheme>(display (list 1 2 3)) (newline) (display (list)) (newline)</lang> Output: <lang>(1 2 3) ()</lang>
cons
<lang scheme>(cons obj lst)</lang>
returns a newly allocated list consisting of obj
prepended to lst
.
Example: <lang scheme>(display (cons 0 (list 1 2 3))) (newline)</lang> Output: <lang>(0 1 2 3)</lang>
append
<lang scheme>(append lst ...)</lang>
returns a newly allocated list consisting of the elements of lst
followed by the elements of the other lists.
Example: <lang scheme>(display (append (list 1 2 3) (list 4 5 6))) (newline)</lang> Output: <lang>(1 2 3 4 5 6)</lang>
Slate
<lang slate>{1. 2. 3. 4. 5} collect: [|:x| x + 1]. "--> {2. 3. 4. 5. 6}" {1. 2. 3. 4. 5} select: #isOdd `er. "--> {1. 3. 5}" ({3. 2. 7} collect: #+ `er <- 3) sort. "--> {"SortedArray traitsWindow" 5. 6. 10}" ExtensibleArray new `>> [addLast: 3. addFirst: 4. ]. "--> {"ExtensibleArray traitsWindow" 4. 3}"</lang>
Seed7
set
<lang seed7>$ include "seed7_05.s7i";
enable_output(set of string);
const proc: main is func
local var set of string: aSet is {"iron", "copper"}; begin writeln(aSet); incl(aSet, "silver"); writeln(aSet); end func;</lang>
array
<lang seed7>$ include "seed7_05.s7i";
const proc: main is func
local var array string: anArray is [] ("iron", "copper"); var string: element is ""; begin for element range anArray do write(element <& " "); end for; writeln; anArray &:= "silver"; for element range anArray do write(element <& " "); end for; writeln; end func;</lang>
hash
<lang seed7>$ include "seed7_05.s7i";
const type: aHashType is hash [string] string;
const proc: main is func
local var aHashType: aHash is aHashType.value; var string: aValue is ""; var string: aKey is ""; begin aHash @:= ["gold"] "metal"; aHash @:= ["helium"] "noble gas"; for aValue key aKey range aHash do writeln(aKey <& ": " <& aValue); end for; end func;</lang>
Smalltalk
Smalltalk has several collection classes (indeed the class Collection is the parent of a long list of subclasses), being the word collection rather generic (an array indexed by integers is a collection too, and in some languages it's the only primitive collection available).
In this code I show how to add elements (which for each collection kind can be mixed) to five kind of Smalltalk collection:
- OrderedCollection: elements are kept in the order they are added;
- Bag: for each element, a count of how many times it appears is kept. So objects appear only once, but we can know how many we added in the bag;
- Set: a set. Elements appear only once, adding an existing object won't change the set; if we want to know if we added the same object several time, we use a Bag;
- SortedCollection: elements-objects are sorted (every comparable object can be added, and if we want different sorting criteria, we can give our custom comparator through sortBlock);
- Dictionary: objects are indexed by an arbitrary key, e.g. a string
<lang smalltalk>|anOrdered aBag aSet aSorted aSorted2 aDictionary|
anOrdered := OrderedCollection new. anOrdered add: 1; add: 5; add: 3. anOrdered printNl.
aBag := Bag new. aBag add: 5; add: 5; add: 5; add: 6. aBag printNl.
aSet := Set new. aSet add: 10; add: 5; add: 5; add: 6; add: 10. aSet printNl.
aSorted := SortedCollection new. aSorted add: 10; add: 9; add: 8; add: 5. aSorted printNl.
"another sorted with custom comparator: let's sort
the other collections according to their size (number of elements)"
aSorted2 := SortedCollection sortBlock: [ :a :b |
(a size) < (b size) ].
aSorted2 add: anOrdered; add: aBag; add: aSet; add: aSorted. aSorted2 printNl.
aDictionary := Dictionary new. aDictionary at: 'OrderedCollection' put: anOrdered;
at: 'Bag' put: aBag; at: 'Set' put: aSet; at: 'SortedCollection' put: { aSorted. aSorted2 }.
aDictionary printNl.</lang>
Output:
OrderedCollection (1 5 3 ) Bag(5:3 6:1 ) Set (10 5 6 ) SortedCollection (5 8 9 10 ) SortedCollection (Set (10 5 6 ) OrderedCollection (1 5 3 ) Bag(5:3 6:1 ) SortedCollection (5 8 9 10 ) ) Dictionary ( 'SortedCollection'->(SortedCollection (5 8 9 10 ) SortedCollection (Set (10 5 6 ) OrderedCollection (1 5 3 ) Bag(5:3 6:1 ) SortedCollection (5 8 9 10 ) ) ) 'OrderedCollection'->OrderedCollection (1 5 3 ) 'Set'->Set (10 5 6 ) 'Bag'->Bag(5:3 6:1 ) )
Tcl
Tcl has 3 fundamental collection types: list, array and dictionary.
A Tcl list is called an array in other languages (an integer-indexed list of values). <lang tcl>set c [list] ;# create an empty list
- fill it
lappend c 10 11 13 set c [linsert $c 2 "twelve goes here"]
- iterate over it
foreach elem $c {puts $elem}
- pass to a proc
proc show_size {l} {
puts [llength $l]
} show_size $c</lang>
A Tcl array is an associative array (aka hash). Arrays are collections of variables indexable by name, and not collections of values. An array cannot be passed to a procedure be value: it must either be passed by name or by its serialized representation. Tcl arrays also are strictly one-dimensional: arrays cannot be nested. However, multi-dimensional arrays can be simulated with cleverly constructed key strings.
<lang tcl># create an empty array array set h {}
- add some pair
set h(one) 1 set h(two) 2
- add more data
array set h {three 3 four 4 more {5 6 7 8}}
- iterate over it in a couple of ways
foreach key [array names h] {puts "$key -> $h($key)"} foreach {key value} [array get h] {puts "$key -> $value"}
- pass by name
proc numkeys_byname {arrayName} {
upvar 1 $arrayName arr puts "array $arrayName has [llength [array names arr]] keys"
} numkeys_byname h
- pass serialized
proc numkeys_bycopy {l} {
array set arr $l puts "array has [llength [array names arr]] keys"
} numkeys_bycopy [array get h]</lang>
A Tcl dictionary is an associative array value that contains other values. Hence dictionaries can be nested and arbitrarily deep data structures can be created.
<lang tcl># create an empty dictionary set d [dict create] dict set d one 1 dict set d two 2
- create another
set e [dict create three 3 four 4] set f [dict merge $d $e] dict set f nested [dict create five 5 more [list 6 7 8]] puts [dict get $f nested more] ;# ==> 6 7 8</lang>
TUSCRIPT
<lang tuscript> $$ MODE TUSCRIPT
collection=* DATA apple DATA banana DATA orange
morestuff=* DATA peaches DATA apple
collection=APPEND(collection,morestuff) TRACE *collection </lang> Output:
collection = * 1 = apple 2 = banana 3 = orange 4 = peaches 5 = apple
Ursala
There are several kinds of collections in Ursala that are supported by having their own operators and type constructors associated with them. All storage is immutable, but one may "add" to a collection by invoking a function that returns a new collection from it. The examples shown below populate the collections with primitive types expressed literally, but they could also be aggregate or abstract types, functions, symbolic names or expressions.
Lists
Lists are written as comma-separated sequences enclosed in angle brackets, or with the head and tail separated by a colon. <lang Ursala>x = <1,5,6> y = <'foo','bar'> z = 3:<6,8></lang> This function takes a pair of a new head and an existing list, and returns one that has the new head "added" to it. <lang Ursala>foo ("newhead","existing-list") = "newhead":"existing-list"</lang>
Sets
Sets are comma separated sequences enclosed in braces. The order and multiplicities of elements are ignored, so that the followng declarations are equivalent. <lang Ursala>x = {'a','b'} y = {'b','a'} z = {'a','b','a'}</lang>
Modules
Modules are lists in a particular form used to represent key:value pairs, with the key being a character string. <lang Ursala>m = <'foo': 1,'bar': 2,'baz': 3></lang> A module or any list of pairs can be reified into a function (a.k.a., a hash or finite map) and used in any context where a function is usable, assuming the keys are mutually distinct.
Trees
Trees are written in the form ^:
,
where is the root and is a list of subtrees, which can
be of any length.
<lang Ursala>x =
'z'^: <
'x'^: < '7'^: <>, '?'^: <'D'^: <>>>, 'a'^: <'E'^: <>,'j'^: <>>, 'b'^: <'i'^: <>>, 'c'^: <>></lang>
A-trees
A-trees allow faster access than trees by using a different representation wherein data are stored only in the leaves at a constant depth. <lang Ursala>x =
[
4:0: 'foo', 4:1: 'bar', 4:2: 'baz', 4:3: 'volta', 4:4: 'pramim']</lang>
Grids
Grids are similar to lists of A-trees satisfying certain additional invariants. They represent a rooted, directed graph in which the nodes are partitioned by levels and edges exist only between nodes in consecutive levels. This type of data structure is ubiquitous in financial derivatives applications.
This example shows a grid of floating point numbers. The colon separated numbers (e.g., 4:10) are used in grids of any type as addresses, with each node including a list of the addresses of its descendents in the next level.
<lang Ursala>g =
<
[0:0: -9.483639e+00^: <4:10,4:14>], [ 4:14: -9.681900e+00^: <4:15>, 4:10: 2.237330e+00^: <4:7>], [ 4:15: -2.007562e+00^: <5:5>, 4:7: 2.419021e+00^: <5:5,5:15>], [ 5:15: 8.215451e+00^: <11:118>, 5:5: 4.067704e+00^: <11:741>], [ 11:741: -7.608967e+00^: <8:68>, 11:118: -1.552837e+00^: <8:68,8:208>], [ 8:208: 5.348115e+00^: <4:7,4:9,4:12>, 8:68: -9.066821e+00^: <4:9,4:12>], [ 4:12: -3.460494e+00^: <>, 4:9: 2.840319e+00^: <>, 4:7: -2.181140e+00^: <>]></lang>
V
A quote is used for the same purpose in V <lang v>[4 3 2 1] 5 swap cons =[5 4 3 2 1]</lang>
Visual Basic .NET
<lang vbnet>Dim toys As New List(Of String) toys.Add("Car") toys.Add("Boat") toys.Add("Train")</lang>