c++ - 使用std::forward_list的队列实现返回错误

Question

返回此运行时错误

$/usr/bin/ld: QueueusingSLL: _ZSt4cout: invalid version 2 (max 0)

$/usr/bin/ld: QueueusingSLL: error adding symbols: bad value 
collect2: error: ld returned 1 exit status

另外，如何从类成员函数返回迭代器？
请参阅代码内部的 auto iterator()函数。

源代码

#include<iostream>     // std::cout
#include<forward_list> // std::singly linked list
#include<iterator>     //// std::iterator,next(is a random iterator)
//#include <algorithm> // std::for_each loop
using namespace std;

class Queue
{
private:
   forward_list<int> list;

public:
   Queue()
   {}

   Queue(int firstElem) {
      enqueue(firstElem);
   }

   //Return the size of Queue
   int size()
   {
      forward_list<int>::iterator first = list.begin();
      forward_list<int>::iterator last = list.end();
      return std::distance(first, last);
   }

   //Return whether or not the queue us empty
   void isEmpty()
   {
      std::cout << "Queue " << (list.empty() ? "is empty" : "is not empty") << std::endl;
   }

   // Peek the top of the stack without removing an element
   // Returns 0 if queue is empty.
   int peek()
   {
      if (list.empty() == 1)
         return 0;
      return list.front();
   }

   //Add an element at back(end or tail) of queue:enqueue
   void enqueue(int Elem)
   {
      auto pos = list.begin();
      while (std::next(pos) != list.end()) ++pos;
      list.insert_after(pos, Elem);
   }

   //Remove an element from front of queue:dequeue
   int dequeue()
   {
      if (list.empty() == 1) return 0;
      list.pop_front();
      return 1; //1 means success
   }

   void display()
   {
      cout << endl << "Elements in Queue x";
      for (forward_list<int>::iterator i = list.begin(); i != list.end(); i++)
      {
         cout << endl << "\t" << *i;
      }
      cout << endl << endl;
   }

   /*auto iterator()
    {
        return list.iterator();
    }*/
};


int main()
{
   Queue Q1, Q2(5);
   Q1.isEmpty();
   Q2.isEmpty();
   cout << endl << "sizeofQ1   " << Q1.size() << endl << "sizeofQ2     " << Q2.size() << endl << endl;
   Q1.enqueue(10);
   Q1.enqueue(20);
   Q1.enqueue(30);
   Q1.enqueue(40);
   Q1.enqueue(50);
   Q1.enqueue(60);
   Q1.display();
   Q2.display();
   cout << endl << "sizeofQ1   " << Q1.size() << endl << endl;
   Q1.dequeue();
   Q1.dequeue();
   Q1.display();
   cout << endl << "sizeofQ1   " << Q1.size() << endl << endl;
   return 0;
}

Answer 1

首先，如果您想插入容器的末尾，最好使用 std::vector 而不是std::forward_list。然后只需简单地使用 std::vector::push_back 或 std::vector::emplace_back 。要获取第一个和最后一个元素，请分别使用 std::vector::front 和 std::vector::back 。

问题所在:您的enqueue函数不处理list空情况。你需要

void enqueue(int Elem)
{
   if (list.empty())  // for the empty list case
   {
      list.push_front(Elem);
      return; // done here
   }

   auto pos = list.begin();
   while (std::next(pos) != list.end())
      ++pos;
   list.insert_after(pos, Elem);
}

How can you return an iterator from a class member function?

像在标准容器中一样，您需要通过提供合适的成员来返回 begin和 end迭代器。例如

auto begin() const noexcept {
   return list.begin();
}

auto end() const noexcept {
   return list.end();
}

但是，自 c++14以来，只能返回 auto。在 c++11中，您需要明确提及返回类型。感谢 trailing return，您可以通过它

auto begin() const noexcept -> decltype(list.begin()) // trailing return
{
   return list.begin();
}

auto end() const noexcept -> decltype(list.end()) // trailing return
{
   return list.end();
}

作为旁注， please do not practice with using namespace std;