C++对对象表示矩阵坐标的指针向量进行排序

Question

我读取了一个由0、1和2填充矩阵的文件。当我找到一个1时，我创建一个BlueCar，当我创建一个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;
};

对于这个对象，我填充了两个向量：

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

考虑到我需要移动矩阵的小车，蓝色的移动，红色的移动，我认为最好的方法是排序这个向量。这样，我就能很快看到我考虑的汽车旁边的位置是否是空的。

由于蓝色汽车向下移动，我认为最好先按列排序"sparseBlu“，然后按行排序，而不是先按行排序"sparseRed”，然后再按列排序。

我怎样才能达到这个结果呢？(就性能而言)，当我用汽车填充向量时，立即对其排序更好，对吗？

Answer 1

简短答覆：

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());
          });

请重新考虑，如果使用指针真的是您需要这里。没有指针，你的噪音就会更小。

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());
          });

当这种排序在您的应用程序中是自然的时，您可能还会考虑重载operator < ()。这使得对sort()的调用更加明确：

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

一种几乎声明式的编程风格。

如果出于任何原因决定坚持使用指针，请考虑使用std::unique_ptr<>或std::shared_ptr<>而不是原始指针，以正确地管理对象的生存期。请记住，C++中没有垃圾收集。

Answer 2

std::sort有一个带有比较器的重载版本--一个用来比较两项的自定义函数：http://en.cppreference.com/w/cpp/algorithm/sort，因此您可以指定任何比较。

此外，您还可以考虑将您的汽车存储在稀疏矩阵(std::vector<std::vector<Car>>)中，其中空单元格只是空的。因此，您不需要排序，只需查看相应的单元格，如果它是空的。