Прежде, чем приступать к обзору контейнерных типов библиотеки STL, разумно освежить в памяти информацию об организации массивов C и C++. Потому что контейнеры STL — это некоторые альтернативные формы организации коллекций данных, свободные от ограничений массивов.
Массивы — одна из самых используемых форм организаций данных, и исторически одна из самых первых форм, появившихся в языках программирования (языки конца 50-х годов XX века). Массив — это представление набора последовательных однотипных элементов. Принципиально важным в таком определении являются 2 момента, которые для массива должны выполняться обязательно:
Каждый элемент массива нужно указать номером его местоположения в последовательности подобных элементов.
Все элементы массива должны обязательно быть однотипными. Всем знакомы и понятны простейшие определения, например, целочисленных массивов: int array[100] . Но это вовсе не означает, что в массивы могут организовываться только простейшие встроенные типы языка C++. В массив могут организовываться объекты-переменные любого составного типа (класса, структуры) и степени сложности. Единственным ограничением является то, что все элементы одного массива должны быть одного типа. Например, так может описываться студенческая группа:
К этому крайне важному обстоятельству — типы элементов массива — мы ещё вернёмся в дальнейшем.
Ещё со времён самых ранних языков программирования (FORTRAN и др.), на массивы накладывалось сильное ограничение: размер массива должен определяться только целочисленной константой, значение которой должно быть определено на момент компиляции кода. То же самое ограничение сохранилось и в языке C, который стал прародителем C++. Например:
В C++ (в классическом, кроме стандартов последних лет!) это ограничение незначительно ослаблено до того, что размер массива может быть целочисленной константой, значение которой может вычисляться на момент компиляции кода. Например, так:
1 2 3 4 5 6 7 8 9 10 11 | #include <iostream> using namespace std; int main(void) { float array[(int)(10. * 10.) + 2]; cout << "array size = " << sizeof(array) / sizeof(array[0]) << endl; } |
Во всех таких случаях, после определения массива размер его фиксируется и мы никак не сможем увеличить его размер (если, например, в ходе вычислений окажется, что нам не хватает этого размера). Так определенные массивы называются массивами со статически объявленным (в момент написания кода) размером.
Примечание: Из-за того, что все элементы массива располагаются последовательно (1-е правило из названных выше), для вычисления размера массива (в области его видимости) можно использовать показанный в примере трюк: размер массива равен длине всего массива, делённой на длину любого его элемента (поскольку все они одинаковые по типу).
Может показаться, что по-другому определяются массивы без указания размера, но со списком инициализирующих значений:
Но это не так! Просто здесь константное значение размера объявляемого массива извлекается из списка значений, и равно, в показанном примере 5.
Единственным способом создать массив, в классических C и C++, размером в N элементов, вычисляемым в момент создания массива (на этапе выполнения) — это был способ динамического размещения массива. Которое в C и C++ делается, соответственно:
1 2 | double *array = (double*)calloc( N, sizeof( double ) ); // это C double *array = new double[ N ]; // а это C++ |
Например, так:
1 2 3 4 5 6 7 8 9 10 11 | #include <iostream> #include <cmath> using namespace std; int main(void) { const double PI = 3.1415; int size = (int)(sin(PI / 2) * pow(2, 10)); float *array = new float[size]; cout << "array size = " << size << endl; delete[] array; } |
Самые поздние стандарты (C99, C++11) внесли расширения, которые допускают создание локальных массивов в функциях с размерами, вычисляемыми при входе в функцию. При таких условиях массив будет выделен в стеке функции. Это уже весьма существенно, когда мы не можем знать наперед размер обрабатываемых данных. В качестве примера посмотрим задачу нахождения всех простых чисел, не превосходящих N (решето Эратосфена), где N задаётся при запуске программы.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #include <iostream> #include <cinttypes> #include <cstdlib> using namespace std; int main(int argc, char **argv) { unsigned long k, j, n; // верхняя граница bool a[n = atoi(argv[1]) + 1]; a[0] = a[1] = false; for (k = 2; k < n; k++) a[k] = true; for (k = 2; k < n; k++) for (j = k + k; j < n; j += k) // вычеркивание всех чисел кратных k a[j] = false; const int line = 10; for (k = 0, j = 0; k < n; k++) if (a[k]) { cout << k << "\t"; if (0 == ++j % line) cout << endl; } if (j % line != 0) cout << endl; return 0; } |
Этот код мы уже обязаны компилировать с указанием стандарта C++ 2011 года (опциями или компилятора, или свойствами собираемого проекта):
Но даже после всех расширений, простейший массив, как форма организации набора объектов, оказывается недостаточно гибким. Главные из ограничивающих факторов:
Как бы не определялся размер массива (константой или вычислением в точке определения) в дальнейшем увеличить этот размер невозможно (если не угадали заранее требуемый размер, или не заложили достаточный запас).
По правилам C/C++ при вызове функций вместо массива в качестве параметра вместо массива передаётся указатель на его начало (адрес 1-го элемента). Это позволяет сильно повысить эффективность многих вычислительных алгоритмов, но при этом теряется информация о размере массива, и её необходимо передавать отдельным параметром. Например, если бы мы хотели формировать решето Эратосфена не в функции main(), а в отдельной функции, то мы должны были бы формировать её вызов как erastof ( a, n ).
Многие интуитивно простейшие операции над массивами вызывают сложности. Например: в 15-ти элементном массиве элемент под номером 10 надо вставить между элементами 2 и 3. При этом а). все элементы с 3 по 9 нужно копировать на одну позицию вправо, б). делать это можно только в нисходящем порядке от 9 к 3 и в). за всеми индексами этих операций необходимо следить в ручном режиме.
Потребности практики требовали большего, что и породило контейнеры STL (Standard Template Library).
В C и C++ существует правило: вместо массивов при вызове функций передаётся указатель на начало массива (это сложилось лет 40-50 назад из-за соображений эффективности тех компьютеров). Поэтому при передаче массива в функцию информация о его размере теряется.
Традиционно массивы передаются в функцию как 2 параметра: указатель начала массива + число его элементов. Например: void func( double arr[], int size ) или void func( double *arr, int size ).
Хороший урок. Коротко и ясно.
У вас на этой странице есть ошибка когда открываеш “Что сделать, чтобы программа работала в MVS” то снизу описание программы, может это только у меня так посмотрите пожалуйста