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. The array access operator (A[i]) checks its
precondition (a < = i < = b). The check can be turned off by compiling
with the flag -DLEDA_CHECKING_OFF
.
#include < LEDA/core/array.h >
Types
array<E>::item | the item type. |
array<E>::value_type | the value type. |
Creation
array<E> | A(int low, int high) | creates an instance A of type array<E> with index set [low..high]. |
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, const E& x, const 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, const E& x, const E& y, const 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, const E& x, const E& y, const E& z, const 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. |
E& | A.get(int x) | returns A(x).
Precondition a < = x < = b. |
void | A.set(int x, const E& e) | sets A(x) = e.
Precondition a < = x < = b. |
void | A.swap(int i, int j) | swaps the values of A[i] and A[j]. |
void | A.copy(int x, int y) | sets A(x) = A(y).
Precondition a < = x < = b and low() < = y < = high(). |
void | A.copy(int x, const array<E>& B, int y) | |
sets A(x) = B(y).
Precondition a < = x < = b and B.low() < = y < = B.high(). |
||
void | A.resize(int low, int high) | |
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(const 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.permute() | the elements of A are randomly permuted. |
void | A.permute(int low, int high) | |
the elements of A [low..high] are randomly permuted. |
Sorting and Searching
void | A.sort(int (*cmp)(const E& , const 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 of [a..b] such that out_{i} = 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&) if E is a user-defined type (see Section User Defined Parameter Types).. |
void | A.sort(int (*cmp)(const E& , const E& ), int low, int high) | |
sorts sub-array A [llow..high] using compare function cmp. | ||
void | A.sort(int low, int high) | sorts sub-array A [low..high] using the linear order on E. If E is a user-defined type, you have to define the linear order by providing the compare function (see Section User Defined Parameter Types). |
int | A.unique() | removes duplicates from A by copying the unique elements of A to A[A.low()],..., A[h] and returns h (A.low()-1 if A is empty). Precondition A is sorted increasingly according to the default ordering of type E. If E is a user-defined type, you have to define the linear order by providing the compare function (see Section User Defined Parameter Types). |
int | A.binary_search(int (*cmp)(const E& , const E& ), const E& x) | |
performs a binary search for x. Returns an 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(const E& x) | |
as above but uses the default linear order on E. If E is a user-defined type, you have to define the linear order by providing the compare function (see Section User Defined Parameter Types). | ||
int | A.binary_locate(int (*cmp)(const E& , const E& ), const 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(const E& x) | |
as above but uses the default linear order on E. If E is a user-defined type, you have to define the linear order by providing the compare function (see Section User Defined Parameter Types). |
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 « const array<E>& A | |
same as A.print(out); returns out. | ||
istream& | istream& in » array<E>& 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(n log n)) and the binary_search operation takes time O(log n), where n = b - a + 1. The space requirement is O(n*sizeof (E)).