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<E>::item | the item type. |
array<E>::value_type | the value type. |
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. |
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<E> 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
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<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(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)).