Множества (std::set, QSet)

[__Heaven__]

Привет друзья!
Прошу помочь найти решение, ибо не хотелось бы велосипедить.
Я выделяю для себя положительные стороны контейнеров:
std::set - возможность конструирования по месту с подсказкой (emplace_hint, почему этого нет в 5,7+ реализациях QSet, ведь, объявляли о переходе на c++11??)
QSet - наличие простых методов и операторов для вычисления пересечений, сложений и вычитаний.

Используя std::set я не имею возможности выполнить вычитание без создания контейнера для результата. Я говорю про std::set_difference.
Меня же интересует аналог QSet<T> &QSet::operator-=(const T &value). Не хотелось бы выделять дополнительной памяти. Быть может есть какой-нибудь обобщенный erase_iterator? Так можно было бы освобождать память из-под обработанных элементов.

[Igors]

Это принципиально разные ассоциативные контейнеры, и выбор определяется соображением "нужна ли упорядоченность". Напр если данные нужно рисовать по точкам, одна за другой, то QSet (на базе QHash) просто не годится.

Если такой необходимости нет, то выбор обычно в пользу более быстрого QSet. Правда если хеш-ключ получается слишком замороченный, то ну его нафиг, лучше set.

И третье: в любом случае ключ - сами данные, т.е. менять их будет нельзя, в этом нужно сразу точно убедиться

Меня же интересует аналог QSet<T> &QSet::operator-=(const T &value). Не хотелось бы выделять дополнительной памяти. Быть может есть какой-нибудь обобщенный erase_iterator? Так можно было бы освобождать память из-под обработанных элементов.

Была подобная задача с интенсивным вычитанием. Как ни странно, оптимально получается.. на векторах (т.е. вообще без ассоциативных контейнеров). Ну а если выжимать не надо, то делов 5 минут - проходитесь итераторм по первому делая erase для тех что есть во втором (ах это уже велосипед ). Оптимизировать память - см squeeze()

[__Heaven__]

Да, нужна упорядоченность и меньшее потребление памяти.
Ключ менять нет необходимости.
На векторах делать точно не хочу. Имеется много операций вставки и удаления.

[Igors]

Да, нужна упорядоченность и меньшее потребление памяти.
Ключ менять нет необходимости.

Ну тогда QSet пролетает. Когда-то (давно) мерял, помещение в std::set обходится примерно +20 байт на элемент (в 64бит может больше)

На векторах делать точно не хочу. Имеется много операций вставки и удаления.

Всем известно что вставка/удаление в set/map намного (или несравненно) быстрее чем вставка в вектор (там же массу данных надо сдвигать). Однако для "множественных" операций это может оказаться не так. Напр надо вставить тысячу вертексов. Для set это будет тысяча операций, время просто умножится на тысячу. А вот для вектора это можно сделать одной операцией. Поэтому начиная с какой-то интенсивности вектор догонит, а затем и перегонит set. Это заманчиво если финальные данные нужны как вектор. Правда нужна такая задача 

[__Heaven__]

Как производился замер потребления? Очень странно, ведь QSet хранит и хэшданные.
В std::set можно и кусками вставлять через insert(container.cbegin(), container.cend()). Также есть замечательная emplace_hint, которая позволит сэкономить на поиске места вставки.

[kambala]

может линейный список подойдет?

[Igors]

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

Я мерял std::set, просто шагал в отладчике пока не дотопал до new а там посмотрел.

В std::set можно и кусками вставлять через insert(container.cbegin(), container.cend()).

Это не делает вставки быстрее

Расскажите чего хотите добиться, тогда может и "матчасть" присмотрим подходящую

[__Heaven__]

Кажется линейный список не подходит. Недопустимы дубликаты и предпочтительно упорядочивание.

В std::set можно и кусками вставлять через insert(container.cbegin(), container.cend()).

Это не делает вставки быстрее

Та ну... https://ideone.com/tGvhpt

Код

C++ (Qt)
#include <set>
#include <chrono>
#include <iostream>
 
using Time = std::chrono::high_resolution_clock;
using ms = std::chrono::milliseconds;
 
int main()
{
    std::set<int> initialSet;
    for (int i = 0; i < 5000000; ++i) {
        initialSet.insert(i);
    }
 
    std::set<int> setFilledWithForInsert;
    {
        const auto start = Time::now();
        for (const int value: initialSet) {
            setFilledWithForInsert.insert(value);
        }
        std::cout << "Insert: " << std::chrono::duration_cast<ms>(Time::now() - start).count() << "\n";
    }
 
    std::set<int> setFilledWithForEmplaceHint;
    {
        const auto start = Time::now();
        auto it = setFilledWithForEmplaceHint.cend();
        for (const int value: initialSet) {
            it = setFilledWithForEmplaceHint.emplace_hint(it, value);
        }
        std::cout << "EmplaceHint: " << std::chrono::duration_cast<ms>(Time::now() - start).count() << "\n";
    }
 
    std::set<int> setFilledWithForInsertHint;
    {
        const auto start = std::chrono::system_clock::now();
        auto it = setFilledWithForEmplaceHint.cend();
        for (const int value: initialSet) {
            it = setFilledWithForInsertHint.insert(it, value);
        }
        std::cout << "InsertHint: " << std::chrono::duration_cast<ms>(Time::now() - start).count() << "\n";
    }
 
    std::set<int> setFilledWithIterators;
    {
        const auto start = std::chrono::system_clock::now();
        setFilledWithIterators.insert(initialSet.cbegin(), initialSet.cend());
        std::cout << "InsertIterators: " <<  std::chrono::duration_cast<ms>(Time::now() - start).count() << "\n";
    }
 
    return 0;
}
 

Insert: 1065
EmplaceHint: 256
InsertHint: 281
InsertIterators: 273

clang на моём пк:

Insert: 3820
EmplaceHint: 684
InsertHint: 659
InsertIterators: 615

Расскажите чего хотите добиться, тогда может и "матчасть" присмотрим подходящую

Ушли от темы к замерам... Добиться хочу отсечения из текущего std::set другого std::set без дополнительного выделения памяти.
Нужен невелосипедный аналог  QSet::operator-=.

[Igors]

Добиться хочу отсечения из текущего std::set другого std::set без дополнительного выделения памяти.
Нужен невелосипедный аналог  QSet::operator-=.

Такое отсечение (ис каропки или нет) скорее всего не вернет распределенную память (как это водится в std). А фокус со swap (как для вектора) здесь вряд ли прокатит. Лучше это сразу проверить.

Доп выделение неизбежно так или иначе почти для всех контейнеров. Надо выделить память для новых данных, переписать и удалить оригинал. Поэтому не видно смысла упорно искать фирменный оператор -=, он делает то же самое  

Код

C++ (Qt)
    std::set<int> initialSet;
    for (int i = 0; i < 5000000; ++i) {
        initialSet.insert(i);
    }
 

Вставки "по порядку/нарастающей" могут быть заметно быстрее других.

[__Heaven__]

Написал функцию без потребления доп памяти.
Хотел найти подобную реализацию от профессионалов.

Код

C++ (Qt)
template <typename T>
std::set<T> &subtract (std::set<T> &initSet, const std::set<T> &otherSet) {
    auto it = initSet.cbegin();
    auto end = initSet.cend();
    auto otherIt = otherSet.cbegin();
    auto otherEnd = otherSet.cend();
 
    while (it != end) {
        const auto &value = *it;
        while (otherIt != otherEnd) {
            if (*otherIt >= value) {
                break;
            }
            ++otherIt;
        }
 
        if (otherIt == otherEnd) {
            break;
        }
 
        if (*otherIt == value) {
            it = initSet.erase(it);
        }
        else {
            ++it;
        }
    }
    return initSet;
}

[__Heaven__]

https://ideone.com/emlYr7

Код

C++ (Qt)
#include <algorithm>
#include <chrono>
#include <iostream>
#include <set>
 
using Time = std::chrono::high_resolution_clock;
using ms = std::chrono::milliseconds;
 
template <typename T>
std::set<T> &subtract (std::set<T> &initSet, const std::set<T> &otherSet) {
    auto it = initSet.cbegin();
    auto end = initSet.cend();
    auto otherIt = otherSet.cbegin();
    auto otherEnd = otherSet.cend();
 
    while (it != end) {
        const auto &value = *it;
        while (otherIt != otherEnd) {
            if (*otherIt >= value) {
                break;
            }
            ++otherIt;
        }
 
        if (otherIt == otherEnd) {
            break;
        }
 
        if (*otherIt == value) {
            it = initSet.erase(it);
        }
        else {
            ++it;
        }
    }
    return initSet;
}
 
int main()
{
    std::set<int> initialSet;
    auto it = initialSet.end();
    for (int i = 0; i < 5000000; ++i) {
        it = initialSet.emplace_hint(it, i);
    }
 
    std::set<int> diffSet;
    it = diffSet.end();
    for (int i = 0; i < 5000000; i += 2) {
        it = diffSet.emplace_hint(it, i);
    }
 
    auto start = Time::now();
 
    std::set<int> setSubtractedWithStl;
    {
        std::set<int> initialSetCopy = initialSet;
 
        start = Time::now();
        std::set_difference(initialSetCopy.cbegin(), initialSetCopy.cend(),
                            diffSet.cbegin(), diffSet.cend(),
                            std::inserter(setSubtractedWithStl, setSubtractedWithStl.end()));
    }
    std::cout << "Stl + destructor: " << std::chrono::duration_cast<ms>(Time::now() - start).count() << '\n';
 
    start = Time::now();
    subtract(initialSet, diffSet);
    std::cout << "Heaven: " << std::chrono::duration_cast<ms>(Time::now() - start).count() << '\n';
 
    const bool hasEqualSize = initialSet.size() == setSubtractedWithStl.size();
    bool equal = false;
    if (hasEqualSize) {
        equal = std::equal(initialSet.cbegin(), initialSet.cend(),
                           setSubtractedWithStl.cbegin());
    }
 
    std::cout << "Sets are equal: " << std::boolalpha << equal << '\n';
 
    return 0;
}

Stl + destructor: 917
Heaven: 183
Sets are equal: true

[Igors]

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

Код

C++ (Qt)
template <class T>
void subtract( std::set<T> & set1, const std::set<T> & set2 )
{
	typedef typename std::set<T>::iterator TIter;
	TIter it2 = set2.begin();
 
	while (it2 != set2.end()) {
		TIter it1 = set1.find(*it2);
		if (it1 != set1.end())
			set1.erase(it1);
		++it2;
	}
}
 

[__Heaven__]

Этв реализация никакого отношения к std::set не имеет

Да имеет она всё.
Я бы посмотрел, как вы применяете её к вектору с "чуть переделанным erase"

Сложно пишете.
Существует size_type erase( const key_type& key ).

[Igors]

Да имеет она всё.

Предположим вычитаемое (второй set) содержит всего 1 эл-т - а Вы все равно молотите весь первый set который может быть огромен. Зачем так делать если set умеет быстро искать?

Я бы посмотрел, как вы применяете её к вектору с "чуть переделанным erase"

Напишем велик для удаления эл-тов из вектора

Код

C++ (Qt)
template<class T>
void RemoveElems( std::vector<T> & vec )
{
 size_t place = 0;
 for (size_t i = 0; i < vec.size(); ++i) {
  if (IsElementDeleted(vec[i])) continue;
  if (i != place)
   vec[place] = vec[i];
  ++place; 
 }
 vec.resize(place);
}

Теперь вместо IsElementDeleted подставляете что написали выше. Если "ис каропки" - дело чести, то можно remove_if (хотя он чуть хуже). Да, это долгая операция, НО она практически не зависит от числа удаляемых эл-тов, поэтому для "массовых" удалений она может оказаться быстрее.

[__Heaven__]

Да имеет она всё.

Предположим вычитаемое (второй set) содержит всего 1 эл-т - а Вы все равно молотите весь первый set который может быть огромен. Зачем так делать если set умеет быстро искать?

В моей программе чаще встречается вычитание ~ из 10млн элементов 10тыс - 8млн элементов. Если 10 млн на 10 млн случится, то будет долго искать. Думаю, что пробег ради 1 элемента - скромная плата за скорость на больших множествах. Хотя, можно и ветвление алгоритма сделать в зависимости от отношения размеров.

Вашего примера я не понял.