Collections

Collections
You are encouraged to solve this task according to the task description, using any language you may know.

This task has been clarified. Its programming examples are in need of review to ensure that they still fit the requirements of the task.

Collections are abstractions to represent sets of values. In strongly-typed languages, the values are typically of a common data type.

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.

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

Works with: Ada 2005

Library: Ada.Containers.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>

Works with: Ada 2005

Library: Ada.Containers.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>

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

1. 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>

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.

? 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

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

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.

<lang java>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);

}</lang>

<lang java>//loop through myarrlist to sum each entry for(i=0; i<myarrlist.size(); i++) {

   sum+=myarrlist.get(i);

}</lang> or <lang java>for(int i:myarrlist){

   sum+= i;

}</lang>

<lang java>//remove the last entry in the ArrayList myarrlist.remove(myarrlist.size()-1)

//clear the ArrayList myarrlist.clear();</lang>

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>

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.

collection = {0, '1'}

collection = {["foo"] = 0, ["bar"] = '1'} -- a collection of key/value pairs

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 description], [coll countForObject: el]);
   } else if ( [coll isKindOfClass: [NSDictionary class]] ) {
     NSLog(@"%@ -> %@", [el description], [coll valueForKey: el]);
   } else {
     NSLog(@"%@", [el description]);
   }
 }
 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

Perl

Perl has array and hashes.

<lang perl>use strict; my @c = (); # create an empty "array" collection

1. fill it

push @c, 10, 11, 12; push @c, 65;

1. print it

print join(" ",@c) . "\n";

1. create an empty hash

my %h = ();

1. add some pair

$h{'one'} = 1; $h{'two'} = 2;

1. print it

foreach my $i ( keys %h ) {

   print $i . " -> " . $h{$i} . "\n";

}</lang>

PHP

PHP has associative arrays as collection

<lang php><?php $a = array();

1. add elements "at the end"

array_push($a, 55, 10, 20); print_r($a);

1. 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
)

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. <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: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).

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

Ruby

array

<lang ruby># creating an empty array and adding values

a = [] # => [] a[0] = 1 # => [1] a[3] = 2 # => [1, nil, nil, 3]

1. 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"}</lang>

Scala

This example may be incorrect due to a recent change in the task requirements or a lack of testing. Please verify it and remove this message. If the example does not match the requirements or does not work, replace this message with Template:incorrect or fix the code yourself.

[[Category:{{{1}}} examples needing attention]]Property "Example requires attention" (as page type) with input value "{{{1}}}" contains invalid characters or is incomplete and therefore can cause unexpected results during a query or annotation process.

val l = List(1,2,3,4,-1,-2,-4)
l.filter{0<} // get the positive values  List(1,2,3,4)
l.head // 1 -- first element
l.tail // List(2,3,4,-1,-2,-4) -- the rest of the list
l.take(3) // List(1,2,3) -- the first 3 elements in the list
l.drop(4) //  List(-1,-2,-4) -- get rid of the first 4 element in the list
88 :: l.tail //  List(88,2,3,4,-1,-2,-4)
l.take(2) ::: 18 :: l.takeRight(2) //  List(1,2,18,-2,-4)

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 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

1. fill it

lappend c 10 11 13 set c [linsert $c 2 "twelve goes here"]

1. iterate over it

foreach elem $c {puts $elem}

1. 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. Multi-dimensional arrays can be simulated with cleverly constructed key strings.

<lang tcl># create an empty array array set h {}

1. add some pair

set h(one) 1 set h(two) 2

1. add more data

array set h {three 3 four 4 more {5 6 7 8}}

1. 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"}

1. pass by name

proc numkeys_byname {arrayName} {

   upvar 1 $arrayName arr
   puts "array $arrayName has [llength [array names arr]] keys"

} numkeys_byname h

1. pass serialized

proc numkeys_bycopy {l} {

   array set arr $l
   puts "array has [llength [array names arr]] keys"

} numkeys_bycopy [array get h]</lang>

Works with: Tcl version 8.5

A Tcl dictionary is an associative array, but it can be passed as a value. 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

1. 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>

V

A quote is used for the same purpose in V

[4 3 2 1] 5 swap cons
=[5 4 3 2 1]

Visual Basic .NET

       Dim toys As New List(Of String)
       toys.Add("Car")
       toys.Add("Boat")
       toys.Add("Train")