First use of std::map in factors and prime factorization program

Question

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++;
    }
}

Answer 1

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).

Answer 2

• 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;