Всегда ли расположение графического интерфейса всегда есть экспоненциальная сложность? ⇐ C++

[Anonymous]

Я проектирую простой графический интерфейс «структура» с виджетами и макетами. Давайте проиллюстрируем проблему на простом примере основного горизонтального макета, который помещает его детские виджеты рядом друг с другом, и если в конце осталось места, оно оставит его пустым. Вертикально все они будут растянуты до полной высоты макета. Горизонтальная планировка просит каждого ребенка взять минимально возможное пространство горизонтально. С другой стороны, измерения макета корня (которая заполняет окно приложения) известны, поэтому, если горизонтальная планировка была макетом корня, мы бы знали высоту каждого ребенка.

Код: Выделить всё

Dimensions layout(Dimensions minDimensions, Dimensions maxDimensions);
< /code>
Итак, для первого ребенка в горизонтальном макете это будет < /p>
child->layout(Dimensions(0, parentMinDimensions.height), parentMaxDimensions);
< /code>
Поскольку его ширина может быть произвольно мала, но не больше, чем у всей макета, и вертикально, она должна соответствовать макету, поэтому применяются те же ограничения.Dimensions layout(Dimensions minDimensions, Dimensions maxDimensions) {
int remainingWidth = maxDimensions.width;
for (Widget *child : children) {
Dimensions childDimensions = child->layout(
Dimensions(0,              minDimensions.height),
Dimensions(remainingWidth, maxDimensions.height)
);
remainingWidth -= childDimensions.width;
minDimensions.height = max(minDimensions.height, childDimensions.height);
}
return Dimensions(maxDimensions.width-remainingWidth, minDimensions.height);
}
< /code>
выглядит хорошо, но есть одна проблема. Предполагалось, что макет должен растянуть всех детей вертикально до его высоты, но если горизонтальная компоновка, например, является ребенком вертикальной макета, то высота входного минима и максимальная высота, и каждый виджет может в конечном итоге с другой высотой. И вот где возникает проблема. Я не верю, что это можно решить без оценки макета каждого ребенка дважды: < /p>
Dimensions layout(Dimensions minDimensions, Dimensions maxDimensions) {
// First pass - determine height
int height = minDimensions.height;
int remainingWidth = maxDimensions.width;
for (Widget *child : children) {
Dimensions childDimensions = child->layout(
Dimensions(0,              minDimensions.height),
Dimensions(remainingWidth, maxDimensions.height)
);
remainingWidth -= childDimensions.width;
height = max(height, childDimensions.height);
}
// Second pass - apply height
remainingWidth = maxDimensions.width;
for (Widget *child : children) {
Dimensions childDimensions = child->layout(
Dimensions(0,              height),
Dimensions(remainingWidth, height)
);
remainingWidth -= childDimensions.width;
}
return Dimensions(maxDimensions.width-remainingWidth, height);
}
< /code>
Макеты организованы в иерархию дерева произвольного размера и глубины, а также оценивают весь поддерек в каждом узле более одного раза, что приводит к экспоненциальной сложности. Существуют некоторые сценарии, где макет должен быть быстро пересекает каждый кадр, например, когда пользователь изменяет размер окна, так что это было бы плохо. Время выполнения даже в худшем случае сценария (и без жертвы гибкости макетов).
[b] сноска [/b] 
Я знаю, что вместо того, чтобы вызовать макет 

дважды, я могу вместо этого иметь две функции, такие как
Dimensions measure(Dimensions minDimensions, Dimensions maxDimensions);
void layout(Dimensions exactDimensions);
< /code>
и, возможно, даже гарантирует, что первый только когда -либо пересекает дерево только один раз, но в приведенном выше примере мне все равно придется вызвать оба в функции макета для каждого ребенка, поэтому экспоненциальная сложность все еще там. Кроме того, у меня больше не было бы возможности пропускать второй раунд, если бы MIN и максимальная высота были равны, поэтому я не верю, что это даже было бы полезно во всех случаях. Экспоненциальная сложность "Big O" - это то, что меня интересует, а не постоянная оптимизация факторов.


Подробнее здесь: https://stackoverflow.com/questions/790 ... complexity