C++最小成本交换2

Question

我已经给出了一个问题的解决方案，这个问题涉及到改变具有某种质量的对象的顺序，所以需要花费一个对象A的质量和一个对象B的质量来进行交换。

问题的全部描述和原始源代码都在C++中的最小成本交换，请查看我的代码。

#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
int constexpr MaxWeight = 6500, MinVertexes = 2, MaxVertexes = 1000000;

struct ObjectCollection 
{
    int amountOfObjects = 0;
    std::vector<int> weights;
    std::vector<int> startingOrder;
    std::vector<int> endingOrder;
    int minWeight = MaxWeight;
};

std::vector<int> readOrder(std::istringstream& iss, int const amountOfObjects) 
{
    std::vector<int> v;
    v.reserve(amountOfObjects);
    int i = 1;
    while(!iss.eof() && i <= amountOfObjects)
    {
        int number;
        iss >> number;
        if (number - 1 > amountOfObjects) throw std::logic_error("Too high index in order");
        v.push_back(number-1);
        i++;
    }
    if (v.size() != amountOfObjects) throw std::logic_error("Too few values in line");
    return v;
}

void readWeightsAndSetMinWeight(std::istringstream& iss, ObjectCollection& objects)
{
    objects.weights.reserve(objects.amountOfObjects);
    int i = 1;
    while (!iss.eof() && i <= objects.amountOfObjects)
    {
        int number;
        iss >> number;
        if (number> MaxWeight) throw std::logic_error("Too high weight");
        objects.weights.push_back(number);
        objects.minWeight = std::min(objects.minWeight, number);
        i++;
    }
    if (objects.weights.size() != objects.amountOfObjects) throw std::logic_error("Too few values in line");
}

//todo version for weight

ObjectCollection readFromFile(std::string const& filename)
{
    ObjectCollection objects;
    std::ifstream file(filename);

    if (!file.is_open()) throw std::exception("Unable to open file");

    for (int i = 0; i < 4; i++)
    {
        std::string line;
        std::getline(file, line);
        if (line.empty()) throw std::logic_error("Invalid input");
        std::istringstream iss(line);

        if (i == 0)
        {
            iss >> objects.amountOfObjects;
            if (objects.amountOfObjects<MinVertexes || objects.amountOfObjects>MaxVertexes) throw std::exception("Invalid amount of vertexes");
        }
        else if (i == 1)
        {
            objects.weights.reserve(objects.amountOfObjects);
            for (int j = 0; j < objects.amountOfObjects; j++)
            {
                //int number;
                //iss >> number;
                //objects.weights.push_back(number);
                //objects.minWeight = std::min(objects.minWeight, objects.weights[j]);
                readWeightsAndSetMinWeight(iss, objects);
            }
        }
        else if (i == 2)
        {
            objects.startingOrder = readOrder(iss,objects.amountOfObjects);
        }
        else if (i == 3)
        {
            objects.endingOrder = readOrder(iss, objects.amountOfObjects);
        }
    }
    return objects;
}

long long calculateLowestCostOfWork(ObjectCollection const& objects)
{
    int n = objects.amountOfObjects;
    std::vector<int> permutation(n);

    //constructing permutation
    for (int i = 0; i < n; i++) 
    {
        permutation[objects.endingOrder[i]] = objects.startingOrder[i];
    }

    long long result = 0;
    std::vector<bool> visitedVertexes(n);

    for (int i = 0; i < n; i++)
    {
        int numberOfElementsInCycle = 0;
        int minWeightInCycle = MaxWeight;
        long long sumOfWeightsInCycle = 0;
        if (!visitedVertexes[i])
        {
            int vertexToVisit = i;
            //decomposition for simple cycles and calculating parameters for each cycle
            while (!visitedVertexes[vertexToVisit])
            {
                visitedVertexes[vertexToVisit] = true;
                numberOfElementsInCycle++;
                vertexToVisit = permutation[vertexToVisit];
                sumOfWeightsInCycle += objects.weights[vertexToVisit];
                minWeightInCycle = std::min(minWeightInCycle, objects.weights[vertexToVisit]);
            }
            //calculating lowest cost for each cycle
            long long swappingWithMinWeightInCycle = sumOfWeightsInCycle + (static_cast<long long>(numberOfElementsInCycle) - 2) * static_cast<long long>(minWeightInCycle);
            long long swappingWithMinWeight =  sumOfWeightsInCycle + minWeightInCycle + (static_cast<long long>(numberOfElementsInCycle) + 1) * static_cast<long long>(objects.minWeight);
            result += std::min(swappingWithMinWeightInCycle, swappingWithMinWeight);
        }
    }
    return result;
}

int main(int argc, char* argv[])
{
    if (argc < 2)
    {
        std::cerr << "Error: missing filename\n";
        return 1;
    }

    ObjectCollection elephants;
    try
    {
        elephants = readFromFile(argv[1]);
        std::cout << calculateLowestCostOfWork(elephants);
    }
    catch (std::exception const& ex) 
    {
        std::cerr << "Error: " << ex.what() << "\n";
        return 1;
    }
    catch (...)
    {
        std::cerr << "Error unknown \n";
        return 1;
    }
    return 0;
}

Answer 1

这不是一个比较审查。

自记录代码

有一个标准的头文件提供退出常量值main()。对于C和C++，用于退出的标准常数是EXIT_SUCCESS和EXIT_FAILURE。它的C++头是

#include <cstdlib>

int main(int argc, char* argv[])
{
    if (argc < 2)
    {
        std::cerr << "Error: missing filename\n";
        return EXIT_FAILURE;
    }

    ObjectCollection elephants;
    try
    {
        elephants = readFromFile(argv[1]);
        std::cout << calculateLowestCostOfWork(elephants);
    }
    catch (std::exception const& ex)
    {
        std::cerr << "Error: " << ex.what() << "\n";
        return EXIT_FAILURE;
    }
    catch (...)
    {
        std::cerr << "Error unknown \n";
        return EXIT_FAILURE;
    }
    return EXIT_SUCCESS;
}

垂直间距

如果函数中的逻辑块之间存在一些垂直间距，则代码可能更容易阅读和维护。

仅一行上的数字常量

如果数值常量位于单独的行上，则代码可能更容易读取和维护每个声明。

int constexpr MaxWeight = 6500;
int constexpr MinVertexes = 2;
int constexpr MaxVertexes = 1000000;

然后和其他条款

计划未来的维修。更新代码通常需要在then语句中插入额外的语句或在if语句中插入else子句。通常，使所有if语句都具有复合语句以方便将来的修改是一种良好的做法。将if与操作分离也使代码更具可读性。

if (number - 1 > amountOfObjects) throw std::logic\_error("Too high index in order");

    if (number - 1 > amountOfObjects)
    {
        throw std::logic_error("Too high index in order");
    }

变量名

在输入函数中，如果使用的变量指示正在读取的内容，代码可能更容易理解，变量名number可能有点过于笼统。我们知道它是一个数字，因为它被声明为int。在函数int readWeightsAndSetMinWeight()中，也许可以使用weight而不是number？

注释代码

当代码被移动到函数中时，通常没有理由将代码放在原来的注释中。对于必须维护代码的人来说，这可能会让人感到困惑。

Answer 2

if (line.empty()) throw std::logic_error("Invalid input");

std::logic_error用于“违反逻辑前提条件或类不变量”，这通常转化为程序员错误(并且意味着很少使用正确的异常类型)。

无效的输入数据当然不适合这个类别，我们可能应该使用std::runtime_error。

for (int i = 0; i < 4; i++)
{
    std::string line;
    std::getline(file, line);
    if (line.empty()) throw std::logic_error("Invalid input");
    std::istringstream iss(line);

    if (i == 0) ...
    else if (i == 1) ...
    else if (i == 2) ...
    else if (i == 3) ...
}

每一次迭代都有一个具有独立分支的for循环？嗯。

我们可以通过将需要重复的代码(读取一行)抽象为单独的函数来避免这种情况，然后执行如下操作：

objects.count = ReadObjectCount(readLine(file));
objects.weights = ReadObjectWeights(readLine(file), objects.count);
objects.minWeight = CalculateMinWeight(objects.weights);
objects.startingOrder = ReadObjectOrder(readLine(file), objects.count);
objects.endingOrder = ReadObjectOrder(readLine(file), objects.count);
...

在我们阅读了所有的权重之后，计算最小权重可能会更精确，而不是在我们开始的时候这样做。

amountOfObjects应该是一个std::size_t，因为它不能是负的，并且应该匹配向量的索引类型。

同样，如果顺序向量将索引表示为向量，则顺序向量应该包含std::size_t。

据推测，权重也不可能是负值。因此，我们应该为它们使用一个无符号类型，如std::uint32_t或std::uint64_t，并且保持一致(当前代码同时使用int和long long)。

std::vector<int> readOrder(std::istringstream& iss, int const amountOfObjects) 
{
    std::vector<int> v;
    v.reserve(amountOfObjects);
    int i = 1;
    while(!iss.eof() && i <= amountOfObjects)
    {
        int number;
        iss >> number;
        if (number - 1 > amountOfObjects) throw std::logic_error("Too high index in order");
        v.push_back(number-1);
        i++;
    }
    if (v.size() != amountOfObjects) throw std::logic_error("Too few values in line");
    return v;
}

我们应该通过检查流状态来检查是否成功地读取每个数字。(同样，我们可以将其抽象为一个单独的函数)。

想必索引必须是>= 0 (以及小于对象计数)，所以我们应该检查如果我们没有使用无符号类型。

也许是这样：

std::size_t readValue(std::istringstream& iss)
{
    std::size_t value;
    iss >> value;

    if (!iss) // check if we failed to read the value
        throw std::runtime_error("Invalid input.");

    return value;
}

std::vector<std::size_t> readOrder(std::istringstream iss, std::size_t objectCount)
{
    std::vector<std::size_t> v;
    v.reserve(objectCount);

    for (auto i = std::size_t{0}; i != objectCount; ++i)
        v.push_back(readValue(iss, objectCount));

    std::string anything;
    iss >> anything;

    if (!anything.empty() || !iss.eof())
        throw std::runtime_error("Extra stuff at end of line.");

    OffsetAndCheckValues(v); // do the range checking and -1

    return v;
}

稍后(在读取所有值之后)执行范围检查和偏移，使readValue函数更可重用。

在C++中，通常使用增量前运算符(++i)迭代，因为它更准确地反映了意图(我们不需要临时的非增量变量)。

使用!=作为结束条件(而不是< )也更常见，因为这可以更好地转换为使用迭代器。

确保使用适当的迭代类型(例如，用于迭代向量索引的std::size_t )。

for (std::size_t i = 0; i != objects.count; ++i)

使用描述性名称是好的，但其中有些名称有点过分。在某种程度上，较长的名称只会阻碍可读性。

std::vector<bool> visited(objects.count);
...
    std::size_t cycleSize = 0;
    std::uint64_t cycleMin = MaxWeight;
    std::uint64_t cycleSum = 0;

为了避免不必要的缩进，喜欢早期使用return或continue：

    if (visited[i])
        continue;

    // no need to indent this code...

请注意，如果我们访问了顶点，则不使用numberOfElementsInCycle (和其他)，因此可以在检查之后声明。