the numbers appearing closest to integer x in the vector v1 must be printed first

Question

Below there is a tabular view of a sorted vector.

vector v1= {1 , 8 ,10 ,16}

int x=9;

You are given a task to reorder vector v1 by following a rule. You will be given a integer x.

The rule is:

You will print all the elements of the vector, such that, the numbers appearing closest to x in the vector v1 must be printed first.

For example the reordered vector must be 8,10,16,1.

sample examples:

x=15 . . .v1={-100,1,12,15,100} . . . output:{15,12,1,100,-100}

x=99 . . .v1={-100,1,12,15,100} . . . output:{100,15,12,1,-100}

x=-1 . . .v1={-100,1,12,15,100} . . . output:{1,12,15,-100,100}

In case there are two numbers that are equally closer to x, in that case, print smaller element first

for example:

x=0 . . .v1={-100,-50,50,100} . . . output:{**-50**,50,**-100**,100}

I used a naive approach, but it is too slow for larger ranges.

while(0 < v1.size()) {
    for (int j = 0; j <= v1.back(); j++) {
        if (x - j >= 0 && find(all(v1), x - j) != v1.end()) {
            b = x - j; break;
        }
        if (x + j <= v1.back() && find(all(v1), x + j) != v1.end()) {
            b = x + j; break;
        }
    }
    cout<<b;
    auto it2 = find(all(v1), b);
    v1.erase(it2);
}

Please, if you can, suggest me a faster code.

My code is way too slow.

Answer 1

Well, you need an appropriate comparator, then you can simply use std::sort:

std::vector<int> numbers;
int referenceValue; // = ...
std::sort
(
    numbers.begin, numbers.end,
    [/* ... */](int x, int y) { /* ... */ }
);

You'll get the vector sorted into exactly the order you need, no need to find and remove elements from, you can just iterate over it afterwards. std::sort guarantees O(n(log(n)) (since C++11), so that should be fast enough (faster you cannot get on sorting anyway...).

Question now is: how would such a comparator look like?

Well, at very first, it will need to have the reference value available, so it will capture it:

[referenceValue](int x, int y) { /* ... */ }

As it's a simple int, capturing by value is fine, more complex types you might prefer to capture by reference instead.

The comparator should implement 'less' semantics, so it should return true if x goes before y. So we can have:

int dx = std::abs(x - referenceValue);
int dy = std::abs(y - referenceValue);
return                        dx < dy        || dx == dy && x < y;
// if x has smaller distance: ^^^^^^^
// or, in case of equality, the smaller one  ^^^^^^^^^^^^^^^^^^^^

That's it, you're done...

Untested code, if you happen to find a bug, please fix it yourself ;)

Answer 2

Elaborating on what Aconcagua suggested:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

struct sortClosestToFunctor {

  explicit sortClosestToFunctor(int x) : m_x{x} {}

  bool operator()(int const lhs, int const rhs) const {
    int dx = std::abs(lhs - m_x);
    int dy = std::abs(rhs - m_x);
    return (dx < dy) or (dx == dy and lhs < rhs);
  }

private:
  int m_x;
};

int main() {
    std::vector<int> v1{1, 8, 10, 16};
    int x = 9;

    // using functor
    std::sort(v1.begin(), v1.end(), sortClosestToFunctor(9));

    // using lambda
    std::sort(v1.begin(), v1.end(), [x](int const lhs, int const rhs) {
        int dx = std::abs(lhs - m_x);
        int dy = std::abs(rhs - m_x);
        return (dx < dy) or (dx == dy and lhs < rhs);
    });

    // 8 10 16 1
    std::copy(v1.begin(), v1.end(), std::ostream_iterator<int>(std::cout, " "));
}

Answer 3

My five cents. A straightforward approach without sorting a vector.

I am sure that it is a bad idea to sort the vector if the only task is to output it in some order. Otherwise the original vector will be changed (Why?! This is not required in the assignment.) or a copy of the vector will be created.

#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

std::ostream & closest_output( const std::vector<int> &v, 
                               const int &value, 
                               std::ostream &os = std::cout )
{
    auto it = std::lower_bound( std::begin( v ), std::end( v ), value );

    if ( it == std::begin( v ) )
    {
        for ( auto last = std::end( v ); it != last; ++it )
        {
            os << *it << ' ';
        }
    }
    else if ( it == std::end( v ) )
    {
        for ( auto first = std::begin( v ); it != first; )
        {
            os << *--it << ' '; 
        }
    }
    else
    {
        auto next = it, first = std::begin( v ), last = std::end( v );

        while ( it != first && next != last )
        {
            if ( *next - value < value - *std::prev( it ) )
            {
                os << *next++ << ' ';
            }
            else
            {
                os << *--it << ' ';
            }
        }

        while ( it != first ) os << *--it << ' ';
        while ( next != last ) os << *next++ << ' ';
    }

    return os;
}

int main() 
{
    std::vector<int> v1 = { 1 , 8 ,10 ,16 };

    int value = 9;

    closest_output( v1, value  ) << '\n';

    std::vector<int> v2 = { -100, 1, 12, 15, 100 };

    value = 15;

    closest_output( v2, value  ) << '\n';

    value = 99;

    closest_output( v2, value  ) << '\n';

    value = 1;

    closest_output( v2, value  ) << '\n';

    return 0;
}

The program output is

8 10 16 1 
15 12 1 100 -100 
100 15 12 1 -100 
1 12 15 100 -100 

Answer 4

Let's consider if x = 9 and vector = {1, 8, 10, 16},
Then upper bound of x in vector is 10,

Now if you traversal toward begin or toward end of the vector from upper bound the distance will increase with respect to x in both direction, because vector is sorted.

Following two step will produce required output,

1. Find distance between x and left element, and between right element and x then if left distance is less then or equal to right distance then print left element otherwise print right element,
2. If left element is printed then move one element previous to left element and if right element is printed then move next element from right element.
   

Now let`s apply these steps,
Here x = 9, vector = {1, 8, 10, 16} and upper bound = 10

1. left element = 8, right element = 10
   (9 - 8) <= (10 - 9) is true, so print 8, and now left element = 1
2. left element = 1, right element = 10
   (9 - 1) <= (10 - 9) is false, so print 10, and now right element = 16
3. left element = 1, right element = 16
   (9 - 1) <= (16 - 9) is false, so print 16, and now right element = end of vector
4. left element = 1, right element = end of vector
   so print 1

These steps will produce expected output : {8, 10, 16, 1}
Try this implementation,

#include <iostream>

#include <vector>
#include <algorithm>

using std::cout;

template <typename ForwardIterator>
void print(ForwardIterator first, ForwardIterator last){
    for(; last != first; ++first)
        cout<< *first<< " ";
}

void printClostestFirst(const std::vector<int>& vec, const int piotValue){
    std::vector<int>::const_iterator mid = std::upper_bound(vec.cbegin(), vec.cend(), piotValue);

    if(vec.cend() == mid){
        print(vec.crbegin(), vec.crend());
        return;
    }
    else if(vec.begin() == mid){
        print(vec.cbegin(), vec.cend());
        return;
    }

    std::vector<int>::const_reverse_iterator left = vec.crbegin() + std::distance(mid, vec.cend());
    std::vector<int>::const_iterator right = mid;

    std::vector<int>::const_reverse_iterator leftEnd = vec.crend();
    std::vector<int>::const_iterator rightEnd = vec.cend();

    int leftDist = 0;
    int rightDist = 0;

    while(leftEnd != left && rightEnd != right){
        leftDist = piotValue - *left;
        rightDist = *right - piotValue;

        if(leftDist <= rightDist){
            cout<< *left<< " ";
            ++left;
        }
        else{
            cout<< *right<< " ";
            ++right;
        }
    }

    if(leftEnd != left)
        print(left, leftEnd);
    else
        print(right, rightEnd);
}

int main(int , char *[]){
    cout<< "x =  9 . . .vec = { 1, 8, 10, 16 }     . . .  output: { ";
    printClostestFirst({1, 8, 10, 16}, 9);
    cout<< "}\n";

    cout<< "x = 15 . . .vec = { -100,1,12,15,100 } . . .  output: { ";
    printClostestFirst({-100,1,12,15,100}, 15);
    cout<< "}\n";

    cout<< "x = 99 . . .vec = { -100,1,12,15,100 } . . .  output: { ";
    printClostestFirst({-100,1,12,15,100}, 99);
    cout<< "}\n";

    cout<< "x = -1 . . .vec = { -100,1,12,15,100 } . . .  output: { ";
    printClostestFirst({-100,1,12,15,100}, -1);
    cout<< "}\n";

    cout<< "x =  0 . . .vec = { -100,1,12,15,100 } . . .  output: { ";
    printClostestFirst({-100,-50,50,100}, 0);
    cout<< "}\n";
}

output:

x =  9 . . .vec = { 1, 8, 10, 16 }     . . .  output: { 8 10 16 1 }
x = 15 . . .vec = { -100,1,12,15,100 } . . .  output: { 15 12 1 100 -100 }
x = 99 . . .vec = { -100,1,12,15,100 } . . .  output: { 100 15 12 1 -100 }
x = -1 . . .vec = { -100,1,12,15,100 } . . .  output: { 1 12 15 -100 100 }
x =  0 . . .vec = { -100,1,12,15,100 } . . .  output: { -50 50 -100 100 }