4
\$\begingroup\$

I've decided to rebuild the code with advices from previous topic C++ Least cost swapping 2 I've also decided to change input from passing the file name to passing the content of a file, so i am wondering if the input checking is still correct as in previous version. Please review my code.

#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
#include <cstdlib>

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

struct ObjectCollection
{
    size_t count = 0;
    std::vector<uint32_t> weights;
    std::vector<size_t> startingOrder;
    std::vector<size_t> endingOrder;
    uint32_t minWeight = MaxWeight;
};

std::size_t readValue(std::istringstream& iss)
{
    std::size_t value;
    iss >> value;
    if (!iss)
        throw std::runtime_error("Invalid input.");

    return value;
}

std::istringstream readLine(std::istream& stream)
{
    std::string line;
    std::getline(stream
        , line);
    if (line.empty()) throw std::runtime_error("Invalid input");
    return std::istringstream(line);
}

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

    int i = 1;
    while (!iss.eof() && i <= objectCount)
    {
        size_t orderNumber = readValue(iss);
        if (orderNumber - 1 > objectCount)
        {
            throw std::runtime_error("Too high index in order");
        }
        v.push_back(orderNumber - 1);
        ++i;
    }
    if (v.size() != objectCount) throw std::runtime_error("Too few values in line");
    return v;
}

void readWeightsAndSetMinWeight(std::istringstream iss, ObjectCollection& objects)
{
    objects.weights.reserve(objects.count);
    int i = 1;
    while (!iss.eof() && i <= objects.count)
    {
        uint32_t weight = static_cast<uint32_t>(readValue(iss));
        if (weight > MaxWeight)
        {
            throw std::runtime_error("Too high weight");
        }

        objects.weights.push_back(weight);
        objects.minWeight = std::min(objects.minWeight, weight);
        ++i;
    }
    if (objects.weights.size() != objects.count)
        throw std::runtime_error("Too few values in line");
}


ObjectCollection readFromFile(std::istream& stream)
{
    ObjectCollection objects;

    if (!std::cin.good())
        throw std::exception("Unable to read values");

    readLine(stream) >> objects.count;
    if (objects.count<MinVertexes || objects.count>MaxVertexes)
    {
        throw std::exception("Invalid amount of vertexes");
    }

    readWeightsAndSetMinWeight(readLine(stream), objects);
    objects.startingOrder = readOrder(readLine(stream), objects.count);
    objects.endingOrder = readOrder(readLine(stream), objects.count);

    return objects;
}

uint64_t calculateLowestCostOfWork(ObjectCollection const& objects)
{
    size_t n = objects.count;
    std::vector<size_t> permutation(n);

    //constructing permutation
    for (size_t 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)
    {
        if (visitedVertexes[i])
            continue;

        size_t cycleSize = 0;
        uint32_t cycleMinWeight = MaxWeight;
        long long cycleSumOfWeights = 0;

        size_t vertexToVisit = i;
        //decomposition for simple cycles and calculating parameters for each cycle
        while (!visitedVertexes[vertexToVisit])
        {
            visitedVertexes[vertexToVisit] = true;
            cycleSize++;
            vertexToVisit = permutation[vertexToVisit];
            cycleSumOfWeights += objects.weights[vertexToVisit];
            cycleMinWeight = std::min(cycleMinWeight, objects.weights[vertexToVisit]);
        }
        //calculating lowest cost for each cycle
        uint64_t swappingWithMinWeightInCycle = cycleSumOfWeights + (static_cast<uint64_t>(cycleSize) - 2) * static_cast<uint64_t>(cycleMinWeight);
        uint64_t swappingWithMinWeight = cycleSumOfWeights + cycleMinWeight + (static_cast<uint64_t>(cycleSize) + 1) * static_cast<uint64_t>(objects.minWeight);
        result += std::min(swappingWithMinWeightInCycle, swappingWithMinWeight);
    }
    return result;
}

int main()
{
    ObjectCollection elephants;
    try
    {
        elephants = readFromFile(std::cin);
        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;
}
\$\endgroup\$
1
\$\begingroup\$

Let's go through the code and see what can be improved.


#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
#include <cstdlib>

The header names should sorted in alphabetical order.


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

constexpr is usually put in the beginning because the benefits of each const don't really apply to constexprconstexpr applies to the entire declaration, just like static or inline does. You can't declare a "pointer to constexpr" or "reference to constexpr" (the pointer / reference itself will be constexpr instead).

uint32_t is not guaranteed to work (in fact, it is guaranteed to either work or be ill-formed). Use std::uint32_t. Also, since you manage to get rid of magic numbers, why not eliminate magic types as well? Something like

using Weight_t = std::uint32_t;

struct ObjectCollection
{
    size_t count = 0;
    std::vector<uint32_t> weights;
    std::vector<size_t> startingOrder;
    std::vector<size_t> endingOrder;
    uint32_t minWeight = MaxWeight;
};

Again, std::size_t and std::uint32_t. Also, it seems that there is a class invariant that the three vectors are all of size count. You may want to ensure this.


std::size_t readValue(std::istringstream& iss)
{
    std::size_t value;
    iss >> value;
    if (!iss)
        throw std::runtime_error("Invalid input.");

    return value;
}

This is overly restrictive, both in std::size_t and std::istringstream. Make it a template:

template <typename T, typename Istream>
T read_value(Istream&& is)
{
    T value;
    if (!(is >> value))
        throw std::runtime_error{"invalid input"};
    return value;
}

std::istringstream readLine(std::istream& stream)
{
    std::string line;
    std::getline(stream
        , line);
    if (line.empty()) throw std::runtime_error("Invalid input");
    return std::istringstream(line);
}

This function should return a string, not a string stream, in my opinion. Also, why the line break in the getline?


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

    int i = 1;
    while (!iss.eof() && i <= objectCount)
    {
        size_t orderNumber = readValue(iss);
        if (orderNumber - 1 > objectCount)
        {
            throw std::runtime_error("Too high index in order");
        }
        v.push_back(orderNumber - 1);
        ++i;
    }
    if (v.size() != objectCount) throw std::runtime_error("Too few values in line");
    return v;
}

Don't take streams by value. Take by reference instead. And it doesn't make very much sense to declare a parameter as top-level const.

The while loop should really be a for loop. Loop counters should start from 0 and use < instead of starting from 1 and using <=. Like this:

for (std::size_t i = 0; i < objectCount; ++i) {
    // ...
}

The readWeightsAndSetMinWeight function is similar. Casting the result of readValue to uint32_t doesn't feel right; with the template above, this problem is solved.


It seems that you check the input status every time you read something, and throw an exception on failure. You can automate this by using istream::exceptions:

std::cin.exceptions(std::ios_base::failbit);

std::cin will automatically throw exceptions of type std::ios_base::failure when failbit is on.


This should be enough to get you started.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.