c++ std pair vs vector speedup

Question

I wrote a maze program using a vector of lots of coordinates. Testing a 100x100 grid, when I used vector<int> the program took 383 seconds, but when I used pair<int,int> it took only 13 seconds. Where did this dramatic speedup come from?

Here is the code: (still to be improved)

#include <iostream>
#include <vector>
#include <stdlib.h>
#include <time.h>
#include <string>
#include <algorithm>
#include <utility>
using namespace std;

const int HEIGHT = 100, WIDTH = 100;

bool in_bounds(int x, int y)
{
    // Cells (0,0) to (WIDTH-1, HEIGHT -1)
    return (x >= 0 && x < WIDTH && y >= 0 && y < HEIGHT);
}

bool in_vector(int x, int y, vector<pair<int,int> > v)
{
    return find(v.begin(), v.end(), pair<int,int>(x,y)) != v.end();
}

vector<string> get_dir(int x, int y, vector<pair<int,int> > v)
{
    vector<string> open_dir; // Open neighbor cells
    if (in_bounds(x+1,y) && !in_vector(x+1,y,v))
        open_dir.push_back("e");
    if (in_bounds(x-1,y) && !in_vector(x-1,y,v))
        open_dir.push_back("w");
    if (in_bounds(x,y+1) && !in_vector(x,y+1,v))
        open_dir.push_back("n");
    if (in_bounds(x,y-1) && !in_vector(x,y-1,v))
        open_dir.push_back("s");
    return open_dir;
}

int main()
{
    vector<pair <int,int> > in_maze_cells {make_pair(0, 0)}, path {make_pair(0, 0)};
    vector<vector<string> > hor_walls (WIDTH, vector<string>(HEIGHT, "--")),
                            vert_walls (WIDTH, vector<string>(HEIGHT, "|"));

    srand(time(0));

    while (in_maze_cells.size() != HEIGHT * WIDTH)
    {
        pair <int,int> current_cell = path.back();
        int x = current_cell.first;
        int y = current_cell.second;

        vector<string> open_dir = get_dir(x, y, in_maze_cells);

         if (open_dir.size())
         {
             // Randomly pick an open cell and move to it
            string dir = open_dir[rand() % open_dir.size()];
            pair<int,int> new_cell;
            // Left and bottom wall coordinates match cell coordinates
            if (dir == "e"){
                new_cell = make_pair(x+1,y);
                vert_walls[x+1][y] = " ";
            }
            if (dir == "w"){
                new_cell = make_pair(x-1,y);
                vert_walls[x][y] = " ";
            }
            if (dir == "n"){
                new_cell = make_pair(x,y+1);
                hor_walls[x][y+1] = "  ";
            }
            if (dir == "s"){
                new_cell = make_pair(x,y-1);
                hor_walls[x][y] = "  ";
            }
            in_maze_cells.push_back(new_cell);
            path.push_back(new_cell);
         }
         else
            path.pop_back(); // Backtracking
    }
    // Top row
    for(int i=0; i<WIDTH; i++)
        cout << "+--";
    cout << "+" << endl;

    for(int i=HEIGHT-1; i>=0; i--)
    {
        for(int j=0; j<WIDTH; j++)
            cout << vert_walls[j][i] << "  ";
        cout << "|" << endl;

        for(int j=0; j<WIDTH; j++)
            cout << "+" << hor_walls[j][i];
        cout << "+" << endl;
    }
    return 0;
}

Answer 1

Vectors of vectors can be heavier, because a vector is more complicated than a pair.

Also, in your functions you were passing that vector by value:

bool in_vector(int x, int y, vector<cell> v)
{
    return find(v.begin(), v.end(), cell(x,y)) != v.end();
}

Which made it even more costly. Change it to

bool in_vector(int x, int y, vector<cell> const& v)

If you're interested I could give a few more optimization hints