C++ modifying vector of pointers to structs cause undefined behavior

Question

I have a vector of pointers pointing to structs that are stored in another vector for my school project. When I tried to change an element in a struct using the pointer, it caused undefined behavior for some reason. I ripped out part of the code that are related to the issue below.

#include <vector>
#include <string>
#include <iostream>

class someException{};

enum class ProcessStatus{
  RUNNING,
  READY
};

struct Process{
  int priority;
  std::string PID;
  ProcessStatus status;
  Process(){
    status = ProcessStatus::READY;
  }
};

struct ReadyList{
  std::vector<Process*> priority1;
  std::vector<Process*> priority0;
};

class ProcessManager{
private:
  std::vector<Process> processList;
  ReadyList readyList;
public:
  ProcessManager(){};

  void createProcess(std::string PID, int priority){
    Process process;
    process.priority = priority;
    process.PID = PID;
    if (priority == 0)
      process.status = ProcessStatus::RUNNING;
    processList.push_back(process);
    switch(priority){
      case 0:
        readyList.priority0.push_back(&processList.at(processList.size()-1));
        break;
      case 1:
        readyList.priority1.push_back(&processList.at(processList.size()-1));
        break;
      default:
        throw someException();
    }
    schedule(findRunningProcess());
  }

  void printProcesses(){
    std::cout<<"ReadyList results:"<<std::endl;
    for(auto &process: readyList.priority0){
      std::cout << "Process: "<< process->PID << " , Priority: "<<process->priority;
      if (process->status == ProcessStatus::RUNNING)
        std::cout << ", Status: RUNNING"<< std::endl;
      else
        std::cout <<", Status: READY"<<std::endl;
    }
    for(auto &process: readyList.priority1){
      std::cout << "Process: "<< process->PID << " , Priority: "<<process->priority;
      if (process->status == ProcessStatus::RUNNING)
        std::cout << ", Status: RUNNING"<< std::endl;
      else
        std::cout <<", Status: READY"<<std::endl;
    }
    std::cout<<"ProcessList results: "<<std::endl;
    for(auto &process: processList){
      std::cout << "Process: "<< process.PID << " , Priority: "<<process.priority;
      if (process.status == ProcessStatus::RUNNING)
        std::cout << ", Status: RUNNING"<< std::endl;
      else
        std::cout <<", Status: READY"<<std::endl;
    }
  }

private:
  void schedule(Process* currentProcess){
    Process* highestPriorityProcess;
    if (readyList.priority1.size()>0)
      highestPriorityProcess = readyList.priority1[0];
    else
      highestPriorityProcess = readyList.priority0[0];
    if (currentProcess->priority < highestPriorityProcess->priority){
      currentProcess->status = ProcessStatus::READY;
      highestPriorityProcess->status = ProcessStatus::RUNNING;
    }
  }

  Process* findRunningProcess(){
    for (auto &process: processList){
      if (process.status == ProcessStatus::RUNNING){
        return &process;
      }
    }
    return nullptr;
  }
};

int main(){
  ProcessManager pm = ProcessManager();
  pm.createProcess("ROOT", 0);
  std::cout<<"After creating process ROOT"<<std::endl;
  pm.printProcesses();
  pm.createProcess("A", 1);
  std::cout<<"After creating process A"<<std::endl;
  pm.printProcesses();
  return 0;
};

The output result is this:

After creating process ROOT
ReadyList results:
Process: ROOT , Priority: 0, Status: RUNNING
ProcessList results: 
Process: ROOT , Priority: 0, Status: RUNNING
After creating process A
ReadyList results:
Process: ROOT , Priority: 0, Status: RUNNING
Process: A , Priority: 1, Status: RUNNING
ProcessList results: 
Process: ROOT , Priority: 0, Status: READY
Process: A , Priority: 1, Status: RUNNING

ProcessList is set to the correct value with process A running and process ROOT in ready, but for some reason ReadyList is unchanged. In my original code, the PID string value for process ROOT in readylist became empty and the map value stored in the process, which I left out in this example, is also wiped out after changing status. I also tested out changing with the readyList pointer directly instead of using the pointer returned by findRunningProcess function, which didn't fix the issue with PID and map value but caused some other undefined behavior in process status. I am out of ideas for what might be causing this, please help! Many thanks.

Answer 1

Every time you:

processList.push_back(process);

the vector may resize. The means that the datastore backing the vector will be copied into a new datastore and then discarded. This leaves you with two other vectors containing pointers to memory that has been released and possibly reallocated.

processList is a good place to use a std::list or a std::deque because they don't invalidate the pointers as they grow. std::deque should have some performance advantages as it tends to have better spacial locality.

An alternative is to have the other two vectors store the indexes of processes in processList as they will not change so long as you only push back and do not remove processes.

In either case, removing processes from processList without making sure they have first been been removed from the other vectors would be a bad idea. std::deque is at a disadvantage with removal should you erase a process from the middle as this will invalidate the pointers.

Answer 2

I suspect your process list vector in ProcessManager is being resized at some point, causing it to have to create a new internal data structure and copy the contents over, leaving your old pointers dangling.

As stated here: http://en.cppreference.com/w/cpp/container/vector/push_back

If the new size() is greater than capacity() then all iterators and references (including the past-the-end iterator) are invalidated. Otherwise only the past-the-end iterator is invalidated.