std::set_intersection elementary usage

Question

I practice the c++ standard library. Here is one problem I have with the usage of set_intersection:

I try to solve the problem 45 of project Euler:

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle      Tn=n(n+1)/2     1, 3, 6, 10, 15, ...
Pentagonal    Pn=n(3n−1)/2    1, 5, 12, 22, 35, ...
Hexagonal     Hn=n(2n−1)      1, 6, 15, 28, 45, ...

It can be verified that T285 = P165 = H143 = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

here is my tricks-free code for this:

using bint = unsigned long long;

auto pb045()->bint
{

    for (auto max_nb = 1024;; max_nb = max_nb << 1) {

            auto tris = std::vector<bint>{};
            tris.reserve(max_nb);

            auto pentas = std::vector<bint>{};
            pentas.reserve(max_nb);

            auto hexas = std::vector<bint>{};
            hexas.reserve(max_nb);
            for (auto i = 0; i < max_nb; i++) {
                    tris.push_back(i * (i + 1) / 2);
                    pentas.push_back(i * (3 * i - 1) / 2);
                    hexas.push_back(i * (2 * i - 1));
            }

            auto intersection1 = std::vector<bint>(max_nb);

            std::sort(tris.begin(), tris.end());
            std::sort(hexas.begin(), hexas.end());
            std::sort(pentas.begin(), pentas.end());

            auto 
                    begin = intersection1.begin(),
                    end =
            std::set_intersection(hexas.begin(), hexas.end(),
                                  pentas.begin(), pentas.end(),
                                  intersection1.begin());

            auto intersection = std::vector<bint>(end - begin);

            std::set_intersection(begin, end,
                                  tris.begin(), tris.end(),
                                  intersection.begin());

            if (intersection.size() > 3) {
                    // [0] -> 0
                    // [1] -> 1
                    _ASSERT(intersection[2] == 40755);
                    return intersection[3];
            }
    }

here:

• the algorithm does not gives the good solution
• if I comment the sort lines, it crashes (on MS VC++) with the message sequence not ordered in debug mode, and runs for long in release mode (but the numbers are inserted in increasing order, so the sort is useless).

I thinks that I miss something here.

Answer 1

You have overflow for pentas when i == 37838 (i is an int), so your array is no longer sorted by construction. You probably want bint i.