Arrays with static and dynamic dimension. STL Part 1




Arrays with static and dynamic dimension, containers STL C ++ , Standard Template Librarybefore, you begin to digest the STL container types, reasonable to refresh your memory about the organization of C and C ++ arrays. Because the STL containers - these are some alternative forms of organization of data collection, free from the limitations of arrays.

Arrays - one of the most used forms of these organizations, and historically one of the first forms, appeared in programming languages (Languages ​​late 50-ies of the XX century). array - A representation of a set consecutive similar elements. Of fundamental importance in this definition are 2 currently, that must be met for an array necessarily:

  1. Each element of the array you need to specify number its location in a sequence similar elements.

  2. All array elements must necessarily be similar. Anyone familiar and understandable to the simplest definition, for example, integer array: int array[100] . But this does not mean, that arrays may be organized only simple built-in types of C ++. The array may be organized objects, variables of any composite type (class, structure) and complexity. The only limitation is that, what all elements of the same array must be of the same type. For example, so can be described by a student group:

Arrays with static and dynamic dimension, containers STL C ++ , Standard Template Library

By this very important circumstance - the types of elements in the array - we shall return in the future.

Ever since the time of the earliest programming languages (FORTRAN and others.), arrays imposes strong restrictions: the size array should be determined only integer constant, which value should be definitely on at compile time code. The same restriction preserved in C, who became the ancestor of C ++. For example:

Arrays with static and dynamic dimension, containers STL C ++ , Standard Template Library

In C ++ (classically, except for the standards of recent years!) this restriction slightly weakened before, what the size the array can be an integer constant, the value of which can calculated on at compile time code. For example, so:

Arrays with static and dynamic dimension, containers STL C ++ , Standard Template LibraryIn all such cases,, After determining the size of the array is fixed it and we will not be able to increase its size (if, for example, during calculations will, that we do not have enough of this size). For certain arrays are called arrays with statically announced (at the time of writing the code) size.

Note: Because of, that all elements of the array are arranged in series (1-e rule of the above), to calculate the size of the array (in his sight) It can be used as shown in the example of the trick: size of the array is the length of the entire array, divided by the length of any of its elements (because they are all the same type).

It could seem, that different arrays without the size defined, but with a list of initialization values:

Arrays with static and dynamic dimension, containers STL C ++ , Standard Template Library

But it is not so! Just here constancy value size declare arrays is removed from the list of values, and is equal to, in the example shown 5.

The only way to create an array, Classic C and C ++, size of elements N, calculated at the time of the creation of the array (runtime) - It was a way to dynamically allocate an array. In which C and C ++ is, respectively:

For example, so:

Arrays with static and dynamic dimension, containers STL C ++ , Standard Template Library

The most recent standards (C99, C++11) made expansion, that allow for the creation of local arrays with dimensions functions, calculable at the entrance of the function. Under these conditions, the array will be allocated on the stack function. This is very significant, when we can not know in advance the size of the processed data. As an example, look at the problem of finding all prime numbers, not exceeding N (sieve of Eratosthenes), where N is set when the program starts.

The code we have obliged to compile indicating the C ++ standard 2011 of the year (or compiler options, or collected by the project properties):Arrays with static and dynamic dimension, containers STL C ++ , Standard Template Library

But even after all the extensions, simple array, as a form of a set of objects, It is not flexible enough. The main limiting factor:

  • It would not be determined by the size of the array (constant or a calculation to determine the point) further increase this size can not (if you have not guessed in advance the required size, or not laid sufficient stock).

  • In C / C ++ rules when calling functions instead of the array as a parameter instead of an array is passed at its beginning pointer (the address of the 1st element). This allows strong improve the efficiency of many computational algorithms, but the loss of information about the size of the array, and it is necessary to transmit a separate parameter. For example, if we wanted to form a sieve of Eratosthenes not function main(), but in a separate function, then we would have to generate it as a challenge erastof ( a, n ).

  • Many intuitively simple array operations cause difficulty. For example: a 15-element array element numbered 10 must insert between the elements 2 and 3. At the same time as). all elements 3 по 9 You need to copy one position to the right, b). this should be done in descending order from 9 to 3 and). for all the indices of these operations need to monitor in manual mode.

Practice Requirements demanded more, that gave rise to STL containers (Standard Template Library).

Newsletter of programming:

Arrays with static and dynamic dimension. STL Part 1
5 (100%) 1 vote

About Olej

practical experience about software development 40 years. Teacher Global Logic international software company. IBM Developer Works Permanent author of publications. Scientific editor of the computer literature publishing house "Symbol-Plus", St. Petersburg.

2 thoughts on “Arrays with static and dynamic dimension. STL Part 1

  1. In C and C ++, there is a rule: instead arrays in function calls is transmitted pointer at the beginning of the array (This happened years 40-50 ago due to reasons of efficiency the computers). Therefore, the transfer function in the array information about its size is lost.
    Traditionally arrays are passed to the function as a 2 parameter: Index beginning of the array + the number of its elements. For example: void func( double arr[], int size ) или void function( double *arr, int size ).

Leave a Reply

Your email address will not be published. Required fields are marked *