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.

when you do `processList.push_back(process)` it may cause the vector to reallocate, making all of your pointers dangle — M.M, Jan 25 '17 at 05:00

score 6 · Accepted Answer · edited Oct 02 '17 at 22:02

6

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.

edited Oct 02 '17 at 22:02

gsamaras

71,951
46
188
305

answered Jan 25 '17 at 05:03

user4581301

33,082
7
33
54

1

`deque` doesn't invalidate pointers either when growing, so it might be an even better choice. – Mark Ransom Jan 25 '17 at 05:22
1

@MarkRansom Wow. Embarrassed I missed that option. – user4581301 Jan 25 '17 at 05:30
Thanks for answering! So if I do need to erase an element anywhere in the processList, given that I will also remove the corresponding pointers in the other vectors, I will need to use std::list instead of std::deque to prevent invalidation of pointer? I checked over here: http://stackoverflow.com/questions/3287801/pointers-to-elements-of-stdvector-and-stdlist which said that list should handle this just fine. – B Wai Jan 25 '17 at 19:23
@BWai Yes. `deque` is designed for adding and removing from beginning and end with as little pain as possible, but it doesn't touch the data in the middle unless you tell it to. But once you tell a `deque` to operate on the middle, you can no longer trust the pointers. With a `list` the standard assures you no pointers will be harmed. `list` is dead stupid simple and close to foolproof, but can be slow. I recommend starting with `list`, getting your logic sorted out and working, and then profiling the program to see if `list` is fast enough. – user4581301 Jan 25 '17 at 19:43
Thanks a lot! I used a list and it fixed everything! One more follow up question if you don't mind. I'm still kind of new to c++ and am not quite sure about the difference between reference and pointer, though I heard the former is safer. Would I have avoided this issue if I used a vector of references instead of pointers? – B Wai Jan 25 '17 at 22:52
@BWai No. A reference is pointer with some restrictions. For one thing, a reference must point to something when it is created and cannot be repointed at a different object. Unfortunately nothing prevents you from invalidating what the reference refers to AFTER the reference is created, which is what you ran into here. – user4581301 Jan 25 '17 at 22:56

score 1 · Answer 2 · answered Jan 25 '17 at 05:01

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.

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

2 Answers2