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 editContent deleted Content addedVisualWikitext
Revision as of 12:50, 3 October 2011 edit1exec1 (talk | contribs)Pending changes reviewers, Rollbackers50,085 edits Undid revision 453689944 by 1exec1 (talk) undo. better make the other pages lowercase← Previous edit Latest revision as of 11:58, 17 October 2021 edit undoChristian75 (talk | contribs)Extended confirmed users, New page reviewers, Pending changes reviewers, Rollbackers114,301 edits {{R with history}} 
(5 intermediate revisions by 3 users not shown)
Line 1: Line 1:
#REDIRECT ]
{{lowercase}}
{{C++ Standard library}}


{{R to section}}
The '''array''' is a wrapper ] that provides an ]-like interface to standard fixed-size ] arrays. It also overcomes several limitations of standard arrays.
{{R with 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 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 the ] in ].

== Motivation ==

Standard C arrays have several principal limitations:
* They aren't ]s. They can not be copied like other objects.
* They do not provide an STL-like interface.

== Design ==

The <tt>array</tt> 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 the type of the elements and the 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.

If <tt>array</tt> class template is instantiated with a type that fulfills <tt>EqualityComparable</tt> or <tt>LessThanComparable</tt> requirements, it fulfills <tt>EqualityComparable</tt> or <tt>LessThanComparable</tt> correspondingly.

Class also provides standard iterators and element access functions.

=== Implementation as aggregate ===

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

<source lang="cpp">
array<int, 4> a = { { 1, 2, 3 } };
</source>

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 own 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, the <tt>array</tt> template can be initialized as follows:

<source lang="cpp">
array<int, 4> a = { 1, 2, 3 };
</source>

== Differences from standard array ==

* The <tt>array</tt> class is a value type. It satisfies <tt>CopyConstructable</tt> and <tt>Assignable</tt> requirements.
* The <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 the first element.
* The <tt>array</tt> implementation is not required to do bound check. However the implementation in boost does that for <tt>operator</tt>, but not for iterators.

=== Zero-sized arrays ===

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

== Differences from standard containers ==

* The <tt>array</tt> class does not provide constant-time swap. Instead it provides linear-time swap.
* Because the <tt>array</tt> class is an aggregate it does not provide fill and range constructors. Its default constructor also does not initialize elements with zeros.
* <tt>size()</tt> is always constant, based on the second template argument of the type.
* The container provides no allocator support.

== Overview of functions ==

An object of class <tt>array</tt> 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&lt;T, N&gt; a</tt> || create an array object, elements of that have undetermined values || ''O''(1)
|-
| <tt>array&lt;T, N&gt; a1(a2)</tt> || create a copy of other array object || ''O''(N)
|-
| <tt>array&lt;T, N&gt; a = {/*...*/}</tt> || create an array object initialized with specified values || ''O''(N)
|}

The <tt>array</tt> class provides a swap function and the assignment operator. The only difference from other containers is that <tt>swap</tt> takes linear time.

{| class="wikitable" style="text-align: center"|
|-
! style="text-align: left" | expression
! return type
! description
! computational complexity
|-
| <tt>swap(a1, a2)</tt> || <tt>void</tt> || swap content of arrays || ''O''(N)
|-
| <tt>a1 = a2</tt> || <tt>array &</tt> || copy content of a2 to a1 || ''O''(N)
|}

Although TR1 define function <tt>assign</tt> to fill an array with a specified value, ] has the function <tt>fill</tt> for the same purpose. The boost implementation of <tt>array</tt> supports both functions.

{| class="wikitable" style="text-align: center"|
|-
! style="text-align: left" | expression
! return type
! description
! computational complexity
|-
| <tt>a.assign(u)</tt> || <tt>void</tt> || fill a with u (TR1 only) || ''O''(N)
|-
| <tt>a.fill(u)</tt> || <tt>void</tt> || fill a with u (C++0x only) || ''O''(N)
|}

The <tt>array</tt> class provides a standard iterator interface.

{| class="wikitable" style="text-align: center"|
|-
! style="text-align: left" | expression
! return type
! description
! computational complexity
|-
| <tt>a.begin()</tt> || <tt>iterator</tt> || returns iterator to first element of array || ''O''(1)
|-
| <tt>a.end()</tt> || <tt>iterator</tt> || returns iterator to the one after the last element of array || ''O''(1)
|-
| <tt>a.rbegin()</tt> || <tt>reverse_iterator</tt> || returns reverse iterator to first element of array || ''O''(1)
|-
| <tt>a.rend()</tt> || <tt>reverse_iterator</tt> || returns reverse iterator to the one after the last element of array || ''O''(1)
|}

The <tt>array</tt> class provides standard query-capacity functions.

{| class="wikitable" style="text-align: center"|
|-
! style="text-align: left" | expression
! return type
! description
! computational complexity
|-
| <tt>a.size()</tt> || <tt>size_t</tt> || returns size of array || ''O''(1)
|-
| <tt>a.max_size()</tt> || <tt>size_t</tt> || returns size of array || ''O''(1)
|-
| <tt>a.empty()</tt> || <tt>bool</tt> || <tt>a.size() == 0</tt> || ''O''(1)
|}

The <tt>array</tt> class provides a standard set of element access functions.

{| class="wikitable" style="text-align: center"|
|-
! style="text-align: left" | expression
! return type
! description
! computational complexity
|-
| <tt>a</tt> || <tt>T &</tt> || returns reference to i-th element || ''O''(1)
|-
| <tt>a.at(i)</tt> || <tt>T &</tt> || returns reference to i-th element or throws out_of_range exception || ''O''(1)
|-
| <tt>a.front()</tt> || <tt>T &</tt> || returns reference to first element of array || ''O''(1)
|-
| <tt>a.back()</tt> || <tt>T &</tt> || returns reference to last element of array || ''O''(1)
|}

The <tt>array</tt> class has six standard comparison operators.

{| class="wikitable" style="text-align: center"|
|-
! style="text-align: left" | expression
! return type
! description
! computational complexity
|-
| <tt>a1 &lt; a2</tt> || <tt>bool</tt> || compare arrays lexicographically || ''O''(N)
|-
| <tt>a1 == a2</tt> || <tt>bool</tt> || compare arrays lexicographically || ''O''(N)
|-
| <tt>a1 &gt; a2</tt> || <tt>bool</tt> || compare arrays lexicographically || ''O''(N)
|-
| <tt>a1 &lt;= a2</tt> || <tt>bool</tt> || compare arrays lexicographically || ''O''(N)
|-
| <tt>a1 != a2</tt> || <tt>bool</tt> || compare arrays lexicographically || ''O''(N)
|-
| <tt>a1 &gt;= a2</tt> || <tt>bool</tt> || compare arrays lexicographically || ''O''(N)
|}

Raw data access functions.

{| class="wikitable" style="text-align: center"|
|-
! style="text-align: left" | expression
! return type
! description
! computational complexity
|-
| <tt>a.data()</tt> || <tt>T *</tt> || returns pointer to first element of array || ''O''(1)
|-
| <tt>a.c_array()</tt> || <tt>T *</tt> || returns pointer to first element of array (non-standard, boost-only, no const-overload) || ''O''(1)
|}

The <tt>array</tt> class provides the standard tuple interface.

{| class="wikitable" style="text-align: center"|
|-
! style="text-align: left" | expression
! return type
! description
|-
| <tt>tuple_size&lt;array&gt;::value</tt> || <tt>N</tt> || returns size of tuple
|-
| <tt>tuple_element&lt;I, array&gt;::type</tt> || <tt>T</tt> || returns type of tuple element
|-
| <tt>get&lt;i&gt;(a)</tt> || <tt>T</tt> || returns value of i-th tuple element
|}

The <tt>array</tt> class provides the standard set of dependent types.

{| class="wikitable" style="text-align: center"|
|-
! style="text-align: left" | expression
! return type
|-
| <tt>array&lt;T, N&gt;::reference</tt> || <tt>T &</tt>
|-
| <tt>array&lt;T, N&gt;::const_reference</tt> || <tt>T const &</tt>
|-
| <tt>array&lt;T, N&gt;::iterator</tt> || implementation-defined (<tt>T *</tt> in boost)
|-
| <tt>array&lt;T, N&gt;::const_iterator</tt> || implementation-defined (<tt>T const *</tt> in boost)
|-
| <tt>array&lt;T, N&gt;::size_type</tt> || <tt>size_t</tt>
|-
| <tt>array&lt;T, N&gt;::difference_type</tt> || <tt>ptrdiff_t</tt>
|-
| <tt>array&lt;T, N&gt;::value_type</tt> || <tt>T</tt>
|-
| <tt>array&lt;T, N&gt;::reverse_iterator</tt> || <tt>reverse_iterator&lt;iterator&gt;</tt>
|-
| <tt>array&lt;T, N&gt;::const_reverse_iterator</tt> || <tt>reverse_iterator&lt;const_iterator&gt;</tt>
|}

== External links ==

*
*
*

]
]

Latest revision as of 11:58, 17 October 2021

Redirect to:

  • With history: This is a redirect from a page containing substantive page history. This page is kept as a redirect to preserve its former content and attributions. Please do not remove the tag that generates this text (unless the need to recreate content on this page has been demonstrated), nor delete this page.
    • This template should not be used for redirects having some edit history but no meaningful content in their previous versions, nor for redirects created as a result of a page merge (use {{R from merge}} instead), nor for redirects from a title that forms a historic part of Misplaced Pages (use {{R with old history}} instead).