Unexpectedly high memory usage using std :: stack and std :: map

Question

I am trying to cross a tree to visit all possible states of a 4x4 sliding puzzle. The algorithm I wrote was initially recursive, but this was not possible due to the (apparently) very deep tree. He crashed and reported segfault. Then I decided to rewrite the algorithm so that it does its work iteratively, and from what I see, it works fine. However, after a while, it begins to slow down significantly due to replacement. I made some calculations, but I can’t understand where all this memory usage comes from ...

The code is below, but here are the main features:

• std::stack<char, std::vector<char>> stack
• std::map<unsigned long long, int> distanceTable

Assuming that the memory size in memory is stackproportional to the number of elements it holds, and assuming the same for map(where the element is pair<unsigned long long, int>), I printed the expected amount of memory:

cout << (stack.size() * sizeof(char) +
         distanceTable.size() * sizeof(pair<unsigned long long, int>))/(1<<20) << "MB\n";

And compared the conclusion with the results top. When my own program reported 500 MB, it topreported that it uses more than half of all my memory (4 GB). This is factor 4, which is not taken into account by my reasoning. What am I missing here?

code:

#include <iostream>
#include <map>
#include <stack>
#include <vector>
#include <sstream>
#include "slider.h"
using namespace std;

typedef Slider<4> Slider4;
typedef Slider4::Move Move;
typedef map<unsigned long long, int> Map;
typedef stack<char, std::vector<char>> Stack;

Move const moves[] = {Slider4::N, Slider4::S, Slider4::E, Slider4::W};
Move const opposite[] = {Slider4::S, Slider4::N, Slider4::W, Slider4::E};

int const moveIdx[] = {0, 1, 2, 3};
int const oppositeIdx[] = {1, 0, 3, 2};


Map generateDistanceTable()
{
    // non-recursive tree-walker to generate the distance-table
    Map distanceTable;
    Stack stack;
    Slider4 slider;
    unsigned long long depth = 1;

    stack.push(-1);
    distanceTable[slider.hash()]= depth;
    while (depth != 0)
    {
        cout << (stack.size() * sizeof(char) + 
                 distanceTable.size() * sizeof(pair<unsigned long long, int>))/(1ULL<<20) << "MB\n";

        int currentMove = stack.top() + 1;

        // find next move
        while (currentMove != 4)
        {
            // Try the move
            if (!slider.move(moves[currentMove]))
            {
                ++currentMove;
                continue;
            }

            // Check the current state of the puzzle
            auto &d = distanceTable[slider.hash()];
            if (d != 0)
            { // already encountered this state -> move back
                int undoMove = oppositeIdx[currentMove];
                slider.moveUnsafe(moves[undoMove]);
                ++currentMove; // try next move
                continue;
            } 

            stack.push(currentMove);
            d = ++depth;
            currentMove = 0;
        }

        if (currentMove == 4)
        {
            int undoMove = oppositeIdx[stack.top()];
            slider.moveUnsafe(moves[undoMove]);
            --depth;
            stack.pop();
        }
    }
}

int main()
{
    Map table = generateDistanceTable();
}

Answer 1

-, std::map . node, (2 char MS ). , node , , , . 32- 20 ; 64- , 40.

std::vector ( std::stack), , reserve pre-allocate, , 1,5 2. , , . (, , , .)

, std::vector, std::lower_bound std::map.

, , , reserve . .

Answer 2

unsigned long long int. , ( ).

distanceTable.size() * sizeof(char)

, - :

distanceTable.size() *
    (2 * sizeof (void *) + sizeof (unsigned long long ) + sizeof (int))

Answer 3

, : .

wiki Tic-Tac-Toe:

: , 3 , . , , .