Revision as of 08:13, 25 April 2010 editIvansorokin (talk | contribs)50 editsm →Differences from standard containers← Previous edit | Revision as of 08:42, 25 April 2010 edit undoIvansorokin (talk | contribs)50 edits constructor, comparison operators, swapNext edit → | ||
Line 68: | Line 68: | ||
* size() is always constant, based on the second template argument of the type. | * size() is always constant, based on the second template argument of the type. | ||
* The container provides no allocator support. | * The container provides no allocator support. | ||
== Overview of functions == | |||
Object of array class can be created using default constructor, copy constructor or initializer list syntax. | |||
{| class="wikitable" style="text-align: center"| | |||
|- | |||
! style="text-align: left" | expression | |||
! description | |||
! computational complexity | |||
|- | |||
| <tt>array a</tt> || create a array object, elements of that have undetermined values || ''O''(1) | |||
|- | |||
| <tt>array a1(a2)</tt> || create a copy of other array object || ''O''(N) | |||
|- | |||
| <tt>array a = {/*...*/}</tt> || create a array object initialized with specified values || ''O''(N) | |||
|} | |||
Array class has six comparison operators. | |||
{| class="wikitable" style="text-align: center"| | |||
|- | |||
! style="text-align: left" | expression | |||
! return type | |||
! description | |||
! computational complexity | |||
|- | |||
| <tt>a1 < a2</tt> || <tt>bool</tt> || compare arrays lexicographically || ''O''(N) | |||
|- | |||
| <tt>a1 == a2</tt> || <tt>bool</tt> || compare arrays lexicographically || ''O''(N) | |||
|- | |||
| <tt>a1 > a2</tt> || <tt>bool</tt> || compare arrays lexicographically || ''O''(N) | |||
|- | |||
| <tt>a1 <= a2</tt> || <tt>bool</tt> || compare arrays lexicographically || ''O''(N) | |||
|- | |||
| <tt>a1 != a2</tt> || <tt>bool</tt> || compare arrays lexicographically || ''O''(N) | |||
|- | |||
| <tt>a1 >= a2</tt> || <tt>bool</tt> || compare arrays lexicographically || ''O''(N) | |||
|} | |||
{| class="wikitable" style="text-align: center"| | |||
|- | |||
! style="text-align: left" | expression | |||
! return type | |||
! description | |||
! computational complexity | |||
|- | |||
| swap(a1, a2) || void || swap content of arrays || ''O''(N) | |||
|} | |||
== Links == | == Links == |
Revision as of 08:42, 25 April 2010
A array is wrapper class that provides STL-like interface to standard fixed-size C-arrays. It also overcomes several limitations of standard array.
Creation History
In his book, Generic Programming and the STL, Matthew H. Austern introduces a wrapper class for ordinary arrays with static size, called block. It is safer and has no worse performance than ordinary arrays. In The C++ Programming Language, 3rd edition, Bjarne Stroustrup introduces a similar class, called c_array, which Nicolai Josuttis present slightly modified in his book The C++ Standard Library - A Tutorial and Reference, called carray.
Under the name array this class is introduced in boost libraries by Nicolai Josuttis. Later this class was introduced in C++ standard library in TR1.
Motivation
Standard C arrays has several principal limitation:
- They aren't value types. They can not be copied like any other object.
- They do not obey standard operator & semantics.
- They do not provide STL-like interface.
The second item means that in the following code
int a; int * b1 = a; int * b2 = &a;
b1 and b2 receive the same value. This behavior differs from one of any other standard type.
Design
Array template class is defined in header <array> in C++ standard library and in header <boost/array.hpp> in boost. It can resides in namespaces std:: (in C++0x), std::tr1:: (in C++03 with TR1) or boost::.
The array class template is parametrized with a type of element and a number of elements. It can be instantiated with any type that fulfills the CopyConstructible and Assignable requirements. It also itself fulfills CopyConstructible and Assignable requirements.
If array class template is instantiated with a type that fulfills EqualityComparable or LessThanComparable requirements, it fulfills EqualityComparable or LessThanComparable correspondingly.
Class also provides standard iterators and element access functions.
Implementation as aggregate
array class is implemented as aggregate class. This allow array to be initialized with a brace-enclosing, comma-separated list of initializers for the elements of the container, written in increasing subscript order:
array<int,4> a = { { 1, 2, 3 } };
Note that if there are fewer elements in the initializer list, then each remaining element gets default-initialized (thus, it has a defined value).
However, this approach has its drawbacks: passing no initializer list means that the elements have an indetermined initial value, because the rule says that aggregates may have:
- No user-declared constructors.
- No private or protected non-static data members.
- No base classes.
- No virtual functions.
Note that for standard conforming compilers it is possible to use fewer braces (according to 8.5.1 (11) of the Standard). That is, array can be initialized as follows:
array<int,4> a = { 1, 2, 3 };
Differences from standard array
- array class is value type. It satisfy CopyConstructable and Assignable requirements.
- array class can not be implicitly casted to T * or T const *. However there is member function data() that returns pointer to first element.
- array implementation is not required to do bound check. However implementation in boost do that for operator, but not for iterators.
- Unlike standard arrays array class can have zero size.
Differences from standard containers
- array class do not provides constant-time swap. Instead it provides linear-time swap.
- Because array class is aggregate it do not provides fill and range constructors. Its default constructor also does not initialize elements with zeros.
- size() is always constant, based on the second template argument of the type.
- The container provides no allocator support.
Overview of functions
Object of array class can be created using default constructor, copy constructor or initializer list syntax.
expression | description | computational complexity |
---|---|---|
array a | create a array object, elements of that have undetermined values | O(1) |
array a1(a2) | create a copy of other array object | O(N) |
array a = {/*...*/} | create a array object initialized with specified values | O(N) |
Array class has six comparison operators.
expression | return type | description | computational complexity |
---|---|---|---|
a1 < a2 | bool | compare arrays lexicographically | O(N) |
a1 == a2 | bool | compare arrays lexicographically | O(N) |
a1 > a2 | bool | compare arrays lexicographically | O(N) |
a1 <= a2 | bool | compare arrays lexicographically | O(N) |
a1 != a2 | bool | compare arrays lexicographically | O(N) |
a1 >= a2 | bool | compare arrays lexicographically | O(N) |
expression | return type | description | computational complexity |
---|---|---|---|
swap(a1, a2) | void | swap content of arrays | O(N) |
Links
- A Proposal to Add a Fixed Size Array Wrapper to the Standard Library Technical Report
- Boost.Array documentation