CODEWITHSUNDEEP
c++sortingmatrixvector
rh0x
rh0x

Reputation: 1463

C++ Sort a vector of pointers in which the objects represent matrix coordinates

I read a file in which a matrix is filled with 0, 1 and 2. When I find a 1 I create a BlueCar, when 2 I create RedCar:

class BlueCar : public Car
{
    public:
        BlueCar(){};
        BlueCar(int x, int y);
        void move();
        virtual ~BlueCar();
};

class RedCar : public Car
{
    public:
        RedCar(){};
        RedCar(int x, int y);
        void move();
        virtual ~RedCar();
};

class Car
{
    public:
        Car();
        Car(int x, int y);
        virtual ~Car();
        virtual void move() = 0;

    private:
        int x,y;
};

With this objects I fill two vectors:

    std::vector<BluCar*> *sparseBlu;
    std::vector<RedCar*> *sparseRed;

Considering that I need to move the cars of the matrix, and that Blue ones move downward and Red ones move rightward, I think the best approach is to sort this vectors. In that way I can see quickly if the position next to the car I'm considering is empty.

Since Blue cars move downward I think it's better to sort "sparseBlu" first by column and then by row, instead "sparseRed" first by row and then by column.

How can I achieve this result? It's better (in terms of performance) to sort the vector immediately when I fill it car by car, right?

Upvotes: 0

Views: 1226

Answers (2)

Andriy Tylychko
Andriy Tylychko

Reputation: 16256

std::sort has an overloaded version with a comparator - a custom function to compare two items: http://en.cppreference.com/w/cpp/algorithm/sort, so you can specify any comparison.

Also you can consider storing your cars in a sparse matrix (std::vector<std::vector<Car>>) where empty cells are just empty. So you don't need to sort and can just look at corresponding cell if it's empty.

Upvotes: 0

cdonat
cdonat

Reputation: 2822

Short answer:

std::sort(std::begin(*sparseBlu), std::end(*sparseBlu),
          [](const BlueCar* lhs, const BlueCar* rhs) -> bool {
              return lhs->get_x() < rhs->get_x() ||
                     (lhs->get_x() == rhs->get_x() && lhs->get_y() < rhs->get_y());
          });

std::sort(std::begin(*sparseRed), std::end(*sparseRed),
          [](const RedCar* lhs, const RedCar* rhs) -> bool {
              return lhs->get_y() < rhs->get_y() ||
                     (lhs->get_y() == rhs->get_y() && lhs->get_x() < rhs->get_x());
          });

Please reconsider, if using pointers really is what you need here. Without pointers you have less noise.

std::vector<BluCar> sparseBlu;
std::vector<RedCar> sparseRed;

std::sort(std::begin(sparseBlu), std::end(sparseBlu),
          [](const BlueCar& lhs, const BlueCar& rhs) -> bool {
              return lhs.get_x() < rhs.get_x() ||
                     (lhs.get_x() == rhs.get_x() && lhs.get_y() < rhs.get_y());
          });

std::sort(std::begin(sparseRed), std::end(sparseRed),
          [](const RedCar& lhs, const RedCar& rhs) -> bool {
              return lhs.get_y() < rhs.get_y() ||
                     (lhs.get_y() == rhs.get_y() && lhs.get_x() < rhs.get_x());
          });

When that kind of ordering is natural in your application you might also consider to overload operator < (). That makes the calls to sort() much more explicit:

std::sort(std::begin(sparseBlu), std::end(sparseBlu), std::less<BlueCar>);
std::sort(std::begin(sparseRed), std::end(sparseRed), std::less<RedCar>);

An almost declarative programming style.

If you decide to stick with pointers for whatever reason, please consider to use std::unique_ptr<> or std::shared_ptr<> instead of raw pointers, to manage the objects lifetime correctly. Remember, that there is no garbage collection in C++.

Upvotes: 1

Related Questions