How to erase all elements from a vector except for the largest in a specific range?

Question

Suppose I have the following vector:

The vector is a vector of pairs, and we are comparing based on the first element.

[(1,0),(0,1),(3,2),(6,3),(2,4),(4,5),(7,6),(5,7)]

I want to erase all elements in a specific range except the largest.

For example, if the range was $l = 2$ and $r = 5$, then the output:

[(1,0),(0,1),(6,3),(7,6),(5,7)]

Now if we do this again to the output array for $l = 1$, $r = 4$, then the output:

[(1,0),(7,6)]

I found this which I thought would be useful here, but I don't know how to make it work for pairs.

Here is my attempt:

int main(int argc, char const *argv[]) {
    int N;
    cin >> N;
    vector< pair<int,int> > vector_of_pairs(N);

    for (int i = 0; i < N; i++) {
        int input;
        cin >> input;
        vector_of_pairs[i] = make_pair(input, i);
    }

    int l, r;
    cin >> l >> r;

    int max_in_range = vector_of_pairs[l].first;

    for (int i = l+1; i <= r; i++) {
        if (vector_of_pairs[i].first > max_in_range) {
            max_in_range = vector_of_pairs[i].first;
        }
    }

    for (int i = l; i <= r; i++) {
        if (vector_of_pairs[i].first != max_in_range) {
            vector_of_pairs.erase(vector_of_pairs.begin() + i);
        }
    }

    printf("[");
    for(int i = 0; i < vector_of_pairs.size(); i++) {
        printf("(%d,%d)", vector_of_pairs[i].first, vector_of_pairs[i].second);
    }
    printf("]\n");
}

For the following input:

8              
1 0 5 6 2 3 7 4 
1 3

This is the output:

[(1,0)(5,2)(6,3)(3,5)(7,6)(4,7)]

But it should be

[(1,0)(6,3)(3,5)(7,6)(4,7)]

Also, for certain inputs I get seg faults so how can I safe guard against that?

Answer 1

Erase remove idiom at the rescue:

auto begin = v.begin() + l;
auto end = v.begin() + r + 1;
auto max_value = *std::max_element(begin, end);
v.erase(std::remove_if(begin, end,
                       [&](const auto& p) {return p.first != max_value.first; }),
        end);

Demo

Answer 2

Probabaly you want this

#include <iostream>
#include <vector>
using namespace std;


int main(int argc, char const *argv[]) {
    int N;
    cin >> N;
    vector< pair<int,int> > vector_of_pairs(N);

    for (int i = 0; i < N; i++) {
        int input;
        cin >> input;
        vector_of_pairs[i] = make_pair(input, i);
    }

    int l, r;
    cin >> l >> r;

    int max_in_range = vector_of_pairs[l].first;

    for (int i = l+1; i <= r; i++) {
        if (vector_of_pairs[i].first > max_in_range) {
            max_in_range = vector_of_pairs[i].first;
        }
    }
    int p=l;
    for (int i = l; i <= r;i++ ) {
        if (vector_of_pairs[p].first != max_in_range) {
            vector_of_pairs.erase(vector_of_pairs.begin()+p);
        }
        else p++; 
    }

    printf("[");
    for(int i = 0; i < vector_of_pairs.size(); i++) {
        printf("(%d,%d)", vector_of_pairs[i].first, vector_of_pairs[i].second);
    }
    printf("]\n");
}

Getting correct output :

[(1,0)(6,3)(2,4)(3,5)(7,6)(4,7)]

Explanation: When you delete an item in vector, items present after the deleted element get decreased their index by 1. Hence in the ith loop from l to r you shouldn't delete vec.begin()+i element, instead delete vec.begin()+l item until you find largest element, and delete vec.begin()+l+1 element after you find largest element.

Hope it helps.

Answer 3

If you don't need a stable algorithm you can simply sort the vector, get iterator for l in begin - end, get iterator for r in l - end and then remove all but the very last element between both found iterators.

#include <algorithm>
template<class V, class T>
void remove_range_but_max(V& vop, T const& l, T const& r)
{
    std::sort(vop.begin(), vop.end());
    auto lo = std::lower_bound(vop.begin(), vop.end(), l);
    auto hi = std::lower_bound(lo, vop.end(), r);
    if(hi != lo) --hi;
    vop.erase(lo, hi);
}

can be used like:

std::vector< std::pair< int , int > > input { 
    std::make_pair( 1 , 0 ) , std::make_pair( 0 , 1 ) , 
    std::make_pair( 3 , 2 ) , std::make_pair( 6 , 3 ) , 
    std::make_pair( 2 , 4 ) , std::make_pair( 4 , 5 ) , 
    std::make_pair( 7 , 6 ) , std::make_pair( 5 , 7 ) };
/* remove all pairs in range [(2,0), (6,0)) */
remove_range_but_max(input, std::make_pair(2,0), std::make_pair(6,0));
for(auto&& p : input) std::cout << p.first << ", " << p.second << "\n";

Prints:

0, 1
1, 0
5, 7
6, 3
7, 6

Answer 4

Quick and sleazy way:

std::sort(vector_of_pairs.begin(), vector_of_pairs.end());
vector_of_pairs.resize(1);

Just be sure to supply sort with the appropriate function to make the largest element get pushed to the first of the list.

Let me spell it out for you:

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

using namespace std;

bool i_said_to_do_this(const pair<int, int> &lhs, const pair<int, int> &rhs) {
  return lhs.first > rhs.first;
}

int main(int argc, char const *argv[]) {

    int pairs[][2] = {{1,0},{0,1},{3,2},{6,3},{2,4},{4,5},{7,6},{5,7}}; 
    vector< pair<int,int> > vector_of_pairs(8);

    for (int i{0}; i < 8; i++) {
      vector_of_pairs[i] = make_pair(pairs[i][0], pairs[i][1]);
    }

    std::sort(vector_of_pairs.begin(), vector_of_pairs.end(), i_said_to_do_this);
    vector_of_pairs.erase(vector_of_pairs.begin() + 1, vector_of_pairs.end());

    cout << "(" << vector_of_pairs[0].first << ", " << vector_of_pairs[0].second << ")" << endl;
}