Next: Two Dimensional Arrays ( Up: Basic Data Types Previous: Basic Data Types   Contents   Index

# One Dimensional Arrays ( array )

Definition

An instance A of the parameterized data type array<E> is a mapping from an interval I = [a..b] of integers, the index set of A, to the set of variables of data type E, the element type of A. A(i) is called the element at position i.

#include < LEDA/array.h >

Types

 array::item the item type. array::value_type the value type.

Creation

 array A(int a, int b) creates an instance A of type array with index set [a..b]. array A(int n) creates an instance A of type array with index set [0..n - 1]. array A creates an instance A of type array with empty index set.

Special Constructors

 array A(int low, E x, E y) creates an instance A of type array with index set [low, low + 1] initialized to [x, y]. array A(int low, E x, E y, E w) creates an instance A of type array with index set [low, low + 2] initialized to [x, y, w]. array A(int low, E x, E y, E z, E w) creates an instance A of type array with index set [low, low + 3] initialized to [x, y, z, w].

Operations

Basic Operations

 E& A[int x] returns A(x). Precondition a < = x < = b. E& A.get(int x) returns A(x). Precondition a < = x < = b. void A.set(int x, E e) sets A(x) = e. Precondition a < = x < = b. void A.copy(int x, array B, int y) sets A(x) = B(y). Precondition a < = x < = b and B.low() < = y < = B.high(). void A.copy(int x, int y) sets A(x) = A(y). Precondition a < = x < = b and low() < = y < = high(). void A.resize(int a, int b) sets the index set of A to [a..b] such that for all i [a..b] which are not contained in the old index set A(i) is set to the default value of type E. void A.resize(int n) same as A.resize(0,n-1). int A.low() returns the minimal index a of A. int A.high() returns the maximal index b of A. int A.size() returns the size (b - a + 1) of A. void A.init(E x) assigns x to A[i] for every i { a...b }. bool A.C_style() returns true if the array has C-style'', i.e., the index set is [0..size - 1]. void A.swap(int i, int j) swaps the values of A[i] and A[j]. void A.permute() the elements of A are randomly permuted. void A.permute(int l, int h) the elements of A[l..h] are randomly permuted.

Sorting and Searching

 void A.sort(int (*cmp)(E, E )) sorts the elements of A, using function cmp to compare two elements, i.e., if (ina,..., inb) and (outa,..., outb) denote the values of the variables (A(a),..., A(b)) before and after the call of sort, then cmp(outi, outj) < = 0 for i < = j and there is a permutation of [a..b] such that outi = in(i) for a < = i < = b. void A.sort() sorts the elements of A according to the linear order of the element type E. Precondition A linear order on E must have been defined by compare(constE&, constE&). void A.sort(int (*cmp)(E, E ), int l, int h) sorts sub-array A[l..h] using compare function cmp. void A.sort(int l, int h) sorts sub-array A[l..h] using the linear order on E. int A.binary_search(int (*cmp)(E, E ), E x) performs a binary search for x. Returns i with A[i] = x if x in A, A.low() - 1 otherwise. Function cmp is used to compare two elements. Precondition A must be sorted according to cmp. int A.binary_search(E x) as above but uses the default linear order on E. int A.binary_locate(int (*cmp)(E, E ), E x) Returns the maximal i with A[i] < = x or A.low()-1 if x < A[low]. Function cmp is used to compare elements. Precondition A must be sorted according to cmp. int A.binary_locate(E x) as above but uses the default linear order on E.

Input and Output

 void A.read(istream& I) reads b - a + 1 objects of type E from the input stream I into the array A using the operator>>(istream&,E&). void A.read() calls A.read(cin) to read A from the standard input stream cin. void A.read(string s) As above, uses string s as prompt. void A.print(ostream& O, char space = ' ') prints the contents of array A to the output stream O using operator<<(ostream&,const E&) to print each element. The elements are separated by character space. void A.print(char space = ' ') calls A.print(cout, space) to print A on the standard output stream cout. void A.print(string s, char space = ' ') As above, uses string s as header. ostream& ostream& out << A same as A.print(out); returns out. istream& istream& in >> array& A same as A.read(in)); returns in.

Iteration STL compatible iterators are provided when compiled with -DLEDA_STL_ITERATORS (see LEDAROOT/demo/stl/array.c for an example).

Implementation

Arrays are implemented by C++vectors. The access operation takes time O(1), the sorting is realized by quicksort (time O(nlog n)) and the binary_search operation takes time O(log n), where n = b - a + 1. The space requirement is O(I*sizeof (E)).

Next: Two Dimensional Arrays ( Up: Basic Data Types Previous: Basic Data Types   Contents   Index
LEDA research project
2000-10-12