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

Question

У нас есть набор S {1,10,100,1000,10000}.Теперь мы вводим целое число x (скажем, x = 4).

Теперь мы должны добавить каждый элемент продукта набора с x к самому набору.Итак, наконец

S={1,10,100,1000,10000,4,40,400,4000,40000}

[S изначально не ограничивается только 5 записями]

Нам нужно посетить только начальные элементы в наборе.Я попробовал подход, подобный следующему:

for(auto i=s.begin();i!=s.end();i++)
{
    s.insert((*i)*x);
}

Это не дает желаемого результата, поскольку размер набора продолжает увеличиваться.

Еще один подход, который я пробовал, состоял в том, чтобы сохранить все кратные (*i)*x вдругой временный набор / вектор и объединить его с s позже.Но поскольку исходный набор данных огромен, он ухудшает сложность времени.Какие-нибудь оптимизации?

Answer 1

Так как std::set упорядочен, и итераторы не аннулируются при вставке, вы можете просто вставить во время итерации, пока вы не вставите в диапазон, который еще остается для итерации.

Если мы можем предположить, что все числа положительны, то мы можем выполнить итерацию в обратном направлении, потому что результат умножения всегда будет больше, чем входные данные:

for (auto it = S.rbegin(); it != S.rend(); ++it)
    S.insert(*it*x);

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

---

Но так как исходный набор данных огромен, это ухудшает сложность времени.

Вставка Nэлементов в std::set - это O (N log N).Слияние std::set s - это O (N log N).Подход слияния не ухудшает асимптотическую сложность времени.

Если бы вы использовали std::unordered_set, то подход слияния был бы O (N) в среднем случае.Однако в худшем случае это все равно O (N log N).Я рекомендую использовать подход слияния с неупорядоченным набором.

Answer 2

Вот, пожалуйста.

#include <iostream>
#include <set>
#include <iterator>

std::set<int> & update( std::set<int> &s, int value )
{
    for ( auto it = rbegin( s ); it != rend( s ); ++it )
    {
        s.insert( *it * value );
    }

    return s;
}

int main() 
{
    std::set<int> s = { 1, 10, 100, 1000, 10000 };

    for ( const auto &value : s )
    {
        std::cout << value << ' ';
    }
    std::cout << '\n';

    for ( const auto &value : update( s, 4 ) )
    {
        std::cout << value << ' ';
    }
    std::cout << '\n';

    return 0;
}

Вывод программы

1 10 100 1000 10000 
1 4 10 40 100 400 1000 4000 10000 40000 

Согласно стандарту C ++ 20 (22.2.6 Ассоциативные контейнеры)

9 Вставка и размещение членов не должны влиять на действительность итераторы и ссылки на контейнер, а члены стирания должны сделать недействительными только итераторы и ссылки на стертые элементы.

Или более общий подход

#include <iostream>
#include <set>
#include <iterator>

std::set<int> & update( std::set<int> &s, int value )
{
    auto partition = s.lower_bound( 0 );

    for ( auto it = rbegin( s ); it != std::set<int>::reverse_iterator( partition ); ++it )
    {
        s.insert( *it * value );
    }

    for ( auto it  = begin( s ); it != partition; ++it )
    {
        s.insert( *it * value );
    }


    return s;
}

int main() 
{
    std::set<int> s = { -10000, -1000, -100, -10, -1, 1, 10, 100, 1000, 10000 };

    for ( const auto &value : s )
    {
        std::cout << value << ' ';
    }
    std::cout << '\n';

    for ( const auto &value : update( s, 4 ) )
    {
        std::cout << value << ' ';
    }
    std::cout << '\n';

    return 0;
}

Вывод программы

-10000 -1000 -100 -10 -1 1 10 100 1000 10000 
-40000 -10000 -4000 -1000 -400 -100 -40 -10 -4 -1 1 4 10 40 100 400 1000 4000 10000 40000 

Answer 3

Как уже упоминалось в комментариях, проще всего использовать временный набор.В C ++ 17 вы можете использовать std::set::merge с временным набором, приведенным к rvalue:

#include <algorithm>

std::set<int> s2;

std::transform(s1.cbegin(), s1.cend(), std::inserter(s2, s2.end()),
      [](int orig){ return 4*orig; });

s1.merge(std::move(s2));

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

for (auto it = s1.begin(); it != s1.end(); ++it)
   it = s.insert(*it*4).first;

Для меньшего количества ограничений вы можете использовать этот более подробный цикл:

for (std::set<int>::iterator it1 = s.begin(), it2; it1 != s.end();
        it1 = std::next(it1) == it2 ? std::next(it1, 2) : it2)
   it2 = s.insert(*it1*4).first;