使用 Iterator C++ 修改对象时出现问题

Question

所以我正在使用迭代器遍历堆栈和队列列表，我需要修改它们。我尝试取消引用迭代器，然后使用 pop 和 push 但对象没有改变。

我认为问题出在函数 Push 和 Pop（不是堆栈和队列的成员函数）上，但我可能是错的。实际程序接受一个包含命令的文件，但我修改了它，以便它接受单行命令。

这是代码的可重现版本：

#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>
#include <string>
using namespace std;
#include <list>


template <class T>

class SimpleList
{
    struct Node
    {
        T data;
        Node* next;
        Node(T datI, Node* nextI) 
        {
            data = datI;
            next = nextI;
        }
    };

public:
    Node* start;
    int size;
    Node* end;
    std::string name;

    SimpleList(std::string title)
    {
        name = title;
        size = 0;
    }


    void addFront(T element)
    {
        Node *temp = new Node(element, start);
        if (size == 0) {end = temp;}
        if (size == 1) {(*start).next = end;}
        if (size > 1) {(*temp).next = start;}
        start = temp;
        size ++;
    }

    void addEnd(T element)
    {
        Node *temp = new Node(element, NULL);
        if (size == 0) {start = temp;}
        end = temp;
        if(size > 0) {(*end).next = temp;}
        size ++;
    }

    T* remove()
    {
        if (size == 0) {return 0;}
        T *temp = &((*start).data);
        start = (*start).next;
        size --;
        if (size == 1) {start = end;}
        return temp;
    }

    virtual void push(T element) {}

    virtual T pop() { return *(remove()); }
};

template <class T>

class Stack :public SimpleList<T>
{
public:

    Stack(std::string title): SimpleList<T>(title) {}
    void push(T element){SimpleList<T>::addFront(element);}
};

template <class T>

class Queue :public SimpleList<T>
{
public:

    Queue(std::string title): SimpleList<T>(title) {}
    void push(T element){SimpleList<T>::addEnd(element);}
};


std::list<SimpleList<std::string> > liI;
std::list<SimpleList<std::string> > liD;
std::list<SimpleList<std::string> > liS;

bool IsIn(std::string title, std::list<SimpleList<std::string> > li)
{

    std::list<SimpleList<std::string> >::iterator it;
    for (it = li.begin(); it != li.end(); ++it)
    {
        std::string temp = it -> name;
        if(temp == title){return true;}
    }
    return false;
}



std::string Pop(std::vector<std::string> para, std::list<SimpleList<std::string> > *li)
{
    if(!IsIn(para[1], *li)) { return "\nERROR: This name does not exist!\n";}
    std::list<SimpleList<std::string> >::iterator it;
    for (it = (*li).begin(); it != (*li).end(); ++it)
    {

        if(it -> name == para[1])
        {
            return "\nValue popped: " + (*it).pop() + "\n";
        }
    }
    return "";
}

std::string Push(std::vector<std::string> para, std::list<SimpleList<std::string> > *li)
{
    if(!IsIn(para[1], *li)) { return "\nERROR: This name does not exist!\n";}
    std::list<SimpleList<std::string> >::iterator it;

    for (it = (*li).begin(); it != (*li).end(); ++it)
    {
        if(it -> name == para[1])
        {
            (*it).push(para[2]);
            return "\n";
        }
    }
    return "";
}

std::string Create(std::vector<std::string> para, std::list<SimpleList<std::string> > *li)
{
    if(IsIn(para[1], *li)) { return "\nERROR: This name already exists!\n";}
    if (para[2] == "stack") 
    {
        Stack<std::string> temp = Stack<std::string>(para[1]);
        (*li).push_back(temp);
    }
    else 
    {
        Queue<std::string> temp = Queue<std::string>(para[1]);
        (*li).push_back(temp);
    }
    return "\n";
}



std::string Processing(std::vector<std::string> para)
{
    std::string message;
    if (para[0] == "create")
    {
        if (para[1][0] == 'i') {message = Create(para, &liI);}
        if (para[1][0] == 's') {message = Create(para, &liS);}
        else {message = Create(para, &liD);}
    }

    if (para[0] == "push")
    {
        if (para[1][0] == 'i') {message = Push(para, &liI);}
        if (para[1][0] == 's') {message = Push(para, &liS);}
        else {message = Push(para, &liD);}
    }

    if (para[0] == "pop")
    {
        if (para[1][0] == 'i') {message = Pop(para, &liI);}
        if (para[1][0] == 's') {message = Pop(para, &liS);}
        else {message  = Pop(para, &liD);}
    }
    return message;
}
int main()
{

    std::vector<std::string> vec;
    vec.push_back("create");
    vec.push_back("i1");
    vec.push_back("queue");
    std::cout << Processing(vec);

    vec.clear();
    vec.push_back("push");
    vec.push_back("i1");
    vec.push_back("500");
    std::cout << Processing(vec);

    vec.clear();
    vec.push_back("pop");
    vec.push_back("i1");
    std::cout << Processing(vec);
    return 0;
}

Answer 1

我已经进行了我认为最少的更改，以使程序更好地运行。一般来说，这只不过是应用你现在应该已经学会的最佳实践。在你的 add*() 函数中有几个地方你在做一些无意义的操作。

链接列表极大地受益于绘图。画出算法的逐步步骤，然后对其进行编码。如果它不起作用，您可以参考一系列图片，轻松找到代码分歧的地方。

#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
// using namespace std;  // CHANGED: Bad practice
#include <list>

template <class T>  // CHANGED: Removed blank line
class SimpleList {
  struct Node {
    T data = T();  // CHANGED: added default member initialization
    Node* next = nullptr;
    // Node(T datI, Node* nextI)  // CHANGED: Unncecessary; hinders
    // {                          // aggregate initialization
    //     data = datI;
    //     next = nextI;
    // }
  };

  // Not changing for now, but traditionally linked lists have a head and tail
  Node* start = nullptr;  // CHANGED: Added default member initialization
  int size = 0;
  Node* end = nullptr;
  std::string name;

 public:  // CHANGED: Made list data private
  SimpleList(std::string title)
      : name(title) {}  // CHANGED: use ctor
                        // initialization sections

  std::string get_name() const { return name; }  // Added getter for name

  void addFront(T element) {
    // NOTE: Use nullptr in C++, not NULL
    Node* temp = new Node{element};  // CHANGED: Used aggregate initialization
    if (size == 0) end = temp;
    // if (size == 1) start->next = end;  // CHANGED: Makes no sense
    if (size > 1) temp->next = start;  // CHANGED: Arrow notation
    start = temp;
    size++;
  }

  void addEnd(T element) {
    // Similar changeas as above
    Node* temp = new Node{element};
    if (size == 0) start = temp;
    end = temp;
    if (size > 0) end->next = temp;
    size++;
  }

  // Function broken as delivered; remove WHAT?
  // CHANGED: Reading the body implies that the function is poorly named, so
  // changed the name
  T pop_front() {
    if (size == 0) return nullptr;  // CHANGED: Fixed return type
    T temp = start->data;           // CHANGED: Copy data held in start
    Node* tmpNode = start;          // CHANGED: Need to track original start
    start = start->next;

    delete tmpNode;  // CHANGED: Actually get rid of node
    size--;          // CHANGED: Remove space
    // if (size == 1) start = end;  // CHANGED: Makes no sense

    // NOTE: pop functions should only delete, not provide the data
    // You provide the data, and never delete
    return temp;
  }

  // virtual void push(T element) {}  // ???

  // virtual T pop() { return *(remove()); }  // ???
};

template <class T>  // CHANGED: Removed blank line
class Stack : public SimpleList<T> {
 public:
  Stack(std::string title) : SimpleList<T>(title) {}
  void push(T element) { SimpleList<T>::addFront(element); }
};

template <class T>  // CHANGED: Removed blank line
class Queue : public SimpleList<T> {
 public:
  Queue(std::string title) : SimpleList<T>(title) {}
  void push(T element) { SimpleList<T>::addEnd(element); }
};

// CHANGED: Moving randomly placed globals into main()
// std::list<SimpleList<std::string> > liI;
// std::list<SimpleList<std::string> > liD;
// std::list<SimpleList<std::string> > liS;

bool IsIn(std::string title, std::list<SimpleList<std::string>> li) {
  // CHANGED: Moved declartion into for loop with auto
  // std::list<SimpleList<std::string> >::iterator it;
  for (auto it = li.begin(); it != li.end(); ++it) {
    std::string temp = it->get_name();  // CHANGED: removed spacing around arrow
    if (temp == title) return true;
  }
  return false;
}

// CHANGED: Changed parameter from pointer to list to reference to list
std::string Pop(std::vector<std::string> para,
                std::list<SimpleList<std::string>>& li) {
  if (!IsIn(para[1], li)) {
    return "\nERROR: This name does not exist!\n";
  }
  // std::list<SimpleList<std::string> >::iterator it;
  for (auto it = (li).begin(); it != (li).end(); ++it) {
    if (it->get_name() == para[1]) {
      // CHANGED: Cleaned up and fixed return statement
      return "\nValue popped: " + it->pop_front() + "\n";
    }
  }
  return "";
}

// CHANGED: Changed parameter from pointer to list to reference to list
std::string Push(std::vector<std::string> para,
                 std::list<SimpleList<std::string>>& li) {
  if (!IsIn(para[1], li)) {
    return "\nERROR: This name does not exist!\n";
  }
  std::list<SimpleList<std::string>>::iterator it;

  for (it = (li).begin(); it != (li).end(); ++it) {
    if (it->get_name() == para[1]) {
      it->addEnd(para[2]);  // Changed to correct call
      return "\n";
    }
  }
  return "";
}

// CHANGED: Change parameter from pointer to list to reference to list
std::string Create(std::vector<std::string> para,
                   std::list<SimpleList<std::string>>& li) {
  if (IsIn(para[1], li)) {
    return "\nERROR: This name already exists!\n";
  }
  if (para[2] == "stack") {
    Stack<std::string> temp = Stack<std::string>(para[1]);
    (li).push_back(temp);
  } else {
    Queue<std::string> temp = Queue<std::string>(para[1]);
    (li).push_back(temp);
  }
  return "\n";
}

// CHANGED: In attempting to make minimal changes, this is going into main()
// as a lambda
// std::string Processing(std::vector<std::string> para)
// {
//     std::string message;
//     if (para[0] == "create")
//     {
//         if (para[1][0] == 'i') {message = Create(para, liI);}
//         if (para[1][0] == 's') {message = Create(para, liS);}
//         else {message = Create(para, liD);}
//     }

//     if (para[0] == "push")
//     {
//         if (para[1][0] == 'i') {message = Push(para, liI);}
//         if (para[1][0] == 's') {message = Push(para, liS);}
//         else {message = Push(para, liD);}
//     }

//     if (para[0] == "pop")
//     {
//         if (para[1][0] == 'i') {message = Pop(para, liI);}
//         if (para[1][0] == 's') {message = Poppara, liS);}
//         else {message  = Pop(para, liD);}
//     }
//     return message;
// }

int main() {
  std::list<SimpleList<std::string>> liI;
  std::list<SimpleList<std::string>> liD;
  std::list<SimpleList<std::string>> liS;

  auto Processing = [&liI, &liD, &liS](std::vector<std::string> para) {
    std::string message;
    if (para[0] == "create") {
      if (para[1][0] == 'i') {
        message = Create(para, liI);
      }
      if (para[1][0] == 's') {
        message = Create(para, liS);
      } else {
        message = Create(para, liD);
      }
    }

    if (para[0] == "push") {
      if (para[1][0] == 'i') {
        message = Push(para, liI);
      }
      if (para[1][0] == 's') {
        message = Push(para, liS);
      } else {
        message = Push(para, liD);
      }
    }

    if (para[0] == "pop") {
      if (para[1][0] == 'i') {
        message = Pop(para, liI);
      }
      if (para[1][0] == 's') {
        message = Pop(para, liS);
      } else {
        message = Pop(para, liD);
      }
    }
    return message;
  };

  std::vector<std::string> vec;
  vec.push_back("create");
  vec.push_back("i1");
  vec.push_back("queue");
  std::cout << Processing(vec);

  vec.clear();
  vec.push_back("push");
  vec.push_back("i1");
  vec.push_back("500");
  std::cout << Processing(vec);

  vec.clear();
  vec.push_back("pop");
  vec.push_back("i1");
  std::cout << Processing(vec);
  return 0;
}

注意：我没有进行广泛的测试，但我不需要进行任何测试就可以证明它不是一个好地方。您缺少析构函数和其他 5 条规则函数，这意味着您将进行浅拷贝和内存泄漏。值得称赞的是，您写了一个 class 而没有写一个 C 风格的链表。

我还运行通过 clang-format 编写代码，因为样式不一致。虽然这可能会让您的代码按原样工作，但我会注意到整体设计不足。您对 Stack 和 Queue 使用继承，这毫无意义。我可以用链表、向量、静态数组等实现堆栈。要说 Stack 是一个 底层数据结构是......嗯。通过使用继承，您还可以为 Stack 和 Queue 提供链表的所有 public 函数，而这些函数本不应该有。比如你的Stack可以加到前面和后面。

更好的是，使用组合。在您的 Stack 中私下持有一个链表。现在，您的 Stack 用户现在可以被适当地限制为只能使用 Stack 函数，而不是完全访问链表的 public 函数。

使用 Iterator C++ 修改对象时出现问题

Trouble Modifying Object with Iterator C++

c++

debugging

queue

stack

iterator