-
November 26th, 2023, 03:51 PM
#1
Given a list of sorted lists, return a merged sorted list
I wrote this naïve code to make a sorted lists out of three sorted lists:
Code:
import std.compat;
using intLst = std::forward_list<int>;
intLst foo(const intLst& l1, const intLst& l2)
{
intLst res;
auto l1Iter{ l1.begin() }, l2Iter{ l2.begin() };
while (l1Iter != l1.end() && l2Iter != l2.end())
if (*l1Iter <= *l2Iter)
res.push_front(*l1Iter++);
else
res.push_front(*l2Iter++);
if (l1Iter == l1.end() && l2Iter == l2.end())
return res;
if (l1Iter == l1.end())
while(l2Iter != l2.end())
res.push_front(*l2Iter++);
else
while (l1Iter != l1.end())
res.push_front(*l1Iter++);
return res;
}
int main()
{
intLst l1{1, 5, 6}, l2{4}, l3{2,3,7,8}, res;
intLst temp = foo(l1, l2);
temp.reverse();
res = foo(temp, l3);
res.reverse();
for (int e : res) std::print("{} ", e);
return 0;
}
Any comments?
-
November 27th, 2023, 12:30 AM
#2
Re: Given a list of sorted lists, return a merged sorted list
Why not use insert_after, and save a lot of reversing.
https://en.cppreference.com/w/cpp/co...t/insert_after
-
November 27th, 2023, 05:24 AM
#3
Re: Given a list of sorted lists, return a merged sorted list
Why use forward_list and not a list? Using a list makes life much easier by allowing use of std::merge. Consider:
Code:
#include <iostream>
#include <algorithm>
#include <iterator>
#include <list>
using intLst = std::list<int>;
int main() {
const intLst l1 { 1, 5, 6 }, l2 { 4 }, l3 { 2,3,7,8 };
intLst l4, res;
std::ranges::merge(l1, l2, std::back_inserter(l4));
std::ranges::merge(l4, l3, std::back_inserter(res));
std::ranges::copy(res, std::ostream_iterator<int>(std::cout, " "));
}
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
November 27th, 2023, 08:29 AM
#4
Re: Given a list of sorted lists, return a merged sorted list
Sorry, I should have said that this is an exercise and using `std::forward_list` is mandatory.
@salem
Perhaps this way:
Code:
// ...
intLst res;
auto l1Iter{ l1.begin() }, l2Iter{ l2.begin() };
auto it {res.before_begin()};
while (l1Iter != l1.end() && l2Iter != l2.end())
if (*l1Iter <= *l2Iter)
res.insert_front(it, *l1Iter++);
// ...
Not sure this has much benefits to shorten the code.
-
November 27th, 2023, 11:19 AM
#5
Re: Given a list of sorted lists, return a merged sorted list
using `std::forward_list` is mandatory
OK. Then consider:
Code:
int main() {
intLst l1 { 1, 5, 6 }, l2 { 4 }, l3 { 2,3,7,8 };
l1.merge(l2);
l1.merge(l3);
std::ranges::copy(l1, std::ostream_iterator<int>(std::cout, " "));
}
Note though, that this will empty l2 and l3 as their elements are moved and not copied to the destination list.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
November 27th, 2023, 11:49 AM
#6
Re: Given a list of sorted lists, return a merged sorted list
If you have to 'roll your own' merge, then using insert_after as suggested by salem_c above consider:
Code:
#include <forward_list>
#include <iostream>
#include <algorithm>
#include <iterator>
using intLst = std::forward_list<int>;
intLst foo(const intLst& l1, const intLst& l2) {
intLst res;
auto it { res.before_begin() };
auto l1Iter { l1.begin() };
auto l2Iter { l2.begin() };
while (l1Iter != l1.end() && l2Iter != l2.end())
it = res.insert_after(it, *l1Iter <= *l2Iter ? *l1Iter++ : *l2Iter++);
if (l1Iter != l1.end() || l2Iter != l2.end())
for (auto itr { l1Iter == l1.end() ? l2Iter : l1Iter }, itrnd { l1Iter == l1.end() ? l2.end() : l1.end() }; itr != itrnd; it = res.insert_after(it, *itr++));
return res;
}
int main() {
const intLst l1 { 1, 5, 6 }, l2 { 4 }, l3 { 2,3,7,8 };
const auto temp { foo(l1, l2) };
const auto res { foo(temp, l3) };
std::ranges::copy(res, std::ostream_iterator<int>(std::cout, " "));
}
Last edited by 2kaud; November 27th, 2023 at 12:07 PM.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
December 4th, 2023, 08:05 AM
#7
Re: Given a list of sorted lists, return a merged sorted list
agree
thanks
you help me too.
Last edited by VictorN; December 4th, 2023 at 08:20 AM.
Reason: Web link was removed.
-
December 4th, 2023, 08:23 AM
#8
Re: Given a list of sorted lists, return a merged sorted list
 Originally Posted by samstonee30
agree
thanks
you help me too.
Dear samstonee30,
if you will try to spam again then you'll be banned permanently.
Victor Nijegorodov
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|