CODEWITHSUNDEEP
c++stl
Akash
Akash

Reputation: 969

STL container to use for deleting a range of values

I have with myself n integers. I am given with starting value(SV) and ending value(EV), I need to delete the values that lie within the range of these values. The starting value as well the ending value may not exist in the set of n integers. This I need to do in O(No. Of elements deleted). Container such as vector of integers is failing since I need to B.Search and get the iterator that is greater than equal to the SV and for EV as well which takes an additional time of Log n. Any approach appreciated.

Edit : I was even thinking of using maps, storing the values as keys, and erasing on the basis of those key values. But the problem again is that the operation lower_bound and upper_bound occur in log time.

Upvotes: 0

Views: 284

Answers (3)

Persixty
Persixty

Reputation: 8589

As Marek R suggested there is std::multiset.

Complexity of the whole exercise is O(log(values.size()+std::distance(first,last)) where that distance is 'number of elements erased'.

It's difficult to see how you can beat that. At the end of it there is always going to be something that increases with the size of the container and log of it is a good deal!

#include <iostream>
#include <set>

void dump(const std::multiset<int>& values);

int main() {
    std::multiset<int> values;
    values.insert(5);
    values.insert(7);

    values.insert(9);
    values.insert(11);
    values.insert(8);
    values.insert(8);
    values.insert(76);

    dump(values);
    auto first=values.lower_bound(7);
    auto last=values.upper_bound(10);    
    values.erase(first,last);
    dump(values);

    return 0;
}

void dump(const std::multiset<int>& values){
    auto flag=false;
    std::cout<<'{';
    for(auto curr : values){
        if(flag){
            std::cout<<',';
        }else{
            flag=true;
        }
        std::cout<< curr;
    }
    std::cout<<'}'<<std::endl;
}

Upvotes: 0

Cory Kramer
Cory Kramer

Reputation: 117926

You can use the erase-remove idiom with std::remove_if to check if each value is between the two bounds.

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

int main()
{
    std::vector<int> values = {1,2,3,4,5,6,7,8,9};
    int start = 3;
    int stop = 7;
    values.erase(std::remove_if(values.begin(),
                                values.end(),
                                [start, stop](int i){ return i > start && i < stop; }),
                 values.end());
    for (auto i : values)
    {
        std::cout << i << " ";
    }
}

Output

1 2 3 7 8 9

Upvotes: 0

Marek R
Marek R

Reputation: 38052

If you need keep order in container just use: set http://www.cplusplus.com/reference/set/set/ or multiset http://www.cplusplus.com/reference/set/multiset/ if values can repeat.

Both have lower_bound and upper_bound functionality.

Upvotes: 3

Related Questions