Improving O(n) while looping through a 2d array in C++

Question

A goal of mine is to reduce my O(n^2) algorithms into O(n), as it's a common algorithm in my Array2D class. Array2D holds a multidimensional array of type T. A common issue I see is using doubly-nested for loops to traverse through an array, which is slow depending on the size.

As you can see, I reduced my doubly-nested for loops into a single for loop here. It's running fine when I execute it. Speed has surely improved. Is there any other way to improve the speed of this member function? I'm hoping to use this algorithm as a model for my other member functions that have similar operations on multidimensional arrays.

        /// <summary>
        /// Fills all items within the array with a value.
        /// </summary>
        /// <param name="ob">The object to insert.</param>
        void fill(const T &ob)
        {
            if (m_array == NULL)
                return;

            //for (int y = 0; y < m_height; y++)
            //{
            //  for (int x = 0; x < m_width; x++)
            //  {
            //      get(x, y) = ob;
            //  }
            //}

            int size = m_width * m_height;
            int y = 0;
            int x = 0;

            for (int i = 0; i < size; i++)
            {
                get(x, y) = ob;

                x++;

                if (x >= m_width)
                {
                    x = 0;
                    y++;
                }
            }
        }

Answer 1

Make sure things are contiguous in memory as cache behavior is likely to dominate the run-time of any code which performs only simple operations.

For instance, don't use this:

int* a[10];
for(int i=0;i<10;i++)
  a[i] = new int[10];
//Also not this
std::vector< std::vector<int> > a(std::vector<int>(10),10);

Use this:

int a[100];
//or
std::vector<int> a(100);

Now, if you need 2D access use:

for(int y=0;y<HEIGHT;y++)
for(int x=0;x<WIDTH;x++)
  a[y*WIDTH+x];

Use 1D accesses for tight loops, whole-array operations which don't rely on knowledge of neighbours, or for situations where you need to store indices:

for(int i=0;i<HEIGHT*WIDTH;i++)
  a[i];

Note that in the above two loops the number of items touched is HEIGHT*WIDTH in both cases. Though it may appear that one has a time complexity of O(N^2) and the other O(n), it should be obvious that the net amount of work done is HEIGHT*WIDTH in both cases. It is better to think of N as the total number of items touched by an operation, rather than a property of the way in which they are touched.