Нужен аналог QQueue с случайными доступом к элементам

[Admin]

Есть очередь QQueue. Хочется функцию получения(удаления) элемента из случайного места очереди?
Есть ли какие нибудь идеи?

[BRE]

Ну так QQueue наследуется от QList, а там все это есть.

[Admin]

а нельзя ли поподробнее с примером
PS: пятница)

[nixman05]

Вообще то QQueue реализует динамическую структуру данных с дисциплиной LIFO

т.е. добавляются элементы с одного конца, а удаляются с другого. Известны указатели на начало и конец очереди.

[lit-uriy]

2 Admin, дык может Список и пользовать (QList)?

[BRE]

а нельзя ли поподробнее с примером
PS: пятница)

Код

C++ (Qt)
QQueue<int> q;
 
// Добавили в очередь три числа 1, 2, 3
q.enqueue( 1 );
q.enqueue( 2 );
q.append( 3 );
 
// Получить элемент с нужным индексом
int val3 = q.value( 2 );
int val1 = q[ 0 ];
 
// Удалить элемент с нужным индексом
q.removeAt( 1 );
 

[nixman05]

а нельзя ли поподробнее с примером
PS: пятница)

Код

C++ (Qt)
QQueue<int> q;
 
// Добавили в очередь три числа 1, 2, 3
q.enqueue( 1 );
q.enqueue( 2 );
q.append( 3 );
 
// Получить элемент с нужным индексом
int val3 = q.value( 2 );
int val1 = q[ 0 ];
 
// Удалить элемент с нужным индексом
q.removeAt( 1 );
 

Это все конечно хорошо но не корректно.  Очередь это очередь, Стек это стек.  Список это список. С очереди нельзя получить доступ к произвольному элементу. Список позволяет это сделать. Для того чтобы получить доступ к произвольному элементу очереди, удаляя их из очереди и сохраняя в вспомогательную очередь, затем изменить элемент и после этого восстановить  удаленные элементы очереди.

[Rcus]

Продолжая цепочку утверждений: std это std, Qt это Qt. Спасибо, капитан, вы просто открыли нам глаза, что бы мы без вас делали.

[spectre71]

Есть очередь QQueue. Хочется функцию получения(удаления) элемента из случайного места очереди?
Есть ли какие нибудь идеи?

Хотелось бы узнать подробнее о параметрах задачи.
1) Какой длины очередь:
    - всегда короткая
    - всегда длинная
    - любая или неизвестно
2) Как часто происходит выбока елемента из очереди
3) Как часто происходит доступ к произвольному елементу очереди
4) Как часто происходит удаление произвольного елемента очереди
Понятия "часто" и "длина" зависят друг от друга и влияют на производительность только для конкретной задачи.

К примеру если очередь короткая и операции с элементами происходят редко, то тупо берем список и не заморачиваемся псевдооптимизацией.



   

[spectre71]

Пример для очереди.
1) Какой длины очередь: ограниченная не больше N элементов, не жалко памяти на постоянное содержания N элементов
2) Как часто происходит выбока елемента из очереди - очень часто
3) Как часто происходит доступ к произвольному елементу очереди  - очень часто
4) Как часто происходит удаление произвольного елемента очереди - очень редко

Берем обычный список и "ЗАКОЛЬЦОВЫВАЕМ" его:
Храним два индекса на начало и конец очереди, изменяем их на операциях добавления и выборки,
Перезаписываем указатель на объект на операции добавления.

[spectre71]

В общем случае через постронение и манипуляции с бинарным деревом, можно свести стоимость операций:

вставка, удаление получение по идексу = Co*log(N)
А для сортированного(с поддержкой автосортировки) операция получение по ключу = Co*log(N)

Построение дерева = Co*N*log(N)
Стоимость сортировки зависит от текущего алгоритма сортировки и = Cost(ListSortAlg) + Построение дерева.

N   - кол-во элементов списка.
Co - констана в зависимости от операции
log - логарифм

[Admin]

Я сделал уже с QList, а очередь не большая - примерно 1000 элементов всего)

[spectre71]

До 1000-10000 элементов лучше с деревом и не и не заморачиваться.
Констатнты стоимости опраций вставки/удаления огромны.
А кольцо попробуй - если частое случайное чтение.