Почему массивы переменной длины не являются частью стандарта C++?
Я не очень много использовал C в последние несколько лет. Когда я прочитал этот вопрос сегодня, я натолкнулся на некоторый синтаксис Си, с которым я не был знаком.
Видимо в C99 действует следующий синтаксис:
void foo(int n) {
int values[n]; //Declare a variable length array
}
Это кажется довольно полезной функцией. Были ли когда-нибудь дискуссии о добавлении его в стандарт C++, и если да, то почему он был опущен?
Некоторые потенциальные причины:
- Волосатость для поставщиков компиляторов для реализации
- Несовместим с какой-либо другой частью стандарта
- Функциональность можно эмулировать с другими конструкциями C++
Стандарт C++ утверждает, что размер массива должен быть константным выражением (8.3.4.1).
Да, конечно, я понимаю, что в игрушечном примере можно использовать std::vector<int> values(m);, но это выделяет память из кучи, а не из стека. И если я хочу многомерный массив, как:
void foo(int x, int y, int z) {
int values[x][y][z]; // Declare a variable length array
}
vector версия становится довольно неуклюжей:
void foo(int x, int y, int z) {
vector< vector< vector<int> > > values( /* Really painful expression here. */);
}
Срезы, строки и столбцы также могут быть распространены по всей памяти.
Глядя на обсуждение в comp.std.c++ ясно, что этот вопрос довольно спорный с некоторыми очень тяжелыми именами по обе стороны аргумента. Это, конечно, не очевидно, что std::vector всегда лучшее решение.
14 ответов
Недавно в usenet началось обсуждение этого вопроса: почему нет никаких VLA в C++0x.
Я согласен с теми людьми, которые, похоже, согласны с тем, что создавать потенциально большой массив в стеке, в котором обычно мало свободного места, нехорошо. Аргумент: если вы заранее знаете размер, вы можете использовать статический массив. И если вы не знаете размер заранее, вы напишите небезопасный код.
VLA C99 могли бы обеспечить небольшое преимущество, заключающееся в возможности создания небольших массивов без потери пространства или вызова конструкторов для неиспользуемых элементов, но они будут вносить довольно большие изменения в систему типов (необходимо иметь возможность указывать типы в зависимости от значений времени выполнения - это еще не существует в текущем C++, за исключением new спецификаторы типа оператора, но они обрабатываются специально, так что время выполнения не выходит за рамки new оператор).
Ты можешь использовать std::vector, но это не совсем то же самое, поскольку он использует динамическую память, и заставить его использовать собственный распределитель стека не совсем легко (выравнивание также является проблемой). Это также не решает ту же проблему, потому что вектор является контейнером с изменяемым размером, тогда как VLA имеют фиксированный размер. Предложение C++ Dynamic Array предназначено для представления решения на основе библиотеки, как альтернативы VLA на основе языка. Тем не менее, насколько я знаю, он не будет частью C++0x.
(Справочная информация: у меня есть некоторый опыт реализации компиляторов C и C++.)
Массивы переменной длины в C99 были в основном ошибкой. Чтобы поддержать VLA, C99 должен был пойти на следующие уступки здравому смыслу:
sizeof xбольше не всегда константа времени компиляции; компилятор должен иногда генерировать код для оценкиsizeof-выражение во время выполнения.Разрешение двумерных VLA (
int A[x][y]) требуется новый синтаксис для объявления функций, которые принимают 2D VLA в качестве параметров:void foo(int n, int A[][*]),Менее важно в мире C++, но чрезвычайно важно для целевой аудитории программистов встраиваемых систем на C, объявление VLA означает разбрасывание произвольно большого куска вашего стека. Это гарантированное переполнение стека и сбой. (В любое время вы объявляете
int A[n]вы неявно утверждаете, что у вас есть 2 ГБ стека, чтобы сэкономить. Ведь если знаешьnздесь определенно меньше 1000 ", тогда вы просто заявитеint A[1000], Подставляя 32-битное целое числоnза1000это признание того, что вы не представляете, каким должно быть поведение вашей программы.)
Хорошо, теперь давайте перейдем к разговору о C++. В C++ мы имеем такое же сильное различие между "системой типов" и "системой ценностей", как в C89… но мы действительно начали полагаться на него так, как это не делает C. Например:
template<typename T> struct S { ... };
int A[n];
S<decltype(A)> s; // equivalently, S<int[n]> s;
Если n не была константой времени компиляции (то есть, если A были переменно модифицированного типа), то, что на земле будет тип S? Было бы S Тип также определяется только во время выполнения?
Как насчет этого:
template<typename T> bool myfunc(T& t1, T& t2) { ... };
int A1[n1], A2[n2];
myfunc(A1, A2);
Компилятор должен сгенерировать код для некоторой реализации myfunc, Как должен выглядеть этот код? Как мы можем статически генерировать этот код, если мы не знаем тип A1 во время компиляции?
Хуже того, что если во время выполнения окажется, что n1 != n2, чтобы !std::is_same<decltype(A1), decltype(A2)>()? В этом случае вызов myfunc не должен даже компилироваться, потому что вывод типа шаблона должен потерпеть неудачу! Как мы можем подражать этому поведению во время выполнения?
По сути, C++ движется в направлении внедрения все большего и большего количества решений во время компиляции: генерация кода шаблона, constexpr оценка функции и так далее. Тем временем C99 был занят продвижением традиционно решений времени компиляции (например, sizeof) во время выполнения. Имея это в виду, действительно ли имеет смысл тратить какие-либо усилия на интеграцию VLA в стиле C99 в C++?
Как уже отмечал любой другой ответчик, C++ предоставляет множество механизмов выделения кучи (std::unique_ptr<int[]> A = new int[n]; или же std::vector<int> A(n); очевидно), когда вы действительно хотите донести идею: "Я понятия не имею, сколько ОЗУ мне может понадобиться". А C++ предоставляет изящную модель обработки исключений для решения неизбежной ситуации, когда объем необходимой вам оперативной памяти больше, чем у вас. Но, надеюсь, этот ответ дает вам хорошее представление о том, почему VLA в стиле C99 не очень подходят для C++ - и даже не совсем подходят для C99.;)
Подробнее об этой теме см. N3810 "Альтернативы для расширений массивов", документ Bjarne Stroustrup за октябрь 2013 года о VLA. POV Бьярне очень отличается от моего; N3810 больше фокусируется на поиске хорошего синтаксиса C++ для вещей и на препятствовании использованию сырых массивов в C++, тогда как я больше сосредоточился на последствиях для метапрограммирования и системы типов. Я не знаю, считает ли он последствия метапрограммирования / системы типов решенными, разрешимыми или просто неинтересными.
Вы всегда можете использовать alloca() для выделения памяти в стеке во время выполнения, если хотите:
void foo (int n)
{
int *values = (int *)alloca(sizeof(int) * n);
}
Распределение по стеку подразумевает, что он будет автоматически освобожден при размотке стека.
Краткое примечание. Как упоминалось на справочной странице Mac OS X для alloca(3), "функция alloca() зависит от машины и компилятора; ее использование не рекомендуется". Просто чтобы ты знал.
В своей собственной работе я понял, что каждый раз, когда я хотел что-то вроде автоматического массива переменной длины или alloca(), мне было все равно, что память физически расположена в стеке процессора, а только из некоторый распределитель стека, который не вызывал медленные поездки в общую кучу. Так что у меня есть объект для каждого потока, которому принадлежит некоторая память, из которой он может выдвигать / выталкивать буферы переменного размера. На некоторых платформах я позволяю этому расти через mmu. Другие платформы имеют фиксированный размер (обычно сопровождаемый стеком процессоров фиксированного размера, потому что нет MMU). Одна платформа, с которой я работаю (портативная игровая консоль), в любом случае имеет очень маленький стек процессоров, потому что она находится в дефицитной, быстрой памяти.
Я не говорю, что вставка буферов переменного размера в стек процессора никогда не нужна. Честно говоря, я был удивлен, когда обнаружил, что это не стандартно, так как кажется, что концепция достаточно хорошо вписывается в язык. Однако для меня требования "переменный размер" и "должны быть физически размещены в стеке процессора" никогда не встречались. Речь шла о скорости, поэтому я создал свой собственный "параллельный стек для буферов данных".
Кажется, это будет доступно в C++ 14:
https://en.wikipedia.org/wiki/C++14
Обновление: это не сделало это в C++14.
Существуют ситуации, когда выделение динамической памяти очень дорого по сравнению с выполняемыми операциями. Примером является матричная математика. Если вы работаете с небольшими матрицами, скажем, от 5 до 10 элементов, и выполняете много арифметических операций, издержки malloc будут действительно значительными. В то же время превращение размера в постоянную времени компиляции кажется очень расточительным и негибким.
Я думаю, что C++ настолько небезопасен сам по себе, что аргумент "стараться не добавлять больше небезопасных возможностей" не очень силен. С другой стороны, поскольку C++, пожалуй, является наиболее эффективными функциями языка программирования во время выполнения, что делает его еще более полезным: люди, которые пишут программы, критичные к производительности, будут в значительной степени использовать C++, и им потребуется как можно больше производительности. Перемещение вещей из кучи в стек - одна из таких возможностей. Уменьшение количества блоков кучи - другое. Разрешение VLA в качестве членов объекта будет одним из способов достижения этого. Я работаю над таким предложением. По общему признанию, это немного сложно реализовать, но кажется вполне выполнимым.
Это рассматривалось для включения в C++/1x, но было исключено (это исправление к тому, что я говорил ранее).
В любом случае это было бы менее полезно в C++, так как у нас уже есть std::vector чтобы заполнить эту роль.
VLA являются частью большого семейства изменяемых типов. Это семейство типов очень особенное, потому что они содержат компоненты среды выполнения .
Код:
int A[n];
Компилятор видит:
typedef int T[n];
T A;
Обратите внимание, что размер массива во время выполнения не привязан к переменной
Ничто не мешает создавать новые переменные этого типа:
T B,C,D;
или указатели или массивы
T *p, Z[10];
Более того, указатели позволяют создавать VLA с динамической памятью.
T *p = malloc(sizeof(T));
...
free(p);
Что развеивает популярный миф о том, что VLA можно размещать только в стеке.
Вернемся к вопросу.
Этот компонент среды выполнения плохо работает с выводом типов, который является одной из основ системы типизации C++. Было бы невозможно использовать шаблоны, дедукцию и перегрузку.
Система типизации C++ статична, все типы должны быть полностью определены или выведены во время компиляции . Типы ВМ завершаются только во время выполнения программы . Дополнительная сложность, связанная с введением типов ВМ в и без того адски сложный C++, просто посчиталась неоправданной. В основном потому, что их основное практическое применение - автоматические VLA (
Это немного печально, потому что типы виртуальных машин предоставляют очень элегантные и эффективные решения для программ, работающих с многомерными массивами.
На C можно просто написать:
void foo(int n, int A[n][n][n]) {
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
for (int k = 0; k < n; ++k)
A[i][j][k] = i * j * k;
}
...
int A[5][5][5], B[10][10][10];
foo(5, A);
foo(10, B);
Теперь попробуем предоставить максимально эффективное и элегантное решение на C++.
Подобные массивы являются частью C99, но не являются частью стандартного C++. как уже говорили другие, вектор всегда является гораздо лучшим решением, поэтому, вероятно, поэтому массивы переменного размера не входят в стандарт C++ (или в предложенный стандарт C++0x).
Кстати, для вопросов о том, "почему" стандарт C++ таков, модерируемая группа новостей Usenet comp.std.C++ - это то место, куда можно обратиться.
Для этого используйте std::vector. Например:
std::vector<int> values;
values.resize(n);
Память будет выделяться в куче, но это содержит лишь небольшой недостаток производительности. Кроме того, не стоит выделять большие блоки данных в стеке, так как он довольно ограничен по размеру.
C99 позволяет VLA. И это накладывает некоторые ограничения на то, как объявлять VLA. Подробнее см. 6.7.5.2 стандарта. C++ запрещает VLA. Но g++ это позволяет.
Если вы знаете значение во время компиляции, вы можете сделать следующее:
template <int X>
void foo(void)
{
int values[X];
}
Редактировать: Вы можете создать вектор, который использует распределитель стека (alloca), поскольку распределитель является параметром шаблона.
Вам нужно постоянное выражение для объявления массива в C/C++.
Для массивов динамического размера вам необходимо выделить память в куче, а затем управлять временем жизни этой памяти.
void foo(int n) {
int* values = new int[n]; //Declare a variable length array
[...]
delete [] values;
}
У меня есть решение, которое действительно работает для меня. Я не хотел выделять память из-за фрагментации подпрограммы, которую нужно было запускать много раз. Ответ чрезвычайно опасен, поэтому используйте его на свой страх и риск, но он использует преимущества сборки, чтобы зарезервировать место в стеке. В моем примере ниже используется массив символов (очевидно, для переменной другого размера потребуется больше памяти).
void varTest(int iSz)
{
char *varArray;
__asm {
sub esp, iSz // Create space on the stack for the variable array here
mov varArray, esp // save the end of it to our pointer
}
// Use the array called varArray here...
__asm {
add esp, iSz // Variable array is no longer accessible after this point
}
}
Опасностей здесь много, но я объясню несколько: 1. Изменение размера переменной на полпути убило бы позицию стека 2. Превышение границ массива уничтожило бы другие переменные и возможный код 3. Это не работает в 64-битной среде build... нужна другая сборка для этого (но макрос может решить эту проблему). 4. Специфично для компилятора (могут возникнуть проблемы при перемещении между компиляторами). Я не пробовал, поэтому я действительно не знаю.