c++ - STL 列表实现

标签 c++ c++11 stl deque

<分区>

为了练习目的，我已经实现了一个 C++ STL 列表(显然所有的构造函数和方法都没有)。大多数功能都正常工作。 

#ifndef list_H
#define list_H

#include <iostream>
#include <stdexcept>

template <typename T>
class list {
public:
    list <T> & operator = (const list<T> &);
    ~list();
    /* Modifiers */
    void push_back(T&& data);
    void push_back(T const& data);
    void push_front(T&& data);
    void push_front(T const& data);
    void pop_back();
    void pop_front();
    void swap(list &x);
    void clear();

    /* Iterators */
    typedef T* iterator;
    typedef T* const const_iterator;

    const_iterator begin() const; // cbegin
    iterator begin();

    const_iterator end() const; //cend()
    iterator end();

    const_iterator rbegin() const;
    iterator rbegin();

    const_iterator rend() const;
    iterator rend();

    /* Capacity */
    size_t size() const;
    bool empty() const;

    /* Element Access */
    T& front();
    T const& front() const;

    T& back();
    T const& back() const;

    T& at(T const indx);
    T const& at(T const indx) const;

    T& operator[] (T const indx);
    T const& operator[] (T const indx) const;

private:
    struct node {
        int data;
        node *next, *prev;
        node(T const& data, node* next, node* prev)
            : data(data)
            , next(next)
            , prev(prev) {
        }
        node(T&& data, node* next, node* prev)
            : data(std::move(data))
            , next(next)
            , prev(prev) {
        }
    };
    int elements = 0;
    node *head = nullptr;
    node *tail = nullptr;
};

template <typename T>
list <T> & list<T>::operator = (const list<T> & that) {
    node* tmp = head;
    while(head) {
        tmp = head;
        head = head->next;
        delete tmp;
    }
    elements = that.elements;
    head = that.head;
    tail = that.tail;
}

template <typename T>
list <T>::~list() {
    node* tmp;
    while(head) {
        tmp = head;
        head = head->next;
        delete tmp;
    }
}


template <typename T>
T& list<T>:: front() {
    if(head == nullptr)
        throw std::runtime_error("Invalid Action!");
    return head->data;
}

template <typename T>
T const& list<T>:: front() const {
    if(head == nullptr)
        throw std::runtime_error("Invalid Action!");
    return head->data;
}

template <typename T>
T& list<T>:: back() {
    if(tail == nullptr)
        throw std::runtime_error("Invalid Action!");
    return tail->data;
}

template <typename T>
T const& list<T>:: back() const {
    if(tail == nullptr)
        throw std::runtime_error("Invalid Action!");
    return tail->data;
}

template <typename T>
void list<T>::push_back(T const& data) {
    node* newNode = new node(data, nullptr, tail);
    if(head == nullptr)
        head = newNode;
    if(tail != nullptr)
        tail->next = newNode;
    tail = newNode;
    ++elements;
}

template <typename T>
void list<T>::push_back(T&& data) {
    node* newNode = new node(std::move(data), nullptr, tail);
    if(head == nullptr)
        head = newNode;
    if(tail != nullptr)
        tail->next = newNode;
    tail = newNode;
    ++elements;
}

template <typename T>
void list<T>::push_front(T const& data) {
    node* newNode = new node(data, head, nullptr);
    if(tail == nullptr)
        tail = newNode;
    if(head != nullptr)
        head->prev = newNode;
    head = newNode;
    ++elements;
}

template <typename T>
void list<T>::push_front(T&& data) {
    node* newNode = new node(data, head, nullptr);
    if(tail == nullptr)
        tail = newNode;
    if(head != nullptr)
        head->prev = newNode;
    head = newNode;
    ++elements;
}

template <typename T>
void list<T>::pop_front() {
    if(head == nullptr)
        throw std::runtime_error("Invalid Action");
    node *tmp = head;
    head = head->next;
    if(head != nullptr)
        head->prev = nullptr;
    --elements;
    delete tmp;
}

template <typename T>
void list<T>::pop_back() {
    if(tail == nullptr)
        throw std::runtime_error("Invalid Action");
    node *tmp = tail;
    tail = tail->prev;
    if(tail != nullptr)
        tail->next = nullptr;
    --elements;
    delete tmp;
}

template <typename T>
bool list<T>::empty() const {
    return head == nullptr;
}

template <typename T>
size_t list<T>::size() const {
    return elements;
}

template <typename T>
T& list<T>::operator[] (T const indx) {
    int cont = 0;
    node *curr = head;
    while(curr) {
        if(cont == indx)
            return curr->data;
        curr = curr->next;
        ++cont;
    }
    return nullptr;
}

template <typename T>
T const& list<T>::operator[] (T const indx) const {
    int cont = 0;
    node *curr = head;
    while(curr) {
        if(cont == indx)
            return curr->data;
        curr = curr->next;
        ++cont;
    }
    return nullptr;
}

template <typename T>
T& list<T>::at(T const indx) {
    int cont = 0;
    node *curr = head;
    while(curr) {
        if(cont == indx)
            return curr->data;
        curr = curr->next;
    }
    return nullptr;
}

template <typename T>
T const& list<T>::at(T const indx) const {
    int cont = 0;
    node *curr = head;
    while(curr) {
        if(cont == indx)
            return curr->data;
        curr = curr->next;
    }
    return nullptr;
}

template <typename T>
typename list<T>::const_iterator list<T>::begin() const {
    return head;
}

template <typename T>
typename list<T>::iterator list<T>::begin() {
    return head;
}


template <typename T>
typename list<T>::const_iterator list<T>::end() const {
    return tail;
}

template <typename T>
typename list<T>::const_iterator list<T>::rbegin() const {
    return tail;
}
template <typename T>
typename list<T>::iterator list<T>::rbegin() {
    return tail;
}
template <typename T>
typename list<T>::const_iterator list<T>::rend() const {
    return head;
}

template <typename T>
typename list<T>::iterator list<T>::rend() {
    return head;
}

template <typename T>
typename list<T>::iterator list<T>::end() {
    return tail;
}

template <typename T>
void list<T>::swap(list &that) {
    std::swap(head, that.head);
    std::swap(tail, that.tail);
    std::swap(elements, that.elements);
}

template <typename T>
void list<T>::clear() {
    node* curr = head;
    while(head) {
        curr = head;
        head = head->next;
        delete curr;
    }
    head = tail = nullptr;
    elements = 0;
}

#endif // list_H

然后我通过以下方式测试了这个程序:

int main(void) {
    deque<int> dq;
    dq.push_back(1);
    dq.push_back(2);
    dq.push_back(3);
    while(!dq.empty()) {
        int value = dq.back();
        std::cout << value << std::endl;
        dq.pop_back();
    }
    return 0;
}

嗯，输出是:

3
2 
1

但程序没有在我的代码:: block 中终止。

然后我用Ideone编译，输出是:

3
2
1
    *** Error in `./prog': double free or corruption (fasttop): 0x08923008 ***
    ======= Backtrace: =========
    /lib/i386-linux-gnu/i686/cmov/libc.so.6(+0x75e72)[0xb75f8e72]
    /lib/i386-linux-gnu/i686/cmov/libc.so.6(+0x76bb0)[0xb75f9bb0]
    /usr/lib/i386-linux-gnu/libstdc++.so.6(_ZdlPv+0x1f)[0xb77db82f]
    ./prog[0x8048a17]
    /lib/i386-linux-gnu/i686/cmov/libc.so.6(__libc_start_main+0xf5)[0xb759c8f5]
    ./prog[0x8048b41]
    ======= Memory map: ========
    08048000-08049000 r-xp 00000000 09:03 16269491   /home/TKjJyD/prog
    08049000-0804a000 rw-p 00001000 09:03 16269491   /home/TKjJyD/prog
    08923000-08944000 rw-p 00000000 00:00 0          [heap]
    b7581000-b7583000 rw-p 00000000 00:00 0 
    b7583000-b772c000 r-xp 00000000 09:03 16394299   /lib/i386-linux-gnu/i686/cmov/libc-2.17.so
    b772c000-b772d000 ---p 001a9000 09:03 16394299   /lib/i386-linux-gnu/i686/cmov/libc-2.17.so
    b772d000-b772f000 r--p 001a9000 09:03 16394299   /lib/i386-linux-gnu/i686/cmov/libc-2.17.so
    b772f000-b7730000 rw-p 001ab000 09:03 16394299   /lib/i386-linux-gnu/i686/cmov/libc-2.17.so
    b7730000-b7733000 rw-p 00000000 00:00 0 
    b7733000-b774e000 r-xp 00000000 09:03 16394343   /lib/i386-linux-gnu/libgcc_s.so.1
    b774e000-b774f000 rw-p 0001a000 09:03 16394343   /lib/i386-linux-gnu/libgcc_s.so.1
    b774f000-b7750000 rw-p 00000000 00:00 0 
    b7750000-b7791000 r-xp 00000000 09:03 16394296   /lib/i386-linux-gnu/i686/cmov/libm-2.17.so
    b7791000-b7792000 r--p 00040000 09:03 16394296   /lib/i386-linux-gnu/i686/cmov/libm-2.17.so
    b7792000-b7793000 rw-p 00041000 09:03 16394296   /lib/i386-linux-gnu/i686/cmov/libm-2.17.so
    b7793000-b786f000 r-xp 00000000 09:03 16679929   /usr/lib/i386-linux-gnu/libstdc++.so.6.0.18
    b786f000-b7870000 ---p 000dc000 09:03 16679929   /usr/lib/i386-linux-gnu/libstdc++.so.6.0.18
    b7870000-b7874000 r--p 000dc000 09:03 16679929   /usr/lib/i386-linux-gnu/libstdc++.so.6.0.18
    b7874000-b7875000 rw-p 000e0000 09:03 16679929   /usr/lib/i386-linux-gnu/libstdc++.so.6.0.18
    b7875000-b787c000 rw-p 00000000 00:00 0 
    b787e000-b7882000 rw-p 00000000 00:00 0 
    b7882000-b7883000 r-xp 00000000 00:00 0          [vdso]
    b7883000-b78a2000 r-xp 00000000 09:03 16394256   /lib/i386-linux-gnu/ld-2.17.so
    b78a2000-b78a3000 r--p 0001f000 09:03 16394256   /lib/i386-linux-gnu/ld-2.17.so
    b78a3000-b78a4000 rw-p 00020000 09:03 16394256   /lib/i386-linux-gnu/ld-2.17.so
    bfa1b000-bfa3c000 rw-p 00000000 00:00 0          [stack]

我认为问题出在 pop_back() 函数中。谁能知道发生了什么事？ 提前致谢!

最佳答案

pop_back 如果列表为空，则需要使 head 无效；否则，析构函数将使用悬挂的 head 指针尝试删除已删除的节点。

赋值运算符也有一个问题:它对另一个列表的指针进行“浅拷贝”，因此两个列表会认为它们拥有(并尝试删除)相同的节点。

(此外，这比 deque 更接近 list。deque 应该允许在恒定时间内进行随机访问；链表实现不允许这样做.)

关于c++ - STL 列表实现，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25486668/

上一篇：c++ - 如果 unique_lock 管理的互斥量被销毁怎么办？

下一篇：c++ - 关于 shared_ptr 我不明白的事情

相关文章：

c++ - 如何将部分流作为参数传递？

c++ - 如何在 x86-64 上优化 C 和 C++ 中的函数返回值？

c++ - 如何使用 lambda 作为 std::unique_ptr 的删除器？

c++ - vector 中对象的内存分配

c++ - vector 的小字符串优化？

c++ - 类内枚举前向声明是否可能？

c++ - 让 VS2013、DirectXMath、XAudio2 和 D3D11 一起针对 Windows 7 工作

c++ - 部分模板参数应用程序的部分模板特化不适用于 GCC 4.8.1

c++ - 使用显式构造函数返回不可复制的不可移动对象

c++ - 是否可以使用符合 C++17 的 C++14 创建迭代器？

©2024 IT工具网  联系我们