Arrays
Introduction#
Arrays are elements of the same type placed in adjoining memory locations. The elements can be individually referenced by a unique identifier with an added index.
This allows you to declare multiple variable values of a specific type and access them individually without needing to declare a variable for each value.
Array size: type safe at compile time.
#include <stddef.h> // size_t, ptrdiff_t
//----------------------------------- Machinery:
using Size = ptrdiff_t;
template< class Item, size_t n >
constexpr auto n_items( Item (&)[n] ) noexcept
-> Size
{ return n; }
//----------------------------------- Usage:
#include <iostream>
using namespace std;
auto main()
-> int
{
int const a[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 4};
Size const n = n_items( a );
int b[n] = {}; // An array of the same size as a.
(void) b;
cout << "Size = " << n << "\n";
}The C idiom for array size, sizeof(a)/sizeof(a[0]), will accept a pointer as argument and will then generally yield an incorrect result.
For C++11
using C++11 you can do:
std::extent<decltype(MyArray)>::value;Example:
char MyArray[] = { 'X','o','c','e' };
const auto n = std::extent<decltype(MyArray)>::value;
std::cout << n << "\n"; // Prints 4Up till C++17 (forthcoming as of this writing) C++ had no built-in core language or standard library utility to obtain the size of an array, but this can be implemented by passing the array by reference to a function template, as shown above. Fine but important point: the template size parameter is a size_t, somewhat inconsistent with the signed Size function result type, in order to accommodate the g++ compiler which sometimes insists on size_t for template matching.
With C++17 and later one may instead use std::size, which is specialized for arrays.
Dynamically sized raw array
// Example of raw dynamic size array. It's generally better to use std::vector.
#include <algorithm> // std::sort
#include <iostream>
using namespace std;
auto int_from( istream& in ) -> int { int x; in >> x; return x; }
auto main()
-> int
{
cout << "Sorting n integers provided by you.\n";
cout << "n? ";
int const n = int_from( cin );
int* a = new int[n]; // ← Allocation of array of n items.
for( int i = 1; i <= n; ++i )
{
cout << "The #" << i << " number, please: ";
a[i-1] = int_from( cin );
}
sort( a, a + n );
for( int i = 0; i < n; ++i ) { cout << a[i] << ' '; }
cout << '\n';
delete[] a;
}A program that declares an array T a[n]; where n is determined a run-time, can compile with certain compilers that support C99 variadic length arrays (VLAs) as a language extension. But VLAs are not supported by standard C++. This example shows how to manually allocate a dynamic size array via a new[]-expression,
int* a = new int[n]; // ← Allocation of array of n items.… then use it, and finally deallocate it via a delete[]-expression:
delete[] a;The array allocated here has indeterminate values, but it can be zero-initialized by just adding an empty parenthesis (), like this: new int[n](). More generally, for arbitrary item type, this performs a value-initialization.
As part of a function down in a call hierarchy this code would not be exception safe, since an exception before the delete[] expression (and after the new[]) would cause a memory leak. One way to address that issue is to automate the cleanup via e.g. a std::unique_ptr smart pointer. But a generally better way to address it is to just use a std::vector: that’s what std::vector is there for.
Expanding dynamic size array by using std::vector.
// Example of std::vector as an expanding dynamic size array.
#include <algorithm> // std::sort
#include <iostream>
#include <vector> // std::vector
using namespace std;
int int_from( std::istream& in ) { int x = 0; in >> x; return x; }
int main()
{
cout << "Sorting integers provided by you.\n";
cout << "You can indicate EOF via F6 in Windows or Ctrl+D in Unix-land.\n";
vector<int> a; // ← Zero size by default.
while( cin )
{
cout << "One number, please, or indicate EOF: ";
int const x = int_from( cin );
if( !cin.fail() ) { a.push_back( x ); } // Expands as necessary.
}
sort( a.begin(), a.end() );
int const n = a.size();
for( int i = 0; i < n; ++i ) { cout << a[i] << ' '; }
cout << '\n';
}std::vector is a standard library class template that provides the notion of a variable size array. It takes care of all the memory management, and the buffer is contiguous so a pointer to the buffer (e.g. &v[0] or v.data()) can be passed to API functions requiring a raw array. A vector can even be expanded at run time, via e.g. the push_back member function that appends an item.
The complexity of the sequence of n push_back operations, including the copying or moving involved in the vector expansions, is amortized O(n). “Amortized”: on average.
Internally this is usually achieved by the vector doubling its buffer size, its capacity, when a larger buffer is needed. E.g. for a buffer starting out as size 1, and being repeatedly doubled as needed for n=17 push_back calls, this involves 1 + 2 + 4 + 8 + 16 = 31 copy operations, which is less than 2×n = 34. And more generally the sum of this sequence can’t exceed 2×n.
Compared to the dynamic size raw array example, this vector-based code does not require the user to supply (and know) the number of items up front. Instead the vector is just expanded as necessary, for each new item value specified by the user.
A fixed size raw array matrix (that is, a 2D raw array).
// A fixed size raw array matrix (that is, a 2D raw array).
#include <iostream>
#include <iomanip>
using namespace std;
auto main() -> int
{
int const n_rows = 3;
int const n_cols = 7;
int const m[n_rows][n_cols] = // A raw array matrix.
{
{ 1, 2, 3, 4, 5, 6, 7 },
{ 8, 9, 10, 11, 12, 13, 14 },
{ 15, 16, 17, 18, 19, 20, 21 }
};
for( int y = 0; y < n_rows; ++y )
{
for( int x = 0; x < n_cols; ++x )
{
cout << setw( 4 ) << m[y][x]; // Note: do NOT use m[y,x]!
}
cout << '\n';
}
}Output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
C++ doesn’t support special syntax for indexing a multi-dimensional array. Instead such an array is viewed as an array of arrays (possibly of arrays, and so on), and the ordinary single index notation [i] is used for each level. In the example above m[y] refers to row y of m, where y is a zero-based index. Then this row can be indexed in turn, e.g. m[y][x], which refers to the xth item – or column – of row y.
I.e. the last index varies fastest, and in the declaration the range of this index, which here is the number of columns per row, is the last and “innermost” size specified.
Since C++ doesn’t provide built-in support for dynamic size arrays, other than dynamic allocation, a dynamic size matrix is often implemented as a class. Then the raw array matrix indexing notation m[y][x] has some cost, either by exposing the implementation (so that e.g. a view of a transposed matrix becomes practically impossible) or by adding some overhead and slight inconvenience when it’s done by returning a proxy object from operator[]. And so the indexing notation for such an abstraction can and will usually be different, both in look-and-feel and in the order of indices, e.g. m(x,y) or m.at(x,y) or m.item(x,y).
A dynamic size matrix using std::vector for storage.
Unfortunately as of C++14 there’s no dynamic size matrix class in the C++ standard library. Matrix classes that support dynamic size are however available from a number of 3rd party libraries, including the Boost Matrix library (a sub-library within the Boost library).
If you don’t want a dependency on Boost or some other library, then one poor man’s dynamic size matrix in C++ is just like
vector<vector<int>> m( 3, vector<int>( 7 ) );… where vector is std::vector. The matrix is here created by copying a row vector n times where n is the number of rows, here 3. It has the advantage of providing the same m[y][x] indexing notation as for a fixed size raw array matrix, but it’s a bit inefficient because it involves a dynamic allocation for each row, and it’s a bit unsafe because it’s possible to inadvertently resize a row.
A more safe and efficient approach is to use a single vector as storage for the matrix, and map the client code’s (x, y) to a corresponding index in that vector:
// A dynamic size matrix using std::vector for storage.
//--------------------------------------------- Machinery:
#include <algorithm> // std::copy
#include <assert.h> // assert
#include <initializer_list> // std::initializer_list
#include <vector> // std::vector
#include <stddef.h> // ptrdiff_t
namespace my {
using Size = ptrdiff_t;
using std::initializer_list;
using std::vector;
template< class Item >
class Matrix
{
private:
vector<Item> items_;
Size n_cols_;
auto index_for( Size const x, Size const y ) const
-> Size
{ return y*n_cols_ + x; }
public:
auto n_rows() const -> Size { return items_.size()/n_cols_; }
auto n_cols() const -> Size { return n_cols_; }
auto item( Size const x, Size const y )
-> Item&
{ return items_[index_for(x, y)]; }
auto item( Size const x, Size const y ) const
-> Item const&
{ return items_[index_for(x, y)]; }
Matrix(): n_cols_( 0 ) {}
Matrix( Size const n_cols, Size const n_rows )
: items_( n_cols*n_rows )
, n_cols_( n_cols )
{}
Matrix( initializer_list< initializer_list<Item> > const& values )
: items_()
, n_cols_( values.size() == 0? 0 : values.begin()->size() )
{
for( auto const& row : values )
{
assert( Size( row.size() ) == n_cols_ );
items_.insert( items_.end(), row.begin(), row.end() );
}
}
};
} // namespace my
//--------------------------------------------- Usage:
using my::Matrix;
auto some_matrix()
-> Matrix<int>
{
return
{
{ 1, 2, 3, 4, 5, 6, 7 },
{ 8, 9, 10, 11, 12, 13, 14 },
{ 15, 16, 17, 18, 19, 20, 21 }
};
}
#include <iostream>
#include <iomanip>
using namespace std;
auto main() -> int
{
Matrix<int> const m = some_matrix();
assert( m.n_cols() == 7 );
assert( m.n_rows() == 3 );
for( int y = 0, y_end = m.n_rows(); y < y_end; ++y )
{
for( int x = 0, x_end = m.n_cols(); x < x_end; ++x )
{
cout << setw( 4 ) << m.item( x, y ); // ← Note: not `m[y][x]`!
}
cout << '\n';
}
}Output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
The above code is not industrial grade: it’s designed to show the basic principles, and serve the needs of students learning C++.
For example, one may define operator() overloads to simplify the indexing notation.
Array initialization
An array is just a block of sequential memory locations for a specific type of variable. Arrays are allocated the same way as normal variables, but with square brackets appended to its name [] that contain the number of elements that fit into the array memory.
The following example of an array uses the typ int, the variable name arrayOfInts, and the number of elements [5] that the array has space for:
int arrayOfInts[5];An array can be declared and initialized at the same time like this
int arrayOfInts[5] = {10, 20, 30, 40, 50};When initializing an array by listing all of its members, it is not necessary to include the number of elements inside the square brackets. It will be automatically calculated by the compiler. In the following example, it’s 5:
int arrayOfInts[] = {10, 20, 30, 40, 50};It is also possible to initialize only the first elements while allocating more space. In this case, defining the length in brackets is mandatory. The following will allocate an array of length 5 with partial initialization, the compiler initializes all remaining elements with the standard value of the element type, in this case zero.
int arrayOfInts[5] = {10,20}; // means 10, 20, 0, 0, 0Arrays of other basic data types may be initialized in the same way.
char arrayOfChars[5]; // declare the array and allocate the memory, don't initialize
char arrayOfChars[5] = { 'a', 'b', 'c', 'd', 'e' } ; //declare and initialize
double arrayOfDoubles[5] = {1.14159, 2.14159, 3.14159, 4.14159, 5.14159};
string arrayOfStrings[5] = { "C++", "is", "super", "duper", "great!"};It is also important to take note that when accessing array elements, the array’s element index(or position) starts from 0.
int array[5] = { 10/*Element no.0*/, 20/*Element no.1*/, 30, 40, 50/*Element no.4*/};
std::cout << array[4]; //outputs 50
std::cout << array[0]; //outputs 10