Russian Qt Forum

Есть список из интов. Как удалить повторяющиеся элементы через алгоритмы?

Можно:
1) отсортировать список(  алгоритмов полно, выбирайте что нравится)
2) Бежать итератором по списку и удалять если текущий равен предыдущему.
3) Учесть что итераторы, вроде как, портятся при удалении элементов ( хотя могу ошибаться).
Тогда все элементу будут уникальными.
Если сортировать не надо, а надо сохранить последовательность то
1) сделать новый список
2) Бежать итератором по исходному списку и, если элемент не содержится в новом списке, добавлять в новый список ( проверить можно bool QList::contains ( const T & value ) const).
3) Подменить исходный список новым
По поводу скорости вариантов рассуждать уже вам.
Если подумать то можно и лучше придумать.

template <class T> 
void RemoveListDup( QList <T> & lst )
{
  QSet <T> qs;
  int i, place = 0, limit = lst.size();
  for (i = 0; i < limit; ++i) {
    T & val = lst[i]; 
    if (qs.contains(val)) continue;
    qs.insert(val);
    if (i != place) lst[place] = val;
    ++place;
  }
  lst.erase(lst.begin() + place, lst.end());
}

Вот и пример второго варианта ( не совсем, конечно, но суть таже). Но итератором бегать будет существенно быстрее чем в цикле брать элемент по номеру. Я бы использовал именно его. Да и в случае использования const_iterator QSet::insert ( const T & value ) не вижу смысла использовать contains.
Из справки:
const_iterator QSet::insert ( const T & value )
Inserts item value into the set, if value isn't already in the set, and returns an iterator pointing at the inserted item.
Значит в место:
Можно написать:
Что уберет весьма затратную contains.
Хотя все вопросы о скорости зависят от нужд и "структуры" содержимого списка.

Самый простой вариант это пушать элемент, проверяя его на вместимость в списке (если нет - то вставлять в список)
Спасибо за ответы

Правильно заданный вопрос содержит половину ответа. Вы  писали "есть список интов", а раз список уже есть я бы даже и не предположил что есть шанс влиять на алгоритмы создания списка. Но раз такой шанс... Зачем тогда QList, раз хранить надо только уникальные элементы? QSet, вроде, тут выглядит более умесным...

Преимущества QSet от QList?

Из справки по Qt.
QList класс представляет собой шаблон класса списков.
является одним из универсальных классов. Хранит список значений и обеспечивает быстрый доступ, а также быструю вставку и удаление.

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

Т.е. получается что они выполняют разные функции.
У QSet нет, как такового, доступа по индексу.
В QSet изначально нельзя добавить два одинаковых элемента. Если insert'том добавлять элемент который уже есть то он его не добавит и вернет итератор указывающий элемент, который уже есть в QSet ( фактически это и будет индекс элемента).


Если надо хранить набор значений то QSet. Если надо классический список то QList. Я не знаю вашей задачи и отвечаю согласно вопросу и тому как я этот вопрос понял.

Как я понял QSet менее трудоемкий класс и более производителней

Не совсем... Он просто другой. А трудоемкость и производительность зависит от того что от него требовать. Если пытаться сделать что то типа QList::at( int index) то QSet окажется медленнее, если точнее то там такого просто нет и надо велосипед изобретать. А если тебе надо что то найти в своей кучке то тогда QSet быстрее.

Оператор [] "достаточно быстр" и экономить на нем по-моему неразумно. Вызов contains должен быть быстрее insert (добавление в контейнер всегда тяжелее). Обойтись без contains - я бы не рисковал, судя по исходникам нельзя сказать что QSet::insert "ничего не делает если такой элемент уже есть".

Полностью согласен что к задаче надо подходить конкретно в зависимости от нужд/контекста.

QList - никакой не "список", это просто массив указателей. Так что искать в нем придется прямым перебором. "Быстрая вставка и удаление" - здесь имеется ввиду 2 вещи:

- быстрое добавление в начало/конец (там зарезервированы места)

- при вставке в середину указатель на новый элемент вставляется в массив указателей. Это гораздо дешевле чем вставка напр. для std::vector - но все-таки такая операция может двигать в памяти много данных и вызывать перераспределения памяти. Поэтому надо использовать возможность избежать удаления/вставки (как в этом примере).

Если получится что список большой а повторяющихся элементов очень мало то на контайнс сьэкономить можно существенно. Но это уже решать тому, кто знает что это за список и зачем он ему, что я не один раз повторил. Про [] в целом согласен.

Массив указателей с методами это и есть список.
Согласен.

Я использую QList для хранения номеров колонок, которые нужно будет выделить и часто пользуюсь [] -- ? значит лучше не использовать QSet

Сколько их, если по максимуму оценивать? Учитывая что вы в соседней теме спрашиваете что то про QTableWidget, думаю не много. Я бы вообще сделал массив для этого и не трогал списки/ кучи/ хеш таблицы. Но это личное дело каждого.

QList использую потому, что знаю потом его размер и его можна пушать
Изначально я не знаю размер списка, а под масив сразу нужно выделить память

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

Как на ходу перераспределить память и узнать размер динамического массива?

Что делать и нужно ли это зависит от задачи :) Примеры:

- в таблице до 1К (1К = 1000) строк. Разумеется QList и можно удалять повторы прямым перебором
- в таблице до 100К строк. QList но прямой перебор уже нехорошо. Нормально использовать QSet
- в таблице 1000-2000К строк (1-2 миллиона). QList но вместо QSet лучше переписать удаление на "С"
- в таблице 100 миллионов (и более) строк. Нужно отказаться от стандартных контейнеров и писать свои   

а при таком раскладе само добавление/удаление строк в таблице и скроллинг таблицы "адекватно" работать будет?
Я говорю именно про визуальную часть. Я  не проверял, но вот так сразу совать миллион строк в таблицу... я бы задумался.
Может кто-нибудь проверял уже? Мне, если честно, лень...