CODEWITHSUNDEEP
c++sortinginsertmergestl-algorithm
Jonathan Mee
Jonathan Mee

Reputation: 38939

Is There an Alternative to insert and then sort

If I have vector<int> foo and vector<int> bar both of which are sorted, and I want to merge them into foo such that the final result is sorted, does the standard provide me a method for doing this?

Obviously I can do:

foo.insert(foo.end(), bar.begin(), bar.end());
sort(foo.begin(), foo.end());

But I was hoping there was a one step algorithm to accomplish this.

Upvotes: 4

Views: 1582

Answers (4)

Jonathan Mee
Jonathan Mee

Reputation: 38939

So after looking through all the standard algorithms I can confirm that, there is no alternative to insert and sort. As I was searching the standard algorithms I did note that all the copying algorithms use input iterators and output iterators the only time an input-output iterators are used is when a single range is being operated on. (For example sort uses input-output iterators but any copy uses input iterators and an output iterator.)

I'd like to give an illustration of my point. So lets make an example of what an insertion merge algorithm with an input-output iterator would look like:

template <class BidirectionalIterator, class InputIterator>
void func(BidirectionalIterator first1, BidirectionalIterator last1, InputIterator first2, InputIterator last2){
    bool is1Empty = first1 == last1;
    bool is2Empty = first2 == last2;
    BidirectionalIterator end = next(last1, distance(first2, last2));

    if (!is1Empty){
        --last1;
    }

    if (!is2Empty){
        --last2;
    }

    while (!is1Empty || !is2Empty){
        --end;
        if (!is1Empty){
            if (!is2Empty && *last2 > *last1){
                *end = *last2;

                if (last2 == first2){
                    is2Empty = true;
                }else{
                    --last2;
                }
            }else{
                *end = *last1;

                if (last1 == first1){
                    is1Empty = true;
                }
                else{
                    --last1;
                }
            }
        }else{
            *end = *last2;

            if (last2 == first2){
                is2Empty = true;
            }
            else{
                --last2;
            }
        }
    }
}

Two things should be noted about this func algorithm:

  1. It doesn't respect last1 it is assumed that sufficient space is allocated beyond last1 to also contain all the elements in the input range
  2. func's input-output range cannot be called with a back_inserter like any other output only range in a standard algorithm

Because of this even func cannot be a "one step algorithm". It must be called like this:

 foo.resize(foo.size() + bar.size());
 func(foo.begin(), next(foo.begin(), foo.size() - bar.size()), bar.begin(), bar.end());

Note that Blastfurnace's answer takes advantage of the knowledge that it is merging two sorted ranges, and as such is of equivalent speed to func:

auto middle = foo.insert(foo.end(), bar.begin(), bar.end());
inplace_merge(foo.begin(), middle, foo.end());

The only actual "one step algorithm" is to roll this Blastfurnace's answer into a function that you could call by passing in the containers to be merged.

Upvotes: 0

Mateusz Grzejek
Mateusz Grzejek

Reputation: 12068

If you need this kind of merge, why not make one yourself?

template <class Vector>
void insert_sorted(Vector& where, Vector& what)
{
    typename Container::iterator src = what.begin();
    typename Container::iterator src_end = what.end();

    size_t index = 0;

    while(src != src_end)
    {
        if(*src < where[index])
        {
            where.insert(where.begin() + index, *src);
            ++src;
        }

        ++index;
    }
}

Sample usage:

vector<int> foo{ 0, 5, 7, 9, 11, 14 };
vector<int> bar{ 1, 2, 4, 8, 10, 12 };

insert_sorted(foo, bar);

for(vector<int>::iterator i = foo.begin(); i != foo.end(); ++i)
    cout << *i << " ";

Output:

0 1 2 4 5 7 8 9 10 11 12 14

Live sample: link.

Upvotes: 1

Blastfurnace
Blastfurnace

Reputation: 18652

It might be faster to use std::inplace_merge instead of std::sort. If there is additional memory available it has linear complexity otherwise it falls back to NlogN.

auto middle = foo.insert(foo.end(), bar.begin(), bar.end());
std::inplace_merge(foo.begin(), middle, foo.end());

Upvotes: 6

TobiMcNamobi
TobiMcNamobi

Reputation: 4813

To elaborate on Mat's comment your code could look like this using std::merge:

std::vector<int> result;
std::merge(
    foo.begin(), foo.end(),
    bar.begin(), bar.end(),
    std::back_inserter(result));

foo = result; // if desired

Upvotes: 6

Related Questions