1

我目前有一个队列，其中包含用户指定数量的名为Process的结构。进程由 pid、burst 和到达组成。我想按到达对队列进行排序，但我不知道从哪里开始。这里有一些伪代码来帮助说明我想说的：

struct Process{
    int pid;
    int burst;
    int arrival;
};

void function(int numProcesses){
    queue<Process> readyQueue;

    // The following loop is a shortened version of my code
    for(int i=0; i<numProcesses;i++){
        readyQueue.push(aProcess);
    }

    // This is where I need help!
    // sort(readyQueue);
}

我会很感激任何可以为我指出如何做到这一点的正确方向的人，或者是否有可能。谢谢！

4

4 回答 4

3

std::sort您可以使用'' 标头中的标准库进行排序。您可以提供一个比较器或定义一个较少的运算符。

struct Process{
    int pid;
    int burst;
    int arrival;
};

    bool operator<(const Process& a, const Process& b) {
          return a.arrival < b.arrival;
    }

    void function(int numProcesses){
        std::dequeue<Process> readyQueue;

        // The following loop is a shortened version of my code
        for(int i=0; i<numProcesses;i++){
             readyQueue.push_back(aProcess);
         }
        std::sort(readyQueue.begin(), readyQueue.end());       
    }

http://en.cppreference.com/w/cpp/algorithm/sort

于 2012-11-08T00:40:16.067 回答
3

大多数情况下，您需要operator<为您的班级定义：

struct Process{
    int pid;
    int burst;
    int arrival;

    bool operator<(Process const &other) { return arrival < other.arrival; }
};

完成后，std::sort将正常工作：

std::sort(std::begin(readyQueue), std::end(readyQueue));
于 2012-11-08T00:40:47.380 回答
0

您应该std::priority_queue改用...否则，每次将某些内容推到队列上时，您都必须对队列进行排序。

请注意，您仍然需要定义operator<

于 2012-11-08T00:43:59.540 回答
0

您想实现一个日历队列。不要为此使用queue数据结构，而是set：

struct Process{
    int pid;
    int burst;
    int arrival;
    bool operator<(Process const& other) const {
      if (arrival == other.arrival) {
        if (pid == other.pid)
          return this < &other;
        return pid < other.pid;
      }
      return arrival < other.arrival;
    }
};

void func() {
  std::set<Process> myQueue;
}

无需显式排序，该集合将始终保持内容排序，您始终可以通过迭代器删除第erase一个begin()。

于 2012-11-08T00:45:55.023 回答