Sort and search vectors by different criteria

Question

Class

class Player {
    std::string name;       
    int score;          
    int id;     
};      

I thought about how to write a code to sort and search vector of these classes by three criteria: name, id, and score.

The search what I want is to output the previous value and next value of the found element.

The code that I thought of

// v is a vector which the Player is randomly placed

sort(v.begin(), v.end(), [](Player& a, Player& b) {return a.getID() < b.getID(); });
std::vector<Player> ID_sorted_v = v;
sort(v.begin(), v.end(), [](Player& a, Player& b) {return a.getName() < b.getName(); });
std::vector<Player> Name_sorted_v = v;
sort(v.begin(), v.end(), [](Player& a, Player& b) {return a.getScore() < b.getScore(); });
std::vector<Player> Score_sorted_v = v;



std::cin >> input   // input is ID



for (vector<Player>::iterator search =
    find_if(ID_sorted_v.begin(), ID_sorted_v.end(),
        [input](Player& p) {
            return (p.getID() == input);
        });
    search != ID_sorted_v.end();
            search = find_if(++search, ID_sorted_v.end(), [input](Player& p) {
            return (p.getID() == input);
                }
            ))
{
    cout << *(search - 1) << endl << *search << endl << *(search + 1) << endl << endl;
}

for (vector<Player>::iterator search =
    find_if(Name_sorted_v .begin(), Name_sorted_v .end(),
        [input](Player& p) {
            return (p.getID() == input);
        });
    search != Name_sorted_v .end();
            search = find_if(++search, Name_sorted_v .end(), [input](Player& p) {
            return (p.getID() == input);
                }
            ))
{
    cout << *(search - 1) << endl << *search << endl << *(search + 1) << endl << endl;
}

for (vector<Player>::iterator search =
    find_if(Score_sorted_v.begin(), Score_sorted_v.end(),
        [input](Player& p) {
            return (p.getID() == input);
        });
    search != Score_sorted_v.end();
            search = find_if(++search, Score_sorted_v.end(), [input](Player& p) {
            return (p.getID() == input);
                }
            ))
{
    cout << *(search - 1) << endl << *search << endl << *(search + 1) << endl << endl;
}

Desired Results

// Player's <<Operator is overloaded
id 
name:dpygiewhuodfkfu, id:27        , score:206835634
name:jcawlfye       , id:30        , score:534327206
name:nwwffdkgvnegzio, id:31        , score:244395501

name
name:jcawcytbtbc    , id:1535712   , score:552239646
name:jcawlfye       , id:30        , score:534327206
name:jcawuqyvbttcrpq, id:559488    , score:495512171

score 
name:kawuzofo       , id:1030200   , score:534327131
name:jcawlfye       , id:30        , score:534327206
name:intny          , id:1770826   , score:534328056

I think the code is problematic in that it requires too much memory to prepare search. How can I make this code easier and simpler? I thought about it for many hours, but I couldn't think of a better way. Is that an impossible question?

Answer 1

Unnecessary sorting of data

You should be able to find the desired items in \$\mathcal{O}(N)\$ time without needing to sort the container multiple times. You can just linearly go through the items in the vector, and keep track of which item you have seen so far is the largest but also smaller than the search key, as well as the smallest that is also larger than the search key. Of course, if you do lots of searches it might be faster to sort the data first, but only if you search more intelligently:

Use std::equal_range() instead of std::find_if() on sorted data

The algorithm std::find_if() doesn't require the data to be sorted, and will just go throught the input in a linear fashion. This is very inefficient if the data is already sorted. Furthermore, it seems you want to find all elements that match a given search key, not the first one. In this case, you should use std::equal_range(): it will return the range of elements that match the search criteria.

Avoid duplicating the data

I think the code is problematic in that it requires too much memory to prepare search.

Indeed, you are making three copies of the original data, each sorted in a different way. What you could do instead is create three vectors of pointers into the original vector, or even references if you use std::reference_wrapper. There is still some overhead then, but much less than before.

Consider using a library that provides multi-index containers

What you want is a container that works a bit like std::set, but sorts the data on more than one index. You could write this yourself, but there are libraries that provide containers like that already, for example the Boost multi-index containers library.

Handle edge cases

Your code has a problem: what if I search for the lowest possible ID? Then the variable search will be equal to ID_sorted_v.begin(). However, you will then try to print the previous value using *(search - 1), which is illegal. The same goes when you search for something that is the last element of the container and you try to print the next value.

Be consistent

I see that sometimes you prefix types and functions from the standard library with std::, sometimes you don't. Be consistent. I recommend that you avoid using namespace std, and use std:: everywhere.

Make use of auto

You can use auto to avoid repeating type names. This can even make your code easier to read. For example, to copy a vector:

auto ID_sorted_v = v;

Or to iterate:

for (auto search = find_if(...); ...)

Prefer using '\n' insteadf of std::endl

Prefer using '\n' instead of std::endl; the latter is equivalent to the former, but also forces the output to be flushed, which is usually not necessary but also has a performance cost.