Collections
From Rosetta Code
You are encouraged to solve this task according to the task description, using any language you may know.
Collections are abstractions to represent sets of values. In statically-typed languages, the values are typically of a common data type.
Create a collection, and add a few values to it.
[edit] 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).
[edit] 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.
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;
[edit] 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.
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;
[edit] 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.
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;
[edit] doubly linked lists
Works with: Ada 2005 Library: Ada.Containers.Doubly_Linked_Lists
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;
[edit] vectors
Works with: Ada 2005 Library: Ada.Containers.Vectors
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;
[edit] AWK
In awk, the closest thing to collections would be arrays. They are created when needed at assignment
a[0]="hello"
or by splitting a string
split("one two three",a)
Single elements are accessible with the bracket notation, like in C:
print a[0]
One can iterate over the elements of an array:
for(i in a) print i":"a[i]
[edit] 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).
[edit] 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).
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)
[edit] 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.
#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
[edit] 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.
#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
[edit] 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.
#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
[edit] 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).
#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)
[edit] multiset
A multiset is like a set, except the same element may occur multiple times.
#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)
[edit] C#
[edit] Arrays
// 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";
[edit] ArrayList and List
The size of ArrayList is dynamically increased as required. ArrayLists are zero-based.
//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("!");
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).
//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("!");
[edit] 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.
//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");
Dictionary is a generic class.It represents a collection of key/value pairs. Keys must be unique.
//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");
[edit] Common 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
[edit] D
D has static arrays.
int[3] array;
array[0] = 5;
// array.length = 4; // compile-time error
D has dynamic arrays.
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
D has associative arrays.
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
[edit] 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.
? 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
[edit] Fancy
[edit] array
# 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; # => []
[edit] hash
# 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; # => <[]>
[edit] Haskell
Lists are written like so:
[1, 2, 3, 4, 5]
To prepend a single element to a list, use the : operator:
1 : [2, 3, 4]
To concatenate two lists, use ++:
[1, 2] ++ [3, 4]
To concatenate a whole list of lists, use concat:
concat [[1, 2], [3, 4], [5, 6, 7]]
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.
[edit] 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.
[edit] Icon
Several data types could be considered collections:
# 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)
Adding to these collections can be accomplished as follows:
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
Additionally, the following operations apply:
S := S ++ S2 # union of two sets or two csets
S ++:= S2 # augmented assignment
L := L ||| L2 # list concatenation
L |||:= L2 # augmented assignment
[edit] Unicon
The Icon solution works in Unicon.
[edit] 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 is weakly typed, and hetergenous collections are possible via "boxing" (analogous to a "variant" data type).
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
[edit] Java
Works with: Java version 1.5+
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.
List arrayList = new ArrayList();
arrayList.add(new Integer(0));
//other features of ArrayList
//define the type in the arraylist, you can substitute a proprietary class in the "<>"
private List<Integer> myarrlist;
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);
}
//loop through myarrlist to sum each entry
for(i=0; i<myarrlist.size(); i++)
{
sum+=myarrlist.get(i);
}
or
for(int i:myarrlist){
sum+= i;
}
//remove the last entry in the ArrayList
myarrlist.remove(myarrlist.size()-1)
//clear the ArrayList
myarrlist.clear();
Here is a reference table for characteristics of commonly used Collections classes:
| Collection class | random access | order | iterator direction |
|---|---|---|---|
| HashMap | by key | hash | no iterator (except for separate key sets or value lists) |
| TreeMap | by key | ascending(key) | no iterator (except for separate key sets or value lists) |
| LinkedHashMap | by key | insertion | no iterator (except for separate key sets or value lists) |
| 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 |
[edit] JavaScript
var array = [];
array.push('abc');
array.push(123);
array.push(new MyClass);
alert( array[2] );
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'] );
[edit] Lisaac
[edit] vector
+ vector : ARRAY[INTEGER];
vector := ARRAY[INTEGER].create_with_capacity 32 lower 0;
vector.add_last 1;
vector.add_last 2;
[edit] hashed set
+ set : HASHED_SET[INTEGER];
set := HASHED_SET[INTEGER].create;
set.add 1;
set.add 2;
[edit] linked list
+ list : LINKED_LIST[INTEGER];
list := LINKED_LIST[INTEGER].create;
list.add_last 1;
list.add_last 2;
[edit] hashed dictionary
+ 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";
[edit] 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
[edit] 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.
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'}
[edit] 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.
#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;
}
Output (stripped the left-sided log info):
two 20 10 one two appears 1 times one appears 2 times eight -> 8 four -> 4
[edit] OCaml
Lists are written like so:
[1; 2; 3; 4; 5]
To prepend a single element to a list, use the :: operator:
1 :: [2; 3; 4; 5]
To concatenate two lists, use @:
[1; 2] @ [3; 4; 5]
To concatenate a whole list of lists, use List.flatten:
# List.flatten [[1; 2]; [3; 4]; [5; 6; 7]] ;;
- : int list = [1; 2; 3; 4; 5; 6; 7]
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:
[| 1; 2; 3; 4; 5 |]
The extlib also provides a type Enum.t.
[edit] Oz
The most important collection types are lists, records, dictionaries and arrays:
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
There are also tuples (records with consecutive integer keys starting with 1), weak dictionaries, queues and stacks.
[edit] Perl
Perl has array and hashes.
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";
}
[edit] PHP
PHP has associative arrays as collection
<?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);
?>
Output:
Array
(
[0] => 55
[1] => 10
[2] => 20
)
Array
(
[0] => 55
[1] => 10
[2] => 20
[one] => 1
[two] => 2
)
[edit] PicoLisp
The direct way in PicoLisp is a linear list (other possibilities could involve index trees or property lists).
: (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)
[edit] Python
Works with: Python version 2.5 Python supports lists, tuples, dictionaries and now sets as built-in collection types. See http://docs.python.org/tut/node7.html for further details.
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: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)
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).
[edit] R
R has several types that can be considered collections.
[edit] Vectors
Numeric (floating point)
numeric(5)
1:10
c(1, 3, 6, 10, 7 + 8, sqrt(441))
[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
integer(5)
c(1L, -2L, 99L);
[1] 0 0 0 0 0 [1] 1 -2 99
Logical
logical(5)
c(TRUE, FALSE)
[1] FALSE FALSE FALSE FALSE FALSE [1] TRUE FALSE
Character
character(5)
c("abc", "defg", "")
[1] "" "" "" "" "" [1] "abc" "defg" ""
[edit] Arrays and Matrices
These are essentially vectors with a dimension attribute. Matrices are just arrays with two dimensions (and a different class).
matrix(1:12, nrow=3)
array(1:24, dim=c(2,3,4)) #output not shown
[,1] [,2] [,3] [,4] [1,] 1 4 7 10 [2,] 2 5 8 11 [3,] 3 6 9 12
[edit] Lists
Lists are collections of other variables (that can include other lists).
list(a=123, b="abc", TRUE, 1:5, c=list(d=runif(5), e=5+6))
$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
[edit] Data Frames
Data frames are like a cross between a list and a matrix. Each row represents one "record", or a collection of variables.
data.frame(name=c("Alice", "Bob", "Carol"), age=c(23, 35, 17))
name age 1 Alice 23 2 Bob 35 3 Carol 17
[edit] Raven
Numerically indexed List:
[ 1 2 3 'abc' ] as a_list
a_list print
list (4 items)
0 => 1
1 => 2
2 => 3
3 => "abc"
String key indexed Hash:
{ 'a' 1 'b' 2 } as a_hash
a_hash print
hash (2 items)
a => 1
b => 2
Set items:
17 a_list 1 set # set second item
42 a_hash 'b' set # set item with key 'b'
42 a_hash:b # shorthand
Get items:
a_list 1 get # get second item
a_hash 'b' get # get item with key 'b'
a_hash.b # shorthand
Other stuff:
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
[edit] Ruby
[edit] array
# 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 # => []
[edit] hash
# 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 # => {}
[edit] 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.
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)
[edit] Scheme
[edit] list
(list obj ...)
returns a newly allocated list of its arguments.
Example:
(display (list 1 2 3))
(newline)
(display (list))
(newline)
Output:
(1 2 3)
()
[edit] cons
(cons obj lst)
returns a newly allocated list consisting of obj prepended to lst.
Example:
(display (cons 0 (list 1 2 3)))
(newline)
Output:
(0 1 2 3)
[edit] append
(append lst ...)
returns a newly allocated list consisting of the elements of lst followed by the elements of the other lists.
Example:
(display (append (list 1 2 3) (list 4 5 6)))
(newline)
Output:
(1 2 3 4 5 6)
[edit] 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}"
[edit] 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
|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.
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 )
)
[edit] 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).
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
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.
# 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]
Works with: Tcl version 8.5
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.
# 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
[edit] 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.
[edit] Lists
Lists are written as comma-separated sequences enclosed in angle brackets, or with the head and tail separated by a colon.
x = <1,5,6>
y = <'foo','bar'>
z = 3:<6,8>
This function takes a pair of a new head and an existing list, and returns one that has the new head "added" to it.
foo ("newhead","existing-list") = "newhead":"existing-list"
[edit] Sets
Sets are comma separated sequences enclosed in braces. The order and multiplicities of elements are ignored, so that the followng declarations are equivalent.
x = {'a','b'}
y = {'b','a'}
z = {'a','b','a'}
[edit] Modules
Modules are lists in a particular form used to represent key:value pairs, with the key being a character string.
m = <'foo': 1,'bar': 2,'baz': 3>
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.
[edit] Trees
Trees are written in the form r^:s,
where r is the root and s is a list of subtrees, which can
be of any length.
x =
'z'^: <
'x'^: <
'7'^: <>,
'?'^: <'D'^: <>>>,
'a'^: <'E'^: <>,'j'^: <>>,
'b'^: <'i'^: <>>,
'c'^: <>>
[edit] 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.
x =
[
4:0: 'foo',
4:1: 'bar',
4:2: 'baz',
4:3: 'volta',
4:4: 'pramim']
[edit] 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.
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^: <>]>
[edit] V
A quote is used for the same purpose in V
[4 3 2 1] 5 swap cons
=[5 4 3 2 1]
[edit] Visual Basic .NET
Dim toys As New List(Of String)
toys.Add("Car")
toys.Add("Boat")
toys.Add("Train")
