4
\$\begingroup\$

This is from an older question of mine that I decided to revisit:

Simplifying and optimizing factors and prime factorization generator

In that question, someone suggested I use an std::map to hold the factors generated from my inputted number. I've also decided to use it with my generated prime factorization, which also works. Based on what I've found online, auto is one way of iterating through an std::map. I've decided to use that since it appears that my compiler supports C++11.

Am I using std::map appropriately here, or am I developing some bad habits? I want to develop good habits since I'm interested in using it more in the future.

#include <iostream>
#include <cstdint>
#include <map>
#include <cmath>

void displayFactors(const std::map<uint64_t, uint64_t> &factors);
void displayPrimeFactorization(const std::map<uint64_t, uint64_t> &primeFactorization);
void findFactors(uint64_t, std::map<uint64_t, uint64_t> &factors);
void findPrimeFactorization(uint64_t positiveInt, std::map<uint64_t, uint64_t> &primeFactorization);

int main()
{
    std::map<uint64_t, uint64_t> factors;
    std::map<uint64_t, uint64_t> primeFactorization;
    uint64_t positiveInt;

    std::cout << "\n\n> Positive Int: ";
    std::cin >> positiveInt;

    findFactors(positiveInt, factors);
    std::cout << "\n\n  * Factors:\n\n";
    displayFactors(factors);

    findPrimeFactorization(positiveInt, primeFactorization);
    std::cout << "\n  * Prime Factorization:\n\n      ";
    displayPrimeFactorization(primeFactorization);

    std::cout << std::endl << std::endl;
    std::cin.ignore();
    std::cin.get();
}

void displayFactors(const std::map<uint64_t, uint64_t> &factors)
{
    for (auto iter = factors.begin(); iter != factors.end(); ++iter)
    {
        std::cout << "      " << iter->first << " x " << iter->second << "\n";
    }
}

void displayPrimeFactorization(const std::map<uint64_t, uint64_t> &primeFactorization)
{
    for (auto iter = primeFactorization.begin(); iter != primeFactorization.end(); ++iter)
    {
        if (iter != primeFactorization.begin()) std::cout << " x ";
        std::cout << iter->first;
        if (iter->second > 1) std::cout << '^' << iter->second;
    }
}

void findFactors(uint64_t positiveInt, std::map<uint64_t, uint64_t> &factors)
{
    uint64_t sqrtInt = static_cast<uint64_t>(sqrt(static_cast<double long>(positiveInt)));

    for (uint64_t iter = 1; iter <= sqrtInt; ++iter)
    {
        if (positiveInt % iter == 0)
        {
            uint64_t quotient = positiveInt / iter;
            factors[iter] = quotient;
        }
    }
}

void findPrimeFactorization(uint64_t positiveInt, std::map<uint64_t, uint64_t> &primeFactorization)
{
    uint64_t divisor = 2;
    uint64_t power = 0;

    while (positiveInt != 1)
    {
        while (positiveInt % divisor == 0)
        {
            positiveInt /= divisor;
            power++;
        }

        if (power > 0)
            primeFactorization[divisor] = power;

        power = 0;
        divisor++;
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ Few things for others to cover: either make these functions static or put them in a namespace, for C++ 11 you can consider std::unordered_map, using auto for everything you can, range-based for loops, ... \$\endgroup\$ – Mike Weller May 28 '13 at 11:35
  • \$\begingroup\$ ...also returning factors/primeFactors by value (in combination with move semantics) \$\endgroup\$ – Mike Weller May 28 '13 at 11:41
  • \$\begingroup\$ Is that recommended because I'm returning objects by value? I can do that, as well as auto (my compiler doesn't seem to support range-based loops). \$\endgroup\$ – Jamal May 28 '13 at 15:12
3
\$\begingroup\$

Looks generally ok. You can actually shorten iteration even more if your compiler supports range-based for loops:

for (auto iter = factors.begin(); iter != factors.end(); ++iter)
{
    std::cout << "      " << iter->first << " x " << iter->second << "\n";
}

Can be written as:

for(const auto& pair : factors) {
    std::cout << "      " << pair.first << " x " << pair.second << "\n";
}

Further, prefer to return by value than pass by non-const reference:

void findFactors(uint64_t positiveInt, std::map<uint64_t, uint64_t> &factors)

Should be

std::map<uint64_t, uint64_t> findFactors(uint64_t positiveInt)

This will be exactly the same speed in about 98% of situations thanks to (Named) Return Value Optimization.

One final thing to be aware of with map: insertion (or lookup) using [] vs insert. [] performs a lookup; if the value is not found, it is default-constructed and then the copy-assignment operator (operator=) is called to give the object its value. Thus, [] performs a lookup, construction and copy assignment. It also requires a default constructor to be available. insert, on the other hand does not require a default constructor, and will (from memory) call only the copy constructor. It is thus often (slightly) faster (although for plain old data, the difference will be non-existent). The big difference is not requiring a default constructor, which may not exist.

Finally, a really small thing: it should (technically) be std::uint64_t. Importing <cstdint> (as opposed to stdint.h), based on the C++ spec, will guarantee that this (and uint32_t, etc) will live in the std namespace. It may also put them in the global namespace. Most headers seem to put them in both, but to be 100% portable (according to the standard, anyway), it should be prefixed with a std (or brought into scope with a using std::uint64_t).

\$\endgroup\$
7
  • \$\begingroup\$ Thanks! I'm also doing a variation with std::list/std::pair (also for the first time), and I'll decide which one I prefer after checking the execution speed. Since I don't think it's too different from std::map (minus syntax), I won't need to ask a new question about it. Moreover, would std::list/std::pair be more appropriate since I don't need these paired values to be sorted outside of the loop? \$\endgroup\$ – Jamal May 28 '13 at 4:35
  • \$\begingroup\$ @JamalA If you're just calculating a factor for one number, there likely won't be any speed difference. If you decide to store factorizations for given numbers for later use, however, the speed difference will likely be significant. I'd likely use a map anyway (or even an unordered_map since you don't care about order). Honestly, the real use cases for std::list are fairly limited. \$\endgroup\$ – Yuushi May 28 '13 at 4:41
  • \$\begingroup\$ There's an std::unordered_map? Nice. I'll try that instead. I've just finished testing my std::list/std::pair code, and the speed difference was a tad worse. I'll try this out. \$\endgroup\$ – Jamal May 28 '13 at 4:52
  • \$\begingroup\$ @JamalA Again, part of C++11, but as far as I know, all recent versions of gcc, visual studio and clang have it. It sits in <unordered_map> (there's also, unsurprisingly, an unordered_set too). \$\endgroup\$ – Yuushi May 28 '13 at 4:54
  • 1
    \$\begingroup\$ Working on sorted data can often be faster due to branch prediction, cache locality, etc. \$\endgroup\$ – Mike Weller May 28 '13 at 11:42
2
\$\begingroup\$
  • The function prototypes can be removed by defining main() below the functions.

  • This type name is a little long:

    std::map<uint64_t, uint64_t>
    

    and can be "shortened" with a typedef:

    typedef std::map<uint64_t, uint64_t> IntegerMap;
    
  • calculate() can be slow as it's doing two casts. It's especially unnecessary as it's just being done to obtain one number. It can be simplified and made faster by following this advice.

  • The name iter is misleading for this loop:

    for (uint64_t iter = 1; iter <= sqrtInt; ++iter)
    

    It's not actually an iterator, but a loop counter. It could just be given a single-character name, such as i, which is acceptable for such situations only.

  • The if statement in findPrimeFactorization():

    if (power > 0)
        primeFactorization[divisor] = power;
    

    should use curly braces to help with maintenance, even though it's a single line. Curly braces are used correctly elsewhere, so they should be used consistently here.

    if (power > 0)
    {
        primeFactorization[divisor] = power;
    }
    
  • This is unnecessary, especially with the std::endls that also flush the buffer. Just remove it.

    std::cout << std::endl << std::endl;
    
\$\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.