CODEWITHSUNDEEP
c++sortingc++11vector
Jannat Arora
Jannat Arora

Reputation: 2989

Selectively sort vector c++

I have the following vector:

vector<unsigned> vec = {5, 6, 5, 4, 1, 3, 0, 4}

Now I want to sort this vector lexicographically by odd indices (and if odd indices are equal, then by the even indices). Such that the sorted vector "vec" is:

   {0, 4, 1, 3, 5, 4, 5, 6}

I know std::sort is going to sort "vec" entirely. Is it possible to use std::sort to sort the vector selectively. Similarly for std::lower_bound. Is it possible to find the lower_bound using odd indices only.

I want the same effect as vector of pair. For efficiency reasons I am not storing vec as vector of pair.

Upvotes: 1

Views: 249

Answers (4)

Simon Kraemer
Simon Kraemer

Reputation: 5680

Not the fastest sorting algorithm but it works:

#include <vector>
#include <algorithm>

int main()
{
    std::vector<unsigned> vec = { 5, 6, 5, 4, 1, 3, 0, 4 };

    if (vec.size() > 1 && vec.size() % 2 == 0)
    {
        for (size_t i1 = 0, j1 = i1 + 1; i1 < vec.size() - 1 && j1 < vec.size(); i1+=2, j1 = i1+1)
        { 
            for (size_t i2 = i1 + 2, j2 = i2 + 1; i2 < vec.size() - 1 && j2 < vec.size(); i2 += 2, j2 = i2 + 1)
            {
                if (vec[i1] > vec[i2] || (vec[i1] == vec[i2] && vec[j1] > vec[j2]))
                {
                    std::swap(vec[i1], vec[i2]);
                    std::swap(vec[j1], vec[j2]);
                }
            }
        }
    }
    return 0;
}

[On Coliru]

Upvotes: 0

eerorika
eerorika

Reputation: 238451

This can be implemented by calling std::sort with a custom iterator, that skips indices and with a custom comparison fucnction, that compares the adjacent value if current comparison is equal.

The custom iterator can be built on top of the existing iterator. A construct like that is called an iterator adaptor. You don't need to write such iterator adaptor from scratch yourself, since boost has already done the hard work. You can use boost::adaptors::strided. If you cannot use boost, then you can re-implement it.

Much simpler solution would be to use pairs, though. Or better yet, a structure if there are sensible names for the members.

Upvotes: 1

Jarod42
Jarod42

Reputation: 218238

With range-v3, you may do:

std::vector<unsigned> vec = {5, 6, 5, 4, 1, 3, 0, 4};
auto pair_view = ranges::view::zip(vec | ranges::view::stride(2),
                                   vec | ranges::view::drop(1) |  ranges::view::stride(2));

ranges::sort(pair_view);

Demo

Upvotes: 6

Humam Helfawi
Humam Helfawi

Reputation: 20324

Not so efficient but a working solution would be:

std::vector<std::pair<size_t,unsigned int>> temp_vec;
temp_vec.reserve(vec.size());
for(size_t i=0;i<vec.size();++i){
    temp_vec.emplace_back(i,vec[i]);
}
std::sort(temp_vec.begin(),temp_vec.end(),[](auto l,auto r){
    return /* some condition based on l.first and r.first*/;
});
std::transfrom(temp_vec.begin(),temp_vec.end(),vec.begin(),[](auto item){
     return item.second;
});

Upvotes: 1

Related Questions