0

Необходимо подобрать структуру данных для хранения данных z-index. Все индексы должны быть уникальными и для них должна быть определена операция сравнения. Операции со структурой: добавление индекса, который больше или меньше другого индекса, добавление индекса, большего максимального индекса, удаление индекса.

3
  • обычная трехмерная матрица подойдет?
    – perfect
    2 янв 2015 в 20:01
  • @perfect можно подробнее?
    – Im ieee
    3 янв 2015 в 12:14
  • @Im ieee просто z-index это обычно указатель глубины. например есть окно которое лежит поверх другого окна у него есть координаты в пространстве 1-я размерность матрицы указывает его расположение по горизонтали 2-я размерность указывает его положение по вертикали, а 3-я указывает на его положения в глубину (между другими окнами). так можно получить любой пиксел этого окна в любой момент времени
    – perfect
    4 янв 2015 в 9:38

1 ответ 1

0

Вам нужен лишь список z-индексов (тогда базируйтесь на std::set), или z-index для группы объектов (тогда например std::map<double, VisualObject*>)?


Смотрите. Если у вас есть std::set<double>, то все операции выполняются просто.

  1. Уникальность — свойство std::set.
  2. Сравнимость: элементы типа double сравниваются «из коробки».
  3. Добавление индекса после данного:
    • убеждаетесь, что элемент есть во множестве;
    • получаете следующий (upper_bound);
    • подсчитываете среднее арифметическое этих элементов и вставляете во множество
  4. добавление элемента меньше минимального: получаете минимальный (begin, т. к. множество отсортировано), вставляете среднее арифметическое минимального и DOUBLE_MIN. То же для максимального.
  5. Удаление из коробки.

Единственный «скользкий» случай — если при вычислении среднего арифметического в пункте 3 оно окажется равным одному из чисел. Такое может быть, если вы вставляете очень много элементов. В этом случае придётся перенумеровать все индексы: подсчитать количество элементов, и в i-ый по порядку элемент записать число i.

10
  • Просто список z-индексов. На мой взгляд, выбор контейнера — дело второстепенное, основная сложность в том, как при добавлении нового индекса избежать изменения значений большого количества соседних индексов. Наверняка же есть структуры для равномерного или близкого к равномерному распределения целых чисел.
    – Im ieee
    3 янв 2015 в 12:13
  • @Im ieee, по крайней мере в Linux STL set реализован на rb-tree, поэтому добавление нового индекса стоит O(log N). Кстати, обход по итератору происходит по порядку возрастания значений элементов.
    – avp
    3 янв 2015 в 12:26
  • @avp Ну а для двусвязного списка вообще O(1). Дело в другом: допустим, индекс это просто целое число. Тогда при добавлении индекса, большего какого-то другого индекса, если следующие несколько чисел-индексов заняты, то их придётся увеличить. Очевидно, необходимо, чтобы подобное увеличение (или уменьшение) происходило как можно реже.
    – Im ieee
    3 янв 2015 в 12:39
  • @Im ieee, видимо, я не знаком с какой-то спецификой z-индексов (мне казалось, что требуется добавлять новые элементы в произвольные места структуры, сохраняя ее упорядоченность). А что Вам нужно на самом деле? (если можно, то объясните "на пальцах" (для дилетанта в этой области)).
    – avp
    3 янв 2015 в 12:45
  • @avp Так и есть, новые элементы в произвольные места структуры. Например, в плохой реализации, у нас есть двусвязный список индексов i1=1, i2=2, i3=3, i4=4. Нужно добавить индекс i больший i1 и меньший i2. Для этого нужно увеличить все индексы большие i1, то есть i2, i3 и i4, на 1, а i будет равно двум. Итоговый список индексов i1=1, i=2, i2=3, i3=4, i4=5.
    – Im ieee
    3 янв 2015 в 13:00

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.