单联杂货单

Question

对于我自己的链接列表实现，我决定尝试一些不同的东西:食品杂货的链接列表。

这种实现与标准清单之间的主要区别是：

1. 更多的数据字段(名称、数量，如果项目已经购买)
2. 两个大小的数据成员(不同项和总项)
3. 根据要删除的数量，可能不会删除整个节点。

我没有什么特别的顾虑，我想对此作一个全面的回顾。

我已经用艾德龙上的一些测试用例测试了这一点。

GroceryList.hpp

#ifndef GROCERY_LIST_HPP
#define GROCERY_LIST_HPP

#include <cstddef>
#include <string>

class LinkedGroceryList
{
private:
    struct Grocery
    {
        std::string name;
        std::size_t quantity;
        bool purchased;
        Grocery* next;
    };

    Grocery* head;
    std::size_t differentGroceries;
    std::size_t totalGroceries;

public:
    LinkedGroceryList();
    ~LinkedGroceryList();
    void addGrocery(std::string const&, std::size_t);
    void removeGrocery(std::string const&, unsigned int);
    bool findGrocery(std::string const&) const;
    void markAsPurchased(std::string const&);
    void displayGroceries() const;
    void clearGroceries();
    std::size_t different() const { return differentGroceries; }
    std::size_t total() const { return totalGroceries; }
    bool empty() const { return differentGroceries == 0; }
};

#endif

GroceryList.cpp

#include "GroceryList.hpp"
#include <iostream>

LinkedGroceryList::LinkedGroceryList()
    : head(nullptr)
    , differentGroceries(0)
    , totalGroceries(0)
{}

LinkedGroceryList::~LinkedGroceryList()
{
    clearGroceries();
}

void LinkedGroceryList::addGrocery(std::string const& name, std::size_t quantity)
{
    Grocery* newGrocery = new Grocery;

    newGrocery->name = name;
    newGrocery->quantity = quantity;
    newGrocery->purchased = false;

    newGrocery->next = nullptr;

    if (!head)
    {
        head = newGrocery;
    }
    else
    {
        Grocery* groceryPtr = head;

        while (groceryPtr->next)
            groceryPtr = groceryPtr->next;

        groceryPtr->next = newGrocery;
    }

    differentGroceries++;
    totalGroceries += quantity;
}

void LinkedGroceryList::removeGrocery(std::string const& name, unsigned int quantity)
{
    if (!head) return;

    Grocery* groceryPtr;

    if (head->name == name)
    {
        groceryPtr = head;
        head = groceryPtr->next;

        totalGroceries -= quantity;
        if (quantity == groceryPtr->quantity)
            differentGroceries--;
        else
        {
            groceryPtr->quantity -= quantity;
            return;
        }

        delete groceryPtr;
    }
    else
    {
        Grocery* predPtr = nullptr;
        groceryPtr = head;

        while (groceryPtr && groceryPtr->name != name)
        {
            predPtr = groceryPtr;
            groceryPtr = groceryPtr->next;
        }

        if (groceryPtr)
        {
            totalGroceries -= quantity;
            if (quantity == groceryPtr->quantity)
                differentGroceries--;
            else
            {
                groceryPtr->quantity -= quantity;
                return;
            }

            predPtr->next = groceryPtr->next;
            delete groceryPtr;
        }
    }
}

bool LinkedGroceryList::findGrocery(std::string const& name) const
{
    if (!head) return false;

    if (head->name == name)
        return true;
    else
    {
        Grocery* groceryPtr = head->next;

        while (groceryPtr)
        {
            if (groceryPtr->name == name)
            return true;

            groceryPtr = groceryPtr->next;
        }
    }

    return false;
}

void LinkedGroceryList::markAsPurchased(std::string const& name)
{
    Grocery* groceryPtr = head;

    while (groceryPtr)
    {
        if (groceryPtr->name == name)
        groceryPtr->purchased = true;

        groceryPtr = groceryPtr->next;
    }
}

void LinkedGroceryList::displayGroceries() const
{
    if (!head) return;

    Grocery* groceryPtr = head;

    while (groceryPtr)
    {
        std::cout << groceryPtr->name << ", ";
        std::cout << groceryPtr->quantity << ", ";
        std::cout << ((groceryPtr->purchased) ? "purchased\n" : "not purchased\n");
        groceryPtr = groceryPtr->next;
    }
}

void LinkedGroceryList::clearGroceries()
{
    if (!head) return;

    Grocery* predPtr = head;
    Grocery* nextGrocery;

    while (predPtr)
    {
        nextGrocery = predPtr->next;
        delete predPtr;
        predPtr = nextGrocery;
    }

    head = nullptr;
    differentGroceries = 0;
    totalGroceries = 0;
}

驱动程序

#include "GroceryList.hpp"
#include <iostream>

int main()
{
    LinkedGroceryList meats;
    meats.addGrocery("steak", 5);
    meats.addGrocery("chicken", 3);
    meats.addGrocery("pork", 2);

    meats.displayGroceries();
    std::cout << "\nDifferent items: " << meats.different() << "\n";
    std::cout << "Total items: " << meats.total();
    std::cout << "\nsteak present? " << std::boolalpha << meats.findGrocery("steak");
    std::cout << "\ncarrots present? " << std::boolalpha << meats.findGrocery("carrots");

    std::cout << "\n\nRemoving 1 pork...\n\n";
    meats.removeGrocery("pork", 1);

    meats.displayGroceries();
    std::cout << "\nDifferent items: " << meats.different() << "\n";
    std::cout << "Total items: " << meats.total();
    std::cout << "\npork present? " << std::boolalpha << meats.findGrocery("pork");

    meats.markAsPurchased("steak");
    std::cout << "\n\nsteak has been purchased\n\n";
    meats.displayGroceries();
}

Answer 1

与其在名称和数量上传递用户，不如让用户传递一个Grocery。通过让用户提供组件而不是对象，可以完全消除任何封装感。

而不是displayGroceries，我会给ostreams过载operator>>。

给Grocery一个构造函数，这样您就可以将创建代码压缩为一个简洁的一行，而不是六个任务。(而且构造函数可以更高效，因为您可以避免使用属性的默认构造，只需立即将它们分配给它们。)

假设您没有编写这段代码，并考虑以下几点：

void addGrocery(std::string const&, std::size_t);

世界上的参数是什么？一个字符串和一个size_t。好吧..。也许是名字和数量？也许是以美分为单位的名字和费用？也许是这个物品的名字和走道？给出你的公开声明有意义的名字！

(请注意，这是一个非常好的例子，说明了在Grocerys上工作的原因，而不是string/size_t对。

要么保留一个尾指针，要么在列表的顶部插入。addGrocery不应该是线性时间。这违背了链接列表的目的。

对于简单的循环条件，我更喜欢for循环：

for (Grocery* grocery = head; grocery; grocery = grocery->next) {
    // ...
}

不需要阅读整个while就可以更容易地看到正在发生的事情

当head为null时，您已经用了不必要的特殊情况来处理复杂的一些循环。只是让一个for不循环是null：

bool LinkedGroceryList::findGrocery(std::string const& name) const
{

    for (auto node = head; node; node = node->next) {
        if (head->name == name) {
            return true;
        }
    }
    return false;
}

使用名称进行线性搜索的方式意味着您使用了错误的数据结构。任何时候，当你在一个键上搜索一个或多个项目时，你都需要一张地图(或者一对多的多个多个的多个)。

您的differentGroceries和totalGroceries名称有点混乱。我会考虑将它们称为numGroceries和quantitySum (方法名称有类似的更改)。

Answer 2

您需要考虑三条规则。

也就是说:默认的副本和赋值实现将不像您所希望的那样处理head。您需要正确地定义它们，或者隐藏它们(或者在C++ 11中删除它们)。

例如：

class LinkedGroceryList
{
private:
    LinkedGroceryList(const LinkedGroceryList& other);
public:
// etc...
};

关于大小的名称，我同意@Corbin，但我会考虑使用size()来保存列表的长度，即differentGroceries来模仿标准库。同样，clear而不是clearGroceries，因为元素类型在容器名称中是隐式的。

类似地(有些人不同意)，我更喜欢findGrocery而不是findGroceryByName。这不仅应该返回一个bool，而且理想的情况下是一个迭代器与杂货一起返回元素。或者，重命名为containsGroceryWithName或containsGrocery。

还考虑了不变量的一些检验。例如，differentGroceries == 0 <=> head == nullptr。

在方法markAsPurchased中，您应该从匹配的循环中分离出来。我还会返回bool，表示找到匹配的成功。

为什么add取size_t而remove取unsigned？

在remove方法中，对于head情况: 1.重新分配头部，而不考虑是否删除了所有的项。2.你应该检查是否有一个或多个负数的项目成为一个下流。3.头和主箱有共同的代码，应采用一种共同的方法。

在add方法中，需要检查列表是否已经包含具有该名称的项。事实上，这里有一个更大的问题。如果您合并项目时添加的同名，您将失去什么是购买的跟踪。如果你不这样做，你就会有更多的复杂性是remove。对于可能购买或不购买的物品，remove意味着什么？

我认为这意味着purchased不是bool，而是已购买的具有给定密钥的项目数量的计数。可以(但不一定需要)更新markAsPurchased方法，以指定购买的项目数量。

Answer 3

首先，我要使代码更加通用：

template <class T>
class LinkedList {

然后，我可能会将用户的数据(存储的内容)与“您的”数据(列表本身使用的链接)分开：

    class Node {
        T user_data;
        Node *next;

然后，我将为Node创建一个构造函数，它以一个(对常量的引用) T作为参数，并创建一个保存该数据的节点：

Node(T const &data, Node *next = nullptr) : user_data(data), next(next) {}

为了遵循现代的“五的规则”，我们可能需要一个move构造函数：

Node (T &&data, Node *next = nullptr) : user_data(data), next(next) {}

这将允许我们在/如果不再使用现有数据项时“窃取它的内脏”。取决于数据项包含的内容，这可能是一个重大的胜利。它可能也不是，但实现它是相当容易的(至少在本例中)，所以它可能是值得的，尽管它是否会做很多(如果有的话)真正的好处。

不过，这(当然)只适用于C++11。如果您使用的是旧的编译器，您必须在没有rvalue引用的情况下生活(或者更新编译器)。

在我们讨论C++11时，还有一个需要考虑的变化:与其单独管理内存，不如至少考虑使用std::unique_ptr来帮助我们，因此Node变成了：

template <class T>
class Node {
    T user_data;
    std::unique_ptr<Node> next;
};

为了做到这一点，我们希望使用std::make_unique ( C++11无意中遗漏了它，但它将在C++14中)。简化(但足以满足此目的)版本如下所示：

template<typename T, typename... Args>
std::unique_ptr<T> make_unique(Args&&... args)
{
    return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
}

我们使用它为我们创建一个节点，当节点不再需要时，std::unique_ptr会自动删除它(即，当指向该节点的unique_ptr被销毁时)。

Grocery* head;

当然，这也应该是一个unique_ptr。视情况而定，它可能是一个shared_ptr，但在任何情况下几乎肯定不应该是一个“原始”指针。

std::size_t differentGroceries;
std::size_t totalGroceries;

至少在我看来，在运行的基础上保持项目总数可能是毫无意义的。在我去购物的次数中，我不记得上次我想知道我买了多少东西(或打算买多少东西)。

但是，我同意Corbin的观点，您在这里有一个更根本的问题:您正在尝试实现一个set，而链接列表实际上并不是一个非常适合该任务的结构。

关于实现已经说了很多，所以我只想在其他的评论中讲几个我没有注意到的问题。

让我印象深刻的一点是，findGrocery、markAsPurchased和displayGroceries在本质上都有相同的代码来遍历列表。我更希望看到一个函数遍历列表，并将一些函数应用于节点，然后(可能基于其返回值)决定是否继续。然后，所有这三项都可以根据这一职能加以实现。

template <class F>
bool traverse(F f) { 
    for (auto pos = head; pos; pos=pos->next)
       if (f(pos->user_data))
           return true;
    return false;
}

与您的markAsPurchased相比，这将(可能)提高效率(即使在找到一个项目并将其标记为已购买的项目之后，它也会继续遍历列表)。