Sliding window using deque (runtime error)

user_9854514 0
Viewed 243

In the following program, I am trying to find the maximum in window size of k in an array of length n. For reference, the question is from LeetCode.

For example, if the array is [2 5 3 1 2] and window size is 3, then I have windows as [2 5 3], [5 3 1], [3 1 2] and corresponding maximums are 5, 5, 3.

I am using std::deque for this purpose but it is giving runtime error, I don't think any pointer invalidations are happening, I cannot find any. Please help me, I am stuck for a long time on this.

Here's my code:

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> d;
        for (int i = 0; i < k; ++i) {
            while (!d.empty() && d.front() < nums[i]) {
                d.pop_front();
            }
            d.push_front(nums[i]);
        }
        vector<int> ans;
        ans.push_back(d.back());

        int n = nums.size();
        for (int i = k; i < n; ++i) {
            while (1) {
                int elem = d.back();
                d.pop_back();
                if (elem == nums[i-k]) {
                    break;
                }
            }
            while (!d.empty() && d.front() < nums[i]) {
                d.pop_front();
            }
            d.push_front(nums[i]);
            ans.push_back(d.back());
        }
        return ans;
    }
};

Error message shown is this: 

Line 157: Char 16: runtime error: reference binding to misaligned address 0xbebebebebebec0ba for type 'int', which requires 4 byte alignment (stl_deque.h)
0xbebebebebebec0ba: note: pointer points here
<memory cannot be printed>
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/stl_deque.h:162:16
runtime-error deque data-structures c++
2 Answers

Observe this part of your code:

while (1) {
    int elem = d.back();         // get element
    d.pop_back();                // pop element

    if (elem == nums[i-k]) {     // compare element
        break;                   // and break on success
    }                            // What happens on failure???
}                                // Inifinite loop and UB!

The while loop is not exiting.

With its every iteration, you're accessing and popping an element from deque until it is empty because elem is not equal to nums[i-k].

Change while (1) to:

while ( !d.empty() )

Because you can get and pop an element from the deque only when it's not empty!

And, calling back() and pop_back() on an empty deque is Undefined Behavior:

From the documentation of std::deque::back():

Calling back on an empty container causes undefined behavior.

Same goes for std::deque::pop_back():

Calling pop_back on an empty container is undefined.

user_76702620

Sorry, I couldn't resist to make an alternative implementation.

Thereby, I tried to resemble closer the metapher of the sliding window – i.e. to slide a start and end index over the existing vector to determine the maxima for the sub-ranges.

I still had in mind that there exists a std::max() flavor which accepts an initializer list. (It was my original intention to use it somehow.)

However, while I was googling (to recall the details and have the links at hand) I stumbled into something even better (provided by <algorithm> as well):

std::max_element

Finds the greatest element in the range [first, last).

So, I made an MCVE to see how it could look like with std::max_element():

#include <iostream>
#include <algorithm>
#include <vector>

std::vector<int> maxSlidingWindow(
  const std::vector<int> &nums, // the sample data
  int k) // the length of sliding window
{
  if (k <= 0) return { }; // no maxima for insufficient range
  if ((size_t)k > nums.size()) k = nums.size(); // Ehem... window too large
  std::vector<int> ans;
  //ans.reserve(num.size() - k); // allocate final size at once (for more speed)
  for (size_t i = k; i <= nums.size(); ++i) {
    ans.push_back(
      *std::max_element(nums.begin() + i - k, nums.begin() + i));
  }
  return ans;
}      

std::ostream& operator<<(std::ostream &out, const std::vector<int> &vec)
{
  const char *sep = "";
  for (int value : vec) {
    out << sep << value;
    sep = " ";
  }
  return out;
}

int main()
{
  std::vector<int> sample = { 2, 5, 3, 1, 2 };
  std::cout << "Input: " << sample << '\n';
  std::cout << "Output: " << maxSlidingWindow(sample, 3) << '\n';
}

Output:

Input: 2 5 3 1 2
Output: 5 5 3

Live Demo on coliru

user_74785970
Related