CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 8 of 8
  1. #1
    Join Date
    Jan 2019
    Posts
    2

    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?

  2. #2
    Join Date
    Nov 2018
    Posts
    116

    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

  3. #3
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,821

    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)

  4. #4
    Join Date
    Jan 2019
    Posts
    2

    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.

  5. #5
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,821

    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)

  6. #6
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,821

    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)

  7. #7
    Join Date
    Dec 2023
    Posts
    1

    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.

  8. #8
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Hanover Germany
    Posts
    20,386

    Re: Given a list of sorted lists, return a merged sorted list

    Quote Originally Posted by samstonee30 View Post
    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
  •  





Click Here to Expand Forum to Full Width

Featured