Best way to group string members of object in a vector-CodePudding

I am trying to store a vector of objects and sort them by a string member possessed by each object. It doesn't need to be sorted alphabetically, it only needs to group every object with an identical string together in the vector.

IE reading through the vector and outputting the strings from beginning to end should return something like:

string_bulletSprite
string_bulletSprite
string_bulletSprite
string_playerSprite
string_enemySprite
string_enemySprite

But should NEVER return something like:

string_bulletSprite
string_playerSprite
string_bulletSprite
[etc.]

Currently I am using std:sort and a custom comparison function:

std::vector<GameObject*> worldVector;

[...]

std::sort(worldVector.begin(), worldVector.end(), compString);

And the comparison function used in the std::sort looks like this:

bool compString(GameObject* a, GameObject* b)
{
    return a->getSpriteNameAndPath() < b->getSpriteNameAndPath();
}

getSpriteNameAndPath() is a simple accessor which returns a normal string.

This seems to work fine. I've stress tested this a fair bit and it seems to always group things together the way I wanted.

My question is, is this the ideal or most logical/efficient way of accomplishing the stated goal? I get the impression Sort isn't quite meant to be used this way and I'm wondering if there's a better way to do this if all I want to do is group but don't care about doing so in alphabetic order.

Or is this fine?

CodePudding user response：

If you have lots of equivalent elements in your range, then std::sort is less efficient than manually sorting the elements.

You can do this by shifting the minimum elements to the beginning of the range, and then repeating this process on the remaining non-minimum elements

// given some range v

auto b = std::begin(v);  // keeps track of remaining elements
    
while (b != std::end(v))  // while there's elements to be arranged
{
    auto min = *std::min_element(b, std::end(v));  // find the minimum

    // move elements matching that to the front
    // and simultaneously update the remaining range
    b = std::partition(b, std::end(v), 
                       [=](auto const & i) {
                           return i == min;
                       });
}

Of course, a custom comparator can be passed to min_element, and the lambda in partition can be modified if equivalence is defined some other way.

Note that if you have very few equivalent elements, this method is much less efficient than using std::sort.

Here's a demo with a range of ints.

CodePudding user response：

I hope I understood your question correctly, if so, I will give you a little example of std::map which is great for grouping things by keys, which will most probably be a std::string.

Please take a look:

class Sprite
{
public:
    Sprite(/* args */)
    {
    }

    ~Sprite()
    {
    }
};

int main(int argc, char ** argv){

    std::map <std::string, std::map<std::string, Sprite>> sprites;
    std::map <std::string, Sprite> spaceships;
    spaceships.insert(std::make_pair("executor", Sprite()));
    spaceships.insert(std::make_pair("millennium Falcon", Sprite()));
    spaceships.insert(std::make_pair("death star", Sprite()));
    sprites.insert(std::make_pair("spaceships",spaceships)); 

    std::cout << sprites["spaceships"]["executor"].~member_variable_or_function~() << std::endl;

    return 0;
}