stack pop() 导致 "reference binding to misaligned address" 错误

Question

我正在尝试为这个 leetcode 问题编写解决方案 https://leetcode.com/problems/maximum-frequency-stack/

class FreqStack {
public:
    
   
    map<int, int>mp;
    map<int, stack<int>, greater<int>>st;
    FreqStack() {
        
    }
    
    void push(int x) {
        mp[x]++;
        st[mp[x]].push(x);
        
       
    }
    
    int pop() {
        stack<int>&v=st.begin()->second;
        
        int t=v.top();
        
        
        if(!v.empty()){
        v.pop();
        }
        else{
            st.erase(st.begin());
        }
       
        return t;
    }
};

为什么

v.pop()

导致“引用绑定到未对齐的地址”错误？

Answer 1

可能这里有问题 stack<int>&v=st.begin()->second;，也许尝试在不使用那里的引用的情况下实现你的算法。

从技术上讲，我猜你正在引用你的指针指向内存的一部分，这部分内存还不存在，并且你会得到一个 UB，因为你会继续阅读错误。

如果您删除 &，您会发现您的代码没有错误。但是，它会输出部分不正确的结果。

除此之外，我们还可以使用unordered_map。

这会通过：

// This block might trivially optimize the exec time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    return 0;
}();


// Most of headers are already included;
// Can be removed;
#include <cstdint>
#include <unordered_map>
#include <stack>
#include <algorithm>

static const struct FreqStack {
    using SizeType = std::uint_fast32_t;
    FreqStack() {}
    std::unordered_map<SizeType, SizeType> frequencies;
    std::unordered_map<SizeType, std::stack<SizeType>> mapstack;
    SizeType max_fr = 0;

    const void push(const int x) {
        max_fr = std::max(max_fr, ++frequencies[x]);
        mapstack[frequencies[x]].push(x);
    }


    const int pop() {
        const auto top = mapstack[max_fr].top();
        mapstack[max_fr].pop();

        if (mapstack[frequencies[top]--].empty()) {
            --max_fr;
        }

        return top;
    }

};

参考资料

有关更多详细信息，请参阅 Discussion Board which you can find plenty of well-explained accepted solutions in there, with a variety of languages including efficient algorithms and asymptotic time/space complexity analysis^{1, 2}。

Answer 2

它不是上述答案中的参考 - 您需要参考才能实际更改 st.如果您不将 v 声明为引用，您最终只会在本地对 v 进行更改，而不是对 st.

使用 leetcode 中的示例，在所有推送之后，st[3] 应该有一个包含 [5] 的堆栈。在第一次弹出时，堆栈不为空，所以我们将其弹出。所以 st[3] 应该是一个空栈。然后在下一次 pop 中，v = st.begin() -> second 将 return 这个空堆栈，因此 pop / top 失败。这就是为什么评论 pop 行或使 v 不是参考在解决问题方面有效，但实际上并没有做任何明智的功能。

你需要做的是：弹出后，如果它是一个空堆栈，你需要delete/erase那个频率并从st开始堆栈。所以你的弹出代码看起来像这样

    stack<int>&v=st.begin()->second;
    
    int t=v.top();
    
    
    if(!v.empty()){
    v.pop();
    }

    if (v.empty()) {
        st.erase(st.begin());
    }
   
    return t;

我所做的唯一改变是将 else 变成 if。我更愿意在 v 不为空的情况下使用 t = v.top()，但由于我们在堆栈为空时删除频率，因此我们应该被覆盖（v 永远不应该为空）。那应该可以解决您的问题——但这不是 leetcode 问题的正确答案。我会让你自己想办法。

stack pop() 导致 "reference binding to misaligned address" 错误

stack pop() causes "reference binding to misaligned address" error

c++

stack

dictionary

vector

参考资料