CODEWITHSUNDEEP
c++vectormergestlnumeric
Aleph0
Aleph0

Reputation: 6074

Merge two sorted double vectors using different comparision function

I have two sorted std::vector<double> containers. Now I need to merge both vectors to a new sorted container, with the restriction, that two values should be considered equal if and only if std::fabs(a-b)<1.e-6 holds. This problem pops up plenty of times in our code and I'm looking for the neatest solution.

My first attempt was:

std::vector<double> mergeTimeLists(const std::vector<double>& sorted1, const std::vector<double>& sorted2) {    
    auto cmp = [&](double a, double b)->bool { return std::fabs(a - b) > 1e-6 && a < b; };
    std::set<double, decltype(cmp)> set(cmp);
    std::copy(sorted1.begin(), sorted1.end(), std::inserter(set, set.begin()));
    std::copy(sorted2.begin(), sorted2.end(), std::inserter(set, set.begin()));
    std::vector<double> ret;
    std::copy(set.begin(), set.end(), std::back_inserter(ret));
    return ret;
}

After consulting again the docs of the STL I came up with:

std::vector<double> mergeTimeLists1(const std::vector<double>& sorted1, const std::vector<double>& sorted2) {
    std::vector<double> ret;
    std::merge(sorted1.begin(), sorted1.end(), sorted2.begin(), sorted2.end(), std::back_inserter(ret));
    ret.erase(std::unique(ret.begin(), ret.end(), [&](double a, double b)->bool { return std::fabs(a - b) < 1e-6; }),ret.end());
    return ret;
}

This is my test:

int main(int argc, char** args) {
    {
        auto ret = mergeTimeLists({ 0,0.1,0.2,0.3,0.34 }, { 0.05,0.10000001 });
        std::copy(ret.begin(), ret.end(), std::ostream_iterator<double>(std::cout, " "));
    }
    std::cout << std::endl;
    {
        auto ret = mergeTimeLists1({ 0,0.1,0.2,0.3,0.34 }, { 0.05,0.10000001 });
        std::copy(ret.begin(), ret.end(), std::ostream_iterator<double>(std::cout, " "));
    }

}

Does anyone has some ideas for improvements?

Revised question

Seemingly, I was unable to state my question completely clear and unambiguous. It turned out, that what I actually wanted was something slightly different.

Assume, that I have two sorted std::vector<double> containers s1 and s2. I wanted to create a new sorted container s containing all values in s1 and some values in s2, whereas are value v from s2 is only contained in s if and only if there is no value u in s1, such that std::fabs(u-v)<1e-6.

Hence, I only want the values of s2 to be in the resulting container s, if there are not too close to some values in s1.

I'm very sorry for not stating my question so clear beforehand and I'm really delighted about the feedback I already got so far. Maybe there are still ideas I can get from here?

Upvotes: 0

Views: 111

Answers (1)

John Zwinck
John Zwinck

Reputation: 249123

The vectors are sorted. The result is to be a sorted vector as well.

Using std::merge() is a good start, but your example falls short of optimal performance in two ways:

  1. You neglect to reserve capacity in the returned vector before the merge.
  2. You insert all elements during the merge, then erase unwanted elements after it.

The first is trivially addressed:

ret.reserve(std::max(sorted1.size(), sorted2.size()));

The second can be solved by changing the output iterator given to std::merge(). Instead of std::back_inserter(ret), create your own unique_inserter(ret), like this:

struct unique_inserter
    : std::back_insert_iterator<std::vector<double>>
{
    typedef std::back_insert_iterator<std::vector<double>> base;

    unique_inserter(std::vector<double>& out) : base(out) {}

    unique_inserter& operator=(const double& value)
    {
        if (container->empty() || std::fabs(container->back() - value) > 1e-6)
            container->push_back(value);
        return *this;
    }

    // remove this if not using C++11
    unique_inserter& operator=(const double&& value)
    {
        if (container->empty() || std::fabs(container->back() - value) > 1e-6)
            container->push_back(std::move(value));
        return *this;
    }
};

This is like std::back_inserter but does nothing if a new value is equivalent to the last one. This way, unwanted values are never inserted, and do not need to be erased later.

Upvotes: 1

Related Questions