Если отсортированная коллекция ArrayList расширяется за ее первоначальный размер, становится ли она несортированной?

Question

У меня есть ArrayList, который я сортирую изначально. Когда я добавляю к нему, я делаю:

Index = Collections.binarySearch(Data.fileList, fileEntry, FileData.COMPARE_BY_FNAME);

if (Index >=0)
  fileEntry = Data.fileList.get(Index)  // get the object that matches
else
  Data.fileList.add ((Index+1)*-1, fileEntry)  // add the new object

, который добавляет запись в правильное местоположение, поэтому мне не нужно снова сортировать (я полагаю).

Когда ArrayList становится большим, я получаю повторяющиеся записи, поэтому я предполагаю, что он больше не сортируется.

Я думаю, что когда ArrayList превышает свой первоначальный размер и расширяется, моя коллекция больше не сортируется.

Q1) Это правда? Q2) Есть ли способ узнать, если коллекция больше не сортируется? Есть ли способ узнать, был ли расширен ArrayList? Или я должен делать сортировку после каждой вставки? Q3) ArrayList.size () возвращает количество элементов в списке. Есть ли способ определить емкость списка?

Спасибо. -J

Answer 1

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

Answer 2

Когда ArrayList становится большим, я получаю повторяющиеся записи, поэтому я предполагаю, что он больше не сортируется.

Он остается отсортированным до тех пор, пока вы добавляете нужные элементы.место нахождения.Не совсем понятно, что вы подразумеваете под «дубликатами записей», но нет ничего о расширении ArrayList, которое будет переупорядочивать его.

С другой стороны, использование отсортированной коллекции для начала (как предложеноОскар Лопес) сделает вашу жизнь проще.

Answer 3

Изменение размера не имеет к этому никакого отношения.Порядок сортировки не является частью контракта List.Список - это просто упорядоченная коллекция.Порядок зависит от того, кто добавляет элементы.Когда ArrayList изменяет размеры, он просто перераспределяет базовый массив и копирует существующие данные в новый массив в том же порядке.

Как упоминалось выше, вы должны использовать SortedSet (в частности, TreeSet), еслиВы хотите, чтобы вещи сортировались по мере их добавления.Если вы хотите разрешить дублирование класса TreeBag в commons-collection, это хороший вариант.

Answer 4

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

Если вы хотите разрешить дублирование, PriorityQueue - ваш лучший выборЕсли вы можете игнорировать дубликаты, лучше использовать TreeSet.