Russian Qt Forum

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Та ну... 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;
}
 

clang на моём пк:

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

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

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

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

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

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

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

Этв реализация никакого отношения к 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;
	}
}
 

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

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

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

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

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

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

Ну как сказать, если удаляется 1/1000, то простецкое удаление find/erase окажется намного быстрее. Но обычно в подобных задачах важнее другое - а стоит ли вообще заводить ассоциативный контейнер который выжрет немало памяти? Напр если только в целях "быстрого вычитания", то может и нет

Что в своем примере Вы делаете первым в главном цикле? Находите вычитаемый эл-т с которым надо сравнивать (кстати в общем случае lower_bound). Для массивов все то же самое, только вместо erase - сдвиг (поэлементный)