STL + Заказной комплект + без дубликатов

Question

Мне нужно иметь упорядоченный набор значений без дубликатов. Итак, что такое быстрый / лучший метод:

1 - Создать вектор, отсортировать его и удалить дубликаты? 2 - Использовать своего рода «отсортированный» вектор (если он существует)?

Какой из них может быть более эффективным?

Answer 1

Почему бы вам не использовать std::set?

Answer 2

Если вы собираетесь загрузить список один раз, затем использовать его несколько раз, тогда использование std :: vector вместо std :: set, вероятно, будет более эффективным в использовании памяти и итерации по нему.

Если вы собираетесь постоянно добавлять и удалять элементы, вам обязательно следует использовать std :: set.

Для общего назначения используйте std :: set, потому что это менее трудоемко (построение вектора требует сортировки и удаления дубликатов после того, как вы закончили добавлять все элементы), если только у вас нет особой потребности в эффективности при низком использовании памяти или какой-то другой удар по производительности, который указывает, что требуется вектор.

Answer 3

Использовать std :: set.Он упорядочен и не допускает дублирования.

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

Answer 4

Попробуйте это в вашем .h или .hpp:

struct TestWithTime
{
    TestWithTime(unsigned long long timeSecs) : m_timeSecs(timeSecs) {}

    unsigned long long m_timeSecs;
}

struct OrderedByTime
{
    bool operator() (const TestWithTime* first,  const TestWithTime* second) const
    {
        // Important: if the time is equal
        if (first->m_timeSecs == second->m_timeSecs)
        {
            // then compare the pointers
            return first < second;
        }
        return first->m_timeSecs < second->m_timeSecs;
    }
};

typedef std::set<TestWithTime*, OrderedByTime> OrderedDataByTime;

Теперь вы можете использовать свой набор OrderedDataByTime !!

Answer 5

Всегда есть Loki :: AssocVector

В противном случае вы можете легко бросить свой собственный:

• используйте std::vector или std::deque в качествебазовый контейнер
• использование lower_bound / upper_bound / equal_range и binary_search универсальных алгоритмов для поиска объекта
• также inplace_merge замечательно, когда вы уже знаете, что значениенет

Но на самом деле, используйте std::set:)

Answer 6

Эффективность будет зависеть от соотношения количества вставок / обращений, которое у вас есть (т. Е. Сколько раз вам нужно будет отсортировать ваш вектор).Если производительность действительно важна, я предлагаю вам попробовать оба подхода и использовать самый быстрый для реального случая использования приложения.

Примечание: std::set не является отсортированным вектором, поскольку он не является смежным в памяти(это дерево).Нужный вам «отсортированный вектор» - это куча свыше std::vector.Смотри: http://stdcxx.apache.org/doc/stdlibug/14-7.html.

Answer 7

Вставка в набор занимает журнал (n). И сортировка бесплатна.

Вставка в вектор (push_back) занимает постоянное время. Сортировка вектора занимает n * log (n). Но вам все равно нужно удалить дубликаты.

Если вы вставляете сразу, а затем сортируете, вы можете рассмотреть также вектор Если вы вставляете часто, установить правильный.

Answer 8

Это зависит от того, какую эффективность вы хотите.Если вы хотите что-то «просто быстрое», используйте std :: set <> (как уже предлагали другие).

Однако, если вам нужна когерентность chache или держать вещи в векторе (выравнивание памяти гарантировано), вместо этогоиз набора (ничего не гарантировано, реализованного в виде дерева, если я правильно помню), тогда вам придется напрямую использовать std :: vector в сочетании с некоторыми стандартными алгоритмами, которые предполагают, что предоставленный вами контейнер уже отсортирован (что делает проверку быстрее),как std :: binary_search () .