奇怪的C ++链表错误

我在具有不同版本的GNU的不同机器上测试了此代码段,只有一台Clang 1001.0.46.3奇怪的Mac报告分段错误。在这段代码中是否存在地址问题或指针问题?

#include <iostream>
#include <vector>

using namespace std;

class Node
{
public:
    Node* next;
    int val;

};

class List
{
private:
    Node* head;
    Node* tail;
public:
    List()
    {
        head = tail = nullptr;
    }
    bool isEmpty()
    {
        if(!head && !tail) return true;
        return false;
    }
    void pushBack(int num)
    {
        Node* newNode = new Node;
        newNode->val = num;
        if(isEmpty()) head = tail = newNode;
        else
        {
            tail->next = newNode;
            tail = tail->next; 
        }
    }

    void pushFront(int num)
    {
        Node* newNode = new Node;
        newNode->val = num;
        if(isEmpty()) head = tail = newNode;
        else
        {
            Node* tmp = head;
            newNode->next = tmp;
            head = newNode;
        }
    }

    void popBack()
    {
        if(head == tail) {delete head; head = nullptr; return;}
        Node* tmp = head;
        while(tmp->next != tail) tmp = tmp->next;
        tail = tmp;
        delete tmp->next;
        tmp->next = nullptr;
    }

    void popFront()
    {
        if(head == tail) {delete head; head = nullptr; return;}
        Node* tmp = head;
        tmp = tmp->next;
        delete head;
        head = nullptr;
        head = tmp;
    }

    int findLen()
    {
        if(isEmpty()) return 0;
        int len = 0 ;   
        Node* tmp = head;
        while(tmp)
        {
            len++;
            //if(tmp == tail) break;
            tmp = tmp->next;
        }
        return len;
    }

    void inserter(int position,int num)
    {
        if(position > findLen() || isEmpty()) return;
        int index = 0;
        Node* tmp = head;
        Node* newNode = new Node;
        newNode->val = num;
        if(position == 0) {pushFront(num); return;}
        else if(position == findLen()) {pushBack(num); return;}
        while(tmp->next)
        {
            index++;
            if(index == position)
            {
                Node* tmp2 = tmp->next;
                tmp->next = newNode;
                newNode->next = tmp2;
                return;
            }   
            tmp = tmp->next;
        }
    }

    void print()
    {
        if(isEmpty()) return;
        cout << "list = ";
        Node* tmp = head;

        while(tmp)
        {
            cout << tmp->val << " ";
            if(tmp == tail) break;
            tmp = tmp->next;
        }
        cout << endl;
    }
};



int main()
{   
    cout << "delete added" << endl;
    List testList;
    testList.pushBack(5);
    testList.pushBack(10);
    testList.pushBack(15);
    testList.pushBack(20);                          // after this line,we got segmentation fault
    cout << "len = " << testList.findLen() << endl;
    testList.print();

    testList.pushFront(5);
    testList.pushFront(10);
    testList.pushFront(15);
    testList.pushFront(20);
    cout << "len = " << testList.findLen() << endl;
    testList.print();

    testList.inserter(0,8);
    cout << "len = " << testList.findLen() << endl;
    testList.print();

    testList.inserter(9,555);
    cout << "len = " << testList.findLen() << endl;
    testList.print();

    testList.inserter(5,333);
    cout << "len = " << testList.findLen() << endl;
    testList.print();

    cout << "popBack" << endl;
    testList.popBack();
    cout << "len = " << testList.findLen() << endl;
    testList.print();

    cout << "popFront" << endl;
    testList.popFront();
    cout << "len = " << testList.findLen() << endl;
    testList.print();

    cout << "popBack" << endl;
    testList.popBack();
    cout << "len = " << testList.findLen() << endl;
    testList.print();

    cout << "popFront" << endl;
    testList.popFront();
    cout << "len = " << testList.findLen() << endl;
    testList.print();

    return 0;
}

跟进:嘿,伙计们,我自己有一些线索。我认为问题应该出在操作系统方面。在检查了相关的汇编代码之后,我注意到,即使局部变量的默认初始化值为0,它们也不总是零。我认为问题应该出在操作系统的分页方案上。我将尽力弄清楚MacOS(内核10.15.1)和linux如何选择页面以及如何为局部变量生成随机值。如果有人知道这一领域或有任何线索可以解决,请随时告诉我。干杯。

qyrwj 回答:奇怪的C ++链表错误

您的问题是每个Node成员中的next成员都没有初始化。

取消注释您的评论行 //if(tmp == tail) break; 方法findLen中的方法也是一种解决方案。

解决此问题的正确方法是将Node类重写为

class Node
{
public:
    Node* next = nullptr;
    int val;

};

无论如何,我希望这只是家庭作业或锻炼,否则,请选择旧的std::list

,
  

我认为接下来默认情况下会将其初始化为nullptr。

默认情况下,仅静态存储被零初始化,并且即使没有任何显式的初始化程序也可以安全读取。

动态存储和自动存储可以并且确实可以容纳随机垃圾(在理论上和实际实现中都是如此)。

在实践中,前几个动态分配也可能会初始化为零,因为分配器必须从OS获取新页面。但是在删除了一些对象并分配了更多对象之后,您正在从空闲列表中回收内存。 (除非CRT启动代码已经在main的开头之前执行过此操作,否则在这种情况下,即使是第一个小分配也将获得脏内存。)

诸如valgrind之类的工具可以帮助识别读取未初始化的内存。

MSVC的调试模式对此也有一个有用的功能:它用可识别的有毒值memset(0xCC)填充“未初始化”变量,该值不是有效的指针,并且(如果作为x86机器代码执行)是int3指令:调试断点。并且在其他情况下(例如整数)也易于识别。

  

在检查了相关的汇编代码之后,我注意到,即使局部变量的默认初始化值为0,它们也不总是为零。我认为问题应该出在操作系统的分页方案上。

来自操作系统的新页面 始终为零,以避免在用户之间泄漏潜在的敏感信息。 (例如,以前用于读取/etc/shadow或ssh键内容的页面)。当new必须在幕后使用mmapbrk来获得更多内存时,或者第一次函数调用将RSP递减为新的值时,这适用页面。

通常,您没有得到一个新的页面,而是在重用一个已经分配的页面(通过空闲列表,或者通过重用以前的函数调用弄脏的内存用于堆栈)。除非您的函数是调用堆栈中最深的函数,否则请注意脏内存。

您的实验在未初始化变量中看到的大部分为零,这可能是您的程序所做的唯一一件事,因此这是调用堆栈第一次达到如此深的水平。

或者对于动态分配,空闲列表中可能没有脏内存,因此new必须从操作系统中获取新的虚拟页面。


页面的大小仅确定何时逻辑零堆栈和BSS物理归零以及具有何种粒度。

基于对另一个答案的评论,我认为您已经迷上了OS用来清零的机制。 “获取更多页面”这个概念是有意义的,对于动态存储而言,它很有用,但会使您感到困惑。

静态存储和堆栈空间具有固定的布局。函数调用的堆栈框架位于其父框架的正下方,并在返回时释放。调用堆栈是一个堆栈数据结构

所以重要的是,这是否是您进入堆栈中最深的时间?页面边界无关紧要。函数运行时不会弄脏整个页面的堆栈空间,只会弄脏它实际使用的内存。堆栈通常限于8 MiB之类,在CRT起始代码调用main时仅使用了4k页。因此,基本上,您将拥有零内存的8MiB数组的大部分作为堆栈空间。

本文链接:https://www.f2er.com/3111278.html

大家都在问