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.
Creation
array<E> | A(int a, int b); | creates an instance A of type array<E> with index set [a..b]. |
array<E> |
A(int n); | creates an instance A of type array<E> with index set [0..n-1]. |
array<E> |
A; | creates an instance A of type array<E> with empty index set. |
Special Constructors
array<E> | A(int low, E x, E y); | creates an instance A of type array<E> with index set [low, low+1] initialized to [x,y]. |
array<E> |
A(int low, E x, E y, E w); | creates an instance A of type array<E> with index set [low, low+2] initialized to [x,y,w]. |
array<E> |
A(int low, E x, E y, E z, E w); | |
creates an instance A of type array<E> 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. |
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
![]() |
bool | A.C_style() | returns true if the array has ``C-style'', i.e., the index set is [0..size-1]. |
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 (in_a,...,in_b) and (out_a,...,out_b) denote the values of the variables (A(a),...,A(b)) before and after the call of sort, then cmp(out_i,out_j) <= 0 for i<= j and there is a permutation pi of [a..b] such that out_i=in_pi(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(const E&, const E&). |
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. |
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(n log n)) and the binary_search operation takes time O(log n), where n = b-a+1. The space requirement is O(I* sizeof(E)).