Misplaced Pages

Array (C++): Difference between revisions

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Browse history interactively← Previous editNext edit →Content deleted Content addedVisualWikitext
Revision as of 05:26, 14 January 2011 editPnm (talk | contribs)Extended confirmed users14,752 edits +lowercase← Previous edit Revision as of 03:33, 19 January 2011 edit undoMild Bill Hiccup (talk | contribs)Extended confirmed users, Pending changes reviewers, Rollbackers175,372 edits grammarNext edit →
Line 1: Line 1:
{{lowercase}} {{lowercase}}


A array is wrapper class that provides ]-like interface to standard fixed-size C-arrays. It also overcomes several limitations of standard array. The '''array''' is a wrapper ] that provides an ]-like interface to standard fixed-size ] arrays. It also overcomes several limitations of standard array.


== Creation History == == Creation history ==


In his book, ''Generic Programming and the STL'', Matthew H. Austern introduces a wrapper class for ordinary arrays with static size, called <tt>block</tt>. It is safer and has no worse performance than ordinary arrays. In ''The C++ Programming Language, 3rd edition'', ] introduces a similar class, called <tt>c_array</tt>, which Nicolai Josuttis present slightly modified in his book ''The C++ Standard Library - A Tutorial and Reference'', called <tt>carray</tt>. In his book ''Generic Programming and the STL'', Matthew H. Austern introduces a wrapper class for ordinary arrays with static size, called <tt>block</tt>. It is safer and has no worse performance than ordinary arrays. In ''The C++ Programming Language, 3rd edition'', ] introduces a similar class, called <tt>c_array</tt>, which Nicolai Josuttis presents slightly modified in his book ''The C++ Standard Library - A Tutorial and Reference'', called <tt>carray</tt>.


Under the name <tt>array</tt> this class is introduced in ] libraries by Nicolai Josuttis. Later this class was introduced in C++ standard library in ]. Under the name <tt>array</tt> this class is introduced in ] libraries by Nicolai Josuttis. Later this class was introduced in the ] in ].


== Motivation == == Motivation ==
Line 17: Line 17:
== Design == == Design ==


Array template class is defined in header <tt>&lt;array&gt;</tt> in C++ standard library and in header <tt>&lt;boost/array.hpp&gt;</tt> in boost. It can resides in namespaces <tt>std::</tt> (in ]), <tt>std::tr1::</tt> (in C++03 with TR1) or <tt>boost::</tt>. Array template class is defined in header <tt>&lt;array&gt;</tt> in the C++ standard library and in header <tt>&lt;boost/array.hpp&gt;</tt> in boost. It can reside in namespaces <tt>std::</tt> (in ]), <tt>std::tr1::</tt> (in C++03 with TR1) or <tt>boost::</tt>.


The <tt>array</tt> class template is parametrized with a type of element and a number of elements. It can be instantiated with any type that fulfills the <tt>CopyConstructible</tt> and <tt>Assignable</tt> requirements. It also itself fulfills <tt>CopyConstructible</tt> and <tt>Assignable</tt> requirements. The <tt>array</tt> class template is parametrized with a type of element and a number of elements. It can be instantiated with any type that fulfills the <tt>CopyConstructible</tt> and <tt>Assignable</tt> requirements. It also itself fulfills <tt>CopyConstructible</tt> and <tt>Assignable</tt> requirements.
Line 27: Line 27:
=== Implementation as aggregate === === Implementation as aggregate ===


<tt>array</tt> class is implemented as aggregate class. This allows an array to be initialized with a brace-enclosing, comma-separated list of initializers for the elements of the container, written in increasing subscript order: <tt>array</tt> class is implemented as an aggregate class. This allows an array to be initialized with a brace-enclosing, comma-separated list of initializers for the elements of the container, written in increasing subscript order:


<source lang="cpp"> <source lang="cpp">
Line 35: Line 35:
Note that if there are fewer elements in the initializer list, then each remaining element gets default-initialized (thus, it has a defined value). 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: However, this approach has its drawbacks: passing no initializer list means that the elements have an indeterminate initial value, because the rule says that aggregates may have:


* No user-declared constructors. * No user-declared constructors.
Line 51: Line 51:


* <tt>array</tt> class is a value type. It satisfies <tt>CopyConstructable</tt> and <tt>Assignable</tt> requirements. * <tt>array</tt> class is a value type. It satisfies <tt>CopyConstructable</tt> and <tt>Assignable</tt> requirements.
* <tt>array</tt> class can not be implicitly casted to <tt>T *</tt> or <tt>T const *</tt>. However there is member function <tt>data()</tt> that returns pointer to first element. * <tt>array</tt> class can not be implicitly cast to <tt>T *</tt> or <tt>T const *</tt>. However there is member function <tt>data()</tt> that returns a pointer to first element.
* <tt>array</tt> implementation is not required to do bound check. However implementation in boost do that for <tt>operator</tt>, but not for iterators. * <tt>array</tt> implementation is not required to do bound check. However implementation in boost do that for <tt>operator</tt>, but not for iterators.


=== Zero-sized arrays === === Zero-sized arrays ===


Unlike standard arrays <tt>array</tt> class can have zero size. The effect of calling <tt>front()</tt> or <tt>back()</tt> for a zero-sized array is implementation defined. <tt>begin() == end()</tt> shall be unique value. The return value of <tt>data()</tt> is unspecified. Unlike standard arrays, <tt>array</tt> class can have zero size. The effect of calling <tt>front()</tt> or <tt>back()</tt> for a zero-sized array is implementation defined. <tt>begin() == end()</tt> shall be unique value. The return value of <tt>data()</tt> is unspecified.


== Differences from standard containers == == Differences from standard containers ==


* <tt>array</tt> class does not provide constant-time swap. Instead it provides linear-time swap. * <tt>array</tt> class does not provide constant-time swap. Instead it provides linear-time swap.
* Because <tt>array</tt> class is aggregate it do not provides fill and range constructors. Its default constructor also does not initialize elements with zeros. * Because <tt>array</tt> class is aggregate it does not provide 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. * 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.
Line 67: Line 67:
== Overview of functions == == Overview of functions ==


Object of array class can be created using default constructor, copy constructor or initializer list syntax. An object of array class can be created using default constructor, copy constructor or initializer list syntax.


{| class="wikitable" style="text-align: center"| {| class="wikitable" style="text-align: center"|
Line 239: Line 239:
|} |}


== Links == == External links ==


* *

Revision as of 03:33, 19 January 2011


The array is a wrapper class that provides an 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 presents 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 the C++ Standard Library in TR1.

Motivation

Standard C arrays have several principal limitations:

  • They aren't value types. They can not be copied like any other object.
  • They do not provide an STL-like interface.

Design

Array template class is defined in header <array> in the C++ standard library and in header <boost/array.hpp> in boost. It can reside 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 an aggregate class. This allows an 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 indeterminate 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 a value type. It satisfies CopyConstructable and Assignable requirements.
  • array class can not be implicitly cast to T * or T const *. However there is member function data() that returns a 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.

Zero-sized arrays

Unlike standard arrays, array class can have zero size. The effect of calling front() or back() for a zero-sized array is implementation defined. begin() == end() shall be unique value. The return value of data() is unspecified.

Differences from standard containers

  • array class does not provide constant-time swap. Instead it provides linear-time swap.
  • Because array class is aggregate it does not provide 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

An object of array class can be created using default constructor, copy constructor or initializer list syntax.

expression description computational complexity
array<T, N> a create a array object, elements of that have undetermined values O(1)
array<T, N> a1(a2) create a copy of other array object O(N)
array<T, N> a = {/*...*/} create a array object initialized with specified values O(N)

Array class provides swap function and assignment operator. The only difference from other containers is that swap takes linear time.

expression return type description computational complexity
swap(a1, a2) void swap content of arrays O(N)
a1 = a2 array & copy content of a2 to a1 O(N)

Although TR1 define function assign to fill array with specified value, C++0x has function fill intended for the same purpose. Boost implementation of array supports both functions.

expression return type description computational complexity
a.assign(u) void fill a with u (TR1 only) O(N)
a.fill(u) void fill a with u (C++0x only) O(N)

Array class provides standard iterator interface.

expression return type description computational complexity
a.begin() iterator returns iterator to first element of array O(1)
a.end() iterator returns iterator to the one after the last element of array O(1)
a.rbegin() reverse_iterator returns reverse iterator to first element of array O(1)
a.rend() reverse_iterator returns reverse iterator to the one after the last element of array O(1)

Array class provides standard query-capacity functions.

expression return type description computational complexity
a.size() size_t returns size of array O(1)
a.max_size() size_t returns size of array O(1)
a.empty() bool a.size() == 0 O(1)

Array class provides standard set of element access functions.

expression return type description computational complexity
a T & returns reference to i-th element O(1)
a.at(i) T & returns reference to i-th element or throws out_of_range exception O(1)
a.front() T & returns reference to first element of array O(1)
a.back() T & returns reference to last element of array O(1)

Array class has six standard 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)

Raw data access functions.

expression return type description computational complexity
a.data() T * returns pointer to first element of array O(1)
a.c_array() T * returns pointer to first element of array (non-standard, boost-only, no const-overload) O(1)

Array class provides standard tuple interface.

expression return type description
tuple_size<array>::value N returns size of tuple
tuple_element<I, array>::type T returns type of tuple element
get<i>(a) T returns value of i-th tuple element

Array class provides standard set of dependent types.

expression return type
array<T, N>::reference T &
array<T, N>::const_reference T const &
array<T, N>::iterator implementation-defined (T * in boost)
array<T, N>::const_iterator implementation-defined (T const * in boost)
array<T, N>::size_type size_t
array<T, N>::difference_type ptrdiff_t
array<T, N>::value_type T
array<T, N>::reverse_iterator reverse_iterator<iterator>
array<T, N>::const_reverse_iterator reverse_iterator<const_iterator>

External links

Category: