Какую структуру данных использовать

Question

Я ищу структуру данных, которая имеет следующие свойства.

• Сохраняет список tuple<Double,Integer,Integer>.Заказ только на double.Два кортежа с одинаковым двойным значением считаются одинаковыми.
• Поддерживает дубликаты.
• Необходимо иметь возможность перемещаться в порядке возрастания.Если есть дубликаты, добавленные позже должны иметь более высокий порядок.
• Быстрый поиск / вставка
• Быстрое удаление, обратите внимание, что удаление всегда следует этому шаблону

Методсодержит remove:

for(int i=list.size()-1;i>=0;i--){// assume list is in ascending order
    if(list[j:i] can be merged){
        remove list[j:i-1];
        update list[i]'s two integers;
        i = j-1;
    }
}

В настоящее время я использую ArrayList и сохраняю его отсортированным.Поиск быстрый с бинарным поиском.Однако для вставки и удаления потребуется много копий в памяти, например, вставка в начале списка сдвигает все элементы.

Answer 1

Одним из решений было бы иметь отсортированную карту со списками кортежей:

SortedMap<Double,List<Tuple<Integer,Integer>>>

Строка объявления немного некрасива, но она будет работать. Я использовал карты для списков много раз прежде. Приятно то, что вы можете удалять элементы из списков, и если у вас короткие списки, у вас меньше ходов. Чтобы выполнить итерацию по всей структуре, вам нужно создать собственный итератор или адаптировать исходный код.

Answer 2

Если вы решили написать свой собственный двойной компаратор, есть несколько вещей, о которых следует знать.

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

Второй хитрость заключается в том, что компараторы работают с объектами, что означает, что вы будете работать с двойными числами, а не с двойными. Следующие четыре операции приводят к распаковке Double в double: <, <=,> и> =. Следующие два не вызывают распаковку: == и! =. Эти два оператора выполняют сравнения указателей памяти объекта. Итог, вручную распакуйте двойники в двойники перед выполнением сравнений; это значительно уменьшит количество ошибок.