Рекомендации по структуре данных STL

Question

Я реализую алгоритм отображения, в котором у нас может быть несколько слоев окон, основанных на их z-порядке, т.е. я начинаю с последнего z-значения и объединяю изображения, пока у нас не будет изображения с z-значением как 0 в Топ. Чтобы сохранить z-значения, какую структуру данных вы рекомендуете?

Например: если z-порядок равен 2 3 4 5 1 6 7 8 9 10 (индекс приложения) и если пользователь нажал на окно приложения 5, то нам нужно переместить 5 вперед и оставшийся порядок должен быть таким же, т.е. 5 2 3 4 1 6 7 8 9 10.

Если я использую вектор, то перестановка элементов (или копирование значений) каждый раз кажется неэффективной. Если я использую deque, то push_front имеет некоторое очевидное преимущество, но проблема заключается в том, чтобы снова удалить приложение из предыдущего положения. Если я использую список, то каждый раз нам нужно искать элемент и удалять его. Любые мысли о том, какая структура данных является наиболее эффективной для моих целей?

Answer 1

Учитывая, что количество окон, вероятно, будет минимальным, я бы, вероятно, пошел с вектором (умных) указателей и переупорядочил компоненты вектора.Хотя сложность выше, чем с другими альтернативами, фактическая производительность не будет плохой, так как константы могут доминировать в сложности.

Answer 2

Очевидный ответ - использование мульти-индекса усиления . Однако иногда это бывает сложно. Вы можете смоделировать это, имея две структуры:

• список для хранения порядка и значений
• карта для сопоставления значений с позициями в списке

Итак, вы можете получить что-то вроде:

typedef std::list<int> pos_list_t;
pos_list_t positions;
std::map<int, pos_list_t::iterator> position_map;

Затем каждый раз, когда вам нужно искать и менять позиции, вы можете сделать что-то вроде (упрощенно, но вы поняли):

pos_list_t::iterator pos = position_map[window_number];
// pos takes the list iterator. You can move it to the beginning
positions.erase(pos);
positions.push_front(window_number);
// update the map position
position_map[window_number] = positions.begin(); // iterator of the new position. The beginning.

Вам также потребуется некоторая совместная инициализация:

positions.push_back(value1);
positions.push_back(value2);
...
for (pos_list_t::iterator it = positions.begin(); it != positions.end(); ++it)
    position_map[*it] = it;

Answer 3

Что вы действительно собираетесь сделать:

1. найти элемент в определенной позиции
2. вставить новый элемент в начале
3. удалить элемент в определеннойposition
4. итерация по элементам

Так что, если вы используете list - у вас проблемы с 1. Если вы используете map.У вас проблемы с 4. Я бы сказал, пойти на вектор, который имеет константу для 1,2 и 4. И использовать какие-то маркеры для элемента, который необходимо удалить из коллекции.Поскольку у вас, вероятно, не будет миллионов окон, вы можете выполнять уборку внутри вектора довольно редко, скажем раз в 10 секунд.

Answer 4

Я бы использовал здесь просто std::list, потому что 1) итераторы списка никогда не делают недействительными (если объект не удаляется из списка) 2) разделение - это постоянное время (не очень важно, так как мы говорим о небольших списках).

Вы можете сохранить std::list<Window*> и связать std::list<Window*>::iterator в классе Window (при условии, что существует некоторый класс Window, который управляет ресурсом окна)

Answer 5

Вы используете карту, где ключ - это то, что необходимо для идентификации окна, а значение - это положение окна.Давайте предположим, что мы используем HWND для идентификации окна.

 map<HWND, int> windows

В начале вы должны инициализировать карту и установить для каждого окна правильную позицию.Ex.windows [0x0002] = 0;windows [0x0003] = 1;Карта будет упорядочена по значению.Когда вам нужно вывести окно вперед, вам просто нужно изменить его положение с окном 0 ордеров

int temp_order = windows[bringToFrontWindow]; 
HWND front_window = windows.begin().first; // the fist window of the map has 0 z-order
windows[bringToFrontWindow] = 0;
windows[front_window] = temp_order;

Answer 6

Похоже, что простой связанный список будет здесь наиболее удобным, а затем сортирует их по их z-значению.