QList<t> удаление одинаковых элементов QList / QSet

[daimon]

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

[Павел_F.]

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

[Igors]

Код:

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());
}

[Павел_F.]

Вот и пример второго варианта ( не совсем, конечно, но суть таже). Но итератором бегать будет существенно быстрее чем в цикле брать элемент по номеру. Я бы использовал именно его. Да и в случае использования 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.
Значит в место:

Код:

if (qs.contains(val)) continue;
    qs.insert(val);

Можно написать:

Код:

if( qs.insert(val) != qs.end()) continue;

Что уберет весьма затратную contains.
Хотя все вопросы о скорости зависят от нужд и "структуры" содержимого списка.

[daimon]

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

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

[Павел_F.]

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

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

[daimon]

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

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

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

[Павел_F.]

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

Из справки по Qt.

Detailed Description
The QList class is a template class that provides lists.
QList<T> is one of Qt's generic container classes. It stores a list of values and provides fast index-based access as well as fast insertions and removals.

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

The QSet class is a template class that provides a hash-table-based set.

QSet<T> is one of Qt's generic container classes. It stores values in an unspecified order and provides very fast lookup of the values. Internally, QSet<T> is implemented as a QHash.

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

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


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

[daimon]

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

Из справки по Qt.

Detailed Description
The QList class is a template class that provides lists.
QList<T> is one of Qt's generic container classes. It stores a list of values and provides fast index-based access as well as fast insertions and removals.

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

The QSet class is a template class that provides a hash-table-based set.

QSet<T> is one of Qt's generic container classes. It stores values in an unspecified order and provides very fast lookup of the values. Internally, QSet<T> is implemented as a QHash.

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

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


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

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

[Павел_F.]

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

[Igors]

Вот и пример второго варианта ( не совсем, конечно, но суть таже). Но итератором бегать будет существенно быстрее чем в цикле брать элемент по номеру.
....
Можно написать:

Код:

if( qs.insert(val) != qs.end()) continue;

Что уберет весьма затратную contains.

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

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

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

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

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

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

[Павел_F.]

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

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

QList - никакой не "список", это просто массив указателей.

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

Спи́сок — конечное, возможно пустое множество данных (элементов) различной природы, имеющее определённый смысл для решаемой задачи. В качестве элементов множества (списка) могут выступать любые другие элементы данных, в том числе и сами списки.

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

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

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

Согласен.

[daimon]

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

[Павел_F.]

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

[daimon]

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

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