Например, в следующем коде:
int myarray[3];
int x = myarray[1];
Гарантируется ли успешное выполнение кода за постоянное время, когда x
имеет некоторое целочисленное значение? Или компилятор может полностью пропустить вывод кода для этого или выдать код для запуска GNU Chess и при этом соответствовать стандарту C++?
Это полезно в структуре данных, похожей на массив, но может быть инициализирована за постоянное время. (Извините, у меня нет под рукой моей копии Ахо, Хопкрофта и Ульмана, поэтому я не могу найти имя.)
auto& x = myarray[1]; x = 123;
. Это то, что вам нужно для вашего алгоритма? - person Christian Hackl   schedule 06.04.2018T get(i)
,void set(i, T)
иeraseAllTo(T)
. Все три метода занимают время O(1) независимо от размера массива. См. cs.stackexchange.com/questions/492/ для реализации. Реализация также есть в книге «Алгоритмы + структуры данных» Ахо, Хопкрофта и Ульмана. - person Martin C. Martin   schedule 06.04.2018NULL
- это определенная, действительная вещь. Современным эквивалентом C++ будетstd::optional
. - person Christian Hackl   schedule 06.04.2018int f(int &x) { x=2; return 3;} int g(int &x) { x = 55; return 9;} int a; f(a) + g(a);
? Значениеa
равно 2 или 55, но стандарт не говорит, какое именно. То же самое дляfoo(b++, b++)
, не указано, какое приращение происходит первым, но это не неопределенное поведение. - person Martin C. Martin   schedule 06.04.2018V
начинается с неуказанного, но допустимого значения, поэтому сравнениеV[i] < pos
дает определенные результаты. Стандартный C++ не гарантирует, что это предположение выполняется, потому что такая гарантия сделает язык неприменимым для компьютерных архитектур, где определенные битовые комбинации в памяти или регистрах ЦП не представляют действительные целые числа (или другие типы). - person Christian Hackl   schedule 06.04.2018NULL
четко определено. Я имел в виду, что OP нужен надежный способ проверить, установлено ли что-то. Что невозможно, потому что для того, чтобы этот флаг был надежным, кто-то сначала должен его установить... тем самым разрушая любые попытки использовать его для повышения производительности. - person underscore_d   schedule 07.04.2018