为什么最后一个 SPLIT 函数会导致 SEGMENTATION FAULT？如何解决这个问题

Question

我写了循环缓冲区双向链表的典型程序（这里：RING）。我正在使用迭代器（我必须，学校项目）。

似乎一切正常，但内存有问题，我找不到以某种方式修复它的方法。分段错误的原因可能是我正在访问 "forbidden" 部分。

全码HERE

问题是我找不到应该修复的地方。

函数拆分：从原来的循环缓冲区制作了两个独立的循环缓冲区。

对于第一个，我从第一个位置开始迭代，对于第二个，我从第二个位置开始迭代。 DIR 表示顺时针（如果为真），否则为假。 LEN表示我们要获取的RING的长度。我们迭代每个第二个元素。

在截取的代码中你得到了真实的例子。

/******* external function ********/
/****** Example of the split function:
split (r3,r1,true,3,r2,false,6)
r3= 1,2,3,4,5
r1= 1,3,5
r2= 2,5,3,1,4,2
********/

template <typename Key>
Ring<Key> split(const Ring<Key> &source,Ring<Key> &result1, bool dir1, int len1, Ring<Key> &result2, bool dir2, int len2){

typename Ring<Key>::iterator i1 = source.begin();
typename Ring<Key>::iterator i2 = source.begin();
/*I moved second iterator to the 2nd position in original Ring*/
i2++;


if (source.isEmpty()){
    cout<<"Empty source Ring"<<endl;}

if (source.length()==1||source.length()==2){
    return source;
        }

if((len1 <= 0) || (len2 <= 0))
{
    cout << "split():(incorrect lengths)" << endl;
}

    if(!i1.isNULL()){
        for(int i = 0; i < len1; i++)
        {
            result1.insertLast(i1.getKey());
            if(dir1){
                i1++;
                i1++;;
                }
            else
                {i1--;
                i1--;
                }}}
cout<<result1;

    if(!i2.isNULL()){
        for(int i = 0; i < len2; i++)
        {
            result2.insertLast(i2.getKey());
           if(dir2){
                i2++;
                i2++;
                }
            else
                {i2--;
                i2--;
                }}}
cout<<result2;}

Answer 1

我在这里分叉了你的代码：https://ideone.com/7af6D7

更正了一些位。看起来它不再出现段错误，但我不知道它是否按照您的预期进行。阅读评论中的注释。您还应该指定您使用的是 C++11 或更高版本还是旧的 C++ 代码（如果是这样，我很抱歉）

这至少应该被编译器以警告的形式捕获（您应该使用 -Werror 标志进行编译）。

此外，请正确缩进您的代码。

无论如何，我不知道你为什么要 return 在拆分函数上复制整个源代码（它应该 return void 和 throw 错误或bool).

#include <iostream>
#include <stdlib.h>

using namespace std;

template <typename Key>
class Ring
{
    struct Node
    {
        Key key;
        Node *next= nullptr; // Always initialize. Worst case if you do it 
                             // twice: the compiler will be smart enough to 
                             // remove one of the occurrences
        Node *prev= nullptr; // Ditto
    };
    Node *any= nullptr; // Use nullptr on C++11 and onwards
    // Also, any is not a very good name, prefer using root or first

public:

/******* iterator class methods definitions ********/
    class iterator
    {
        Node *el= nullptr; // Ditto
    public:
        iterator()= default; // or iterator() {}
        ~iterator()= default; // or ~iterator() {}

        constexpr iterator(const iterator& copyIter)
        : el(copyIter.el)
        {
            // Empty constructor gets to be constexpr
            // Improves optimizing and can be evaluated at runtime
        }

        constexpr iterator(Node *copyEl)
        : el(copyEl)
        {
        }

        iterator &operator = (const iterator &copyIter)
        {
            el = copyIter.el;
            return *this;
        }

        bool operator == (const iterator &comp) const
        {
            return el == comp.el;
        }

        bool operator != (const iterator &comp) const
        {
            return el != comp.el;
        }

        /* I don't think this operator is good practice
        iterator operator + (const unsigned int number) const
        {
            iterator new_iter = *this; // Could be auto new_iter = *this in C++11
            for(int i = 0; i < number; i++) { // Style: Always put brackets
                new_iter++;
            }
            return new_iter;
        }*/

        iterator& operator ++ ()
        {
            if (el) {
                el = el->next;
            }
            return *this;
            // You had no return if it's null
            // Also, no need for != nullptr or != NULL
            // Usually, you return a reference to self
        }

        iterator operator ++ (int)
        {
            iterator copy_iter(el);
            if (el) {
                el = el->next;
            }
            return copy_iter; // You return the copy, no matter what
        }

        /* Ditto
        iterator operator - (const unsigned int number) const
        {
            iterator new_iter = *this;
            for(int i = 0; i < number; i++) {
                new_iter--;
            }
            return new_iter;
        }*/

        iterator& operator --()
        {
            if (el) {
                el = el->prev;
            }
            return *this;
        }

        iterator operator -- (int)
        {
            iterator copy_iter(el);
            if (el) {
                el= el->prev;
            }
            return copy_iter;
        }

        Key getKey() const
        {
            if (el) {
                return el->key;
            }
            cerr << "getKey(): (iterator = NULL)" << endl;
            return Key(); // Empty element, might aswell throw here
        }

        bool isNULL() const
        {
            return !el;
        }

        operator bool() const
        {
            return !isNULL();
        }
    };

/******* methods ********/
    Ring();
    ~Ring();
    Ring(const Ring<Key> &Ring);
    friend ostream &operator << (ostream &o, const Ring<Key> &Ring){Ring.print(); return o;};
    bool operator ==(const Ring<Key> &Ring);
    bool operator != (const Ring<Key> &Ring);
    Ring<Key> &operator = (const Ring<Key> &Ring);
    Ring<Key> operator + (const Ring<Key> &second)const;
    Ring<Key> operator - (const Ring<Key> &second)const;
    bool insertFront(const Key &key);
    bool insertLast(const Key &key);
    bool insertAt(int pos, const Key &key);
    bool insertAfter(const Key &where, const Key &key);
    bool popByKey(const Key &key);
    bool popLast();
    bool popFront();
    bool ifExists(const Key &key);
    bool isEmpty()const;
    int length()const;
    void print()const;
    bool clear();
    void reverse();

/******* additional iterators definitions *******/
    iterator begin() const
    {
        return iterator(any);
    }

    iterator end() const
    {
        return iterator(any? any->prev : nullptr); // Always check before dereference
    }
};

/******* methods definitions ********/
template <typename Key>
Ring<Key>::Ring()
// : any(nullptr) // Prefer initializers. No need anyway because we did any= nullptr
{
    cout << "Constructor: (Empty Ring created)" << endl;
}

template <typename Key>
Ring<Key>::~Ring()
{
    if (!any) {
        cout << "Destructor: ( Ring deleted )" << endl;
    }
    Node *curr = any; // auto
    if (curr) {
        while(any) {
            this->popLast();
        }
        cout << "Destructor: ( Ring deleted )" << endl;
    }
}

template <typename Key>
Ring<Key>::Ring(const Ring<Key> &ring) // Please be consistent. If you're using 
// capital letters for classes, dont call the variable Ring; it should be ring
// : any(nullptr) // Prefer initializers. No need anyway because we did any= nullptr
{
    if (ring.any) {
        Node *curr = ring.any;
        do {
            this->insertLast(curr->key);
            curr = curr->next;
        } while(curr != ring.any);
    }
}

template <typename Key>
bool Ring<Key>::popLast()
{
    if (!any) {
        return true;
    }
    Node *curr = any;
    if (curr->next == curr) { // one Node
        any = NULL;
        delete curr; // Here is where you "hope" no one copied your class
                     // because you're deleting a pointer that other might be
                     // using, that's what's called a dangling pointer
        return true;
    }
    if(curr->next->next == curr) // two Nodes
    {
        Node *temp = curr->next;
        curr->next = curr;
        curr->prev = curr;
        delete temp;
        return true;
    }
    do
    {
        if(curr->next->next == any) // Last Node
        {
            Node *temp = curr->next;
            temp->next->prev = curr;
            curr->next = temp->next;
            delete temp;
            return true;
        }
        curr = curr->next;
    }
    while(curr != any);
    return false;
}

template <typename Key>
bool Ring<Key>::insertFront(const Key &key)
{
    Node *newNode = new Node; // Either way
    newNode->key = key; // Always set the key

    if (!any) { // Empty
        newNode->next = newNode;
        newNode->prev = newNode;
        any = newNode;
    } else {
        newNode->next= any; // Will be always before the "any"
        newNode->prev= any->prev; // Will always steal any's previous
        any->prev= newNode;  // Any will always point at newNode as previous
        any= newNode; // I'm the captain now
        // Actually, for the above, We don't care if it's only one or more      
    }
    return true;
}

template <typename Key>
bool Ring<Key>::operator == (const Ring<Key> &ring)
{
    if (this->isEmpty() && ring.isEmpty()) {
        return true;
    }
    if (this->length() != ring.length()) {
        return false;
    }
    Node *curr1 = this->any;
    Node *curr2 = ring.any;
    do {
        if (curr1->key != curr2->key) {
            return false;
        }
        curr1 = curr1->next;
        curr2 = curr2->next;
        // No null check needed for non empty rings
    } while(curr1 != this->any);
    return true;
}

template <typename Key>
bool Ring<Key>::insertLast(const Key &key)
{
    if (!any) {  // no elements
        this->insertFront(key);
        return true;
    }
    Node *newNode = new Node;
    newNode->key = key;
    newNode->next = any;
    Node* curr = any;
    do {
        if (curr->next == any) {
            newNode->prev = curr;
            any->prev = newNode;
            curr->next = newNode;
            return true;
        }
        curr= curr->next;
    } while(curr != any);
    return false;
}

template<typename Key>
bool Ring<Key>::isEmpty() const
{
    // return !any;
    if (!any) {
        cout << "isEmpty(): (Ring empty)" << endl;
        return true;
    }
    return false;
}

template <typename Key>
int Ring<Key>::length() const
{
    int count = 0;
    Node *curr = any;
    if (!curr) {
        return count;
    }
    do {
        count++;
        curr = curr->next;
    } while(curr != any);
    return count;
}

template<typename Key>
void Ring<Key>::print() const
{
    Node * curr = any;
    if(!curr) {
        cout << "print(): (Ring empty)" << endl;
        return;
    }
    do {
        cout << "\t(" << curr->key<< ")";
        curr = curr->next;
    } while(curr != any);
    cout << endl;
}

/******* external function ********/
/****** Example of the split function:
split (r3,r1,true,3,r2,false,6)
r3= 1,2,3,4,5
r1= 1,3,5
r2= 2,5,3,1,4,2
********/

template <typename Key>
Ring<Key> split(const Ring<Key> &source, Ring<Key> &result1, bool dir1, 
                int len1, Ring<Key> &result2, bool dir2, int len2)
{
    if (source.isEmpty()) {
        cout<<"Empty source Ring"<<endl;
        return source;
    }

    if (source.length()==1 || source.length()==2) {
        return source;
    }

    if (len1 <= 0 || len2 <= 0) {
        cout << "split():(incorrect lengths)" << endl;
        return source;
    }

    auto i1 = source.begin(); // typename Ring<Key>::iterator i1 = source.begin()
    auto i2 = source.begin(); // typename Ring<Key>::iterator 21 = source.begin()

    /* I moved second iterator to the 2nd position in original Ring */
    ++i2; // Prefer ++i to i++

    if (i1) {
        for (int i= 0; i < len1; ++i) {
            result1.insertLast(i1.getKey());
            if(dir1) {
                ++i1;
                ++i1;
            } else {
                --i1;
                --i1;
            }
        }
    }
    cout << result1;

    if (i2) {
        for(int i = 0; i < len2; ++i) {
            result2.insertLast(i2.getKey());
            if(dir2) {
                ++i2;
                ++i2;
            } else {
                --i2;
                --i2;
            }
        }
    }

    cout << result2;

    return source; // You *ALWAYS* need to return a value. 
    // This was causing the SEGFAULT (and others like this might also)
}

int main()
{
    Ring<int> R1,R2,R3,R4,R5;

    R1.insertLast(2);
    R1.insertLast(3);
    R1.insertLast(4);
    R1.insertLast(5);
    R1.insertLast(6);
    R1.insertLast(1);

    R2.insertLast(10);
    R2.insertLast(20);
    R2.insertLast(30);
    R2.insertLast(40);
    R2.insertLast(50);
    R2.insertLast(60);
    R2.insertLast(70);

    cout<<"Split function:"<<endl;
    split(R1,R3,false,3,R4,false,6);

    R5.insertLast(10);
    R5.insertLast(20);
    R5.insertLast(30);
    R5.insertLast(50);
    R5.insertLast(50);
    R5.insertLast(60);
    R5.insertLast(70);

    R5.print();

    cout << __FILE__ << ':' << __LINE__ << " I'm alive (no segfault)" << endl;

    return 0;
}

为什么最后一个 SPLIT 函数会导致 SEGMENTATION FAULT？如何解决这个问题

Why the last SPLIT function causes SEGMENTATION FAULT? How to fix this

c++

segmentation-fault

doubly-linked-list