Как выполнить быстрый слияние списка C++ с самим собой

Допустим, у меня есть список, содержащий некоторые целые числа, мне нужно быстро слить его с собой: например, у меня есть {1, 2, 3} после этой процедуры, я хочу, чтобы список быть {1, 2, 3, 1, 2, 3} Эти версии сделать это, но слишком медленно, когда размер списка достаточно велик (10^6)Как выполнить быстрый слияние списка C++ с самим собой

list<int> l; //l got some integers here   
    list<int> l_copy = l; 

    while (l_copy.size() > 0) 
    { 
     l.push_back(l_copy.front()); 
     l_copy.pop_front(); 
    } 

    //another version but still slow i think 
    size_t size = l.size(); 
    for (list<int>::iterator it = l.begin(); size--; ++it) 
    { 
     l.push_back(*it); 
    }

есть ли какие-либо альтернативы для этого, но значительно быстрее ? благодаря

источник

2015-04-01 ampawd

Как насчет того, чтобы сделать копию списка, а затем соединить копию с оригиналом? – rcgldr

Списки включают в себя динамическое распределение памяти на узел, поэтому их расширение никогда не будет быстрым. Возможно, вы захотите рассмотреть, например, 'deque' соответствует вашим потребностям - по крайней мере, он группирует элементы в меньшее количество смежных распределений. В качестве альтернативы, для некоторых целей вы можете использовать пользовательский распределитель, который дважды посещает элементы. –

Возможно, это не имеет значения, но какова цель удвоения? Вы можете создать контейнер/итератор, который * действует *, как список, удвоенный. – Persixty

Вы можете использовать std::list::splice для этого:

list<int> l; 
list<int> l_copy = l;  
l.splice (l.end(), l_copy);

Эта версия splice гарантированно работает в постоянном времени стандартом (§23.3.5.5/6 в n4296). Он работает, просто указывая конец первого списка в начале другого списка. Существует еще одна версия сращивания, которая использует диапазоны итераторов, которые являются O (n), но здесь это не нужно. Очевидно, что копия все равно займет время для большого списка, но это неизбежно.

источник

2015-04-01 08:29:52 TartanLlama

Хмм спасибо, хорошая идея, но почему сплайсинг работает в постоянное время? Как я вижу из его исходного кода, он использует итерации от первого до последнего итератора, поэтому зависит от размера списка, сколько итераций будет – ampawd

Отредактировано с дополнительной информацией – TartanLlama

Как выполнить быстрый слияние списка C++ с самим собой

ответ

Смежные вопросы