c++ - STL 列表实现-6ren

c++ - STL 列表实现

转载作者：太空宇宙更新时间：2023-11-04 15:03:11

<分区>

为了练习目的，我已经实现了一个 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() 函数中。谁能知道发生了什么事？提前致谢!

文章推荐： java - 无法让 JdbcTemplate 回滚

文章推荐： html - 将元素放入行中并在每行的开头和结尾对齐它们？

文章推荐： php - 将工具提示添加到 css 打印文件表

文章推荐： java - XML解析器java跳过dtd验证

STL - STL 的实际文档
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。我们不允许提问寻求书籍、工具、软件库等的推荐。您可以编辑问题，以便用事实和引用来回答。关闭 4 年前。
C++:STL 排序 STL 数组的 STL vector
以下 C++ 代码和 Makefile 产生了一个无法理解的编译错误(对我来说)。谁能解释一下问题到底是什么？修复此代码需要做什么？能举个例子吗？我在 Cygwin 的 GCC 上成功编译了这段
STL - 基于 STL 容器的范围
我大量使用 BOOST_FOREACH 来迭代容器，并且由于我最近转向 c++0x，我认为我可以用基于范围的替换 BOOST_FOREACH >for 构造。下面这段代码 #include #inc
STL - 自定义 STL 容器
我编写了代码，允许按照输入的顺序遍历映射数据。我编写了几次代码的解决方案是: 给定键类型 K 和数据类型 D，标准:: map std::向量如果想随机查找数据条目，请使用 map.find(K
c++ - STL 错误_没有_代码中的任何 STL
我在 cygwin 上使用 gcc 3.4.4。我在下面的代码中收到了这个相当令人费解的 STL 错误消息，它根本不使用 STL: #include using namespace std; con
STL - STL count_if 的标准谓词
我正在使用 STL 函数 count_if 来计算所有正值在 double vector 中。例如我的代码是这样的: vector Array(1,1.0) Array.push_back(-1.
STL - 如何从 numpy-STL 网格中提取顶点？
我正在尝试使用 numpy-STL 从 STL 模型中提取顶点以用于相干点漂移注册。你如何提取顶点？我了解如何从顶点和面列表创建网格，但不了解如何倒退。我试过:从顶点和面创建一个新网格。导入创建的网
STL - "home-brew"STL 性能？
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html 根据那篇文章，STL 不适合游戏开发。你对此有何看法？我目前的
STL - STL map::find 函数在没有相等运算符的情况下如何工作？
在幕后，STL 映射是一棵红黑树，它使用其键的 typename _Rb_tree::iterator _Rb_tree:: find(const _Key& __k) { iterator _
STL - C++ 开发人员必须具备哪一部分 STL 知识？
我对 C++ 有很好的了解，但从未深入研究 STL。我必须学习 STL 的哪一部分才能提高工作效率并减少工作中的缺陷？谢谢。最佳答案 I have good knowledge of C++ 恕我
c++ - STL 对输入与 STL 映射
map rollCallRegister; map :: iterator rollCallRegisterIter; pair , bool> returnPair; rollCallRegi
c++ - STL 概念是否涵盖了 STL 算法的所有参数要求？
在查看一些算法的模板名称时，我看到这个名字对应于一个图书馆的概念。取std::mismatch例如。 template std::pair mismatch( InputIt1 first1, I
C++ STL - STL sort() 的第三个参数如何工作？
我想对 class Person 的对象数组进行排序基于其数据成员' age '.我将对象存储在 vector v 中. 据我所知，至少有 4 种方法可以执行此操作，根据下面编写的方法，我有以下问题。
c++ - 什么时候应该使用编译器附带的 STL 以外的 STL？
我对 gcc 或 Visual Studio 打包之外的 STL 实现感到好奇，因此快速 Google 搜索出现了一些结果，例如: Apache stdcxx uSTL rdeSTL 在什么情况下应该
STL - 我可以在 DriverKit 驱动程序中使用 STL 吗？
我可以使用例如std::vector吗？在 macOs/XCode 的 DriverKit 驱动程序中？ DriverKit 有一些容器类，如 OSArray https://developer.ap
STL - D STL 容器 Phobos - 如何使用范围？
我找不到任何关于如何将范围与容器结合使用的好文档。我正在尝试使用给定的 .insertAfter() 函数将一个元素插入到 SList 中。它需要一个范围，但我不知道如何检索它。有人可以发布一两个示
c++ - 如何将聚合支持到 STL 或类似 STL 的库中
如何在(例如)STL 容器中引入聚合初始化支持以正确构造它们？我的意思是: struct A { int i; char c; }; std::list l; // empty l.insert(st
c++ - STL - 将值添加到存储在 STL 映射中的 vector
我有一个 STL map : std::map > my_map; 我有两个变量: string name; int age; 这些变量的值发生变化，但本质上我想要做的是: 如果键名不存在，则创建键名
c++ - 用于查找 STL 容器中间的 STL 样式函数
我是 C++ 的新手，请求帮助解决问题。我正在编写一个简单的 STL 样式函数，它应该返回序列的中间元素( vector 、列表等) 这是我的函数，我尝试使用迭代器的概念 template It
c++ - 如何按第一个 STL 列表的顺序对第二个 STL 列表进行排序
如果我将几个水果名称推回第一个STL列表，同时，我将每个水果的编号推回第二个STL列表；如果我想按字母顺序对第一个STL列表进行排序，我该如何按水果STL列表的顺序对第二个STL列表进行排序？最佳答

太空宇宙

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

c++ - STL 列表实现