c++ - 访问 std::list 元素获取核心转储

Question

#include <iostream>
#include <string>
#include <fstream>
#include <list>
#include <map>
#include <iomanip>
using namespace std;

void runSimulation(int frameNum, fstream &fs);
void handleMemory(string address);
void handleAddress(int frameNum, string address);
void insertValue(string index);
void replaceValue(string index);
void updateOrder(list<string>::iterator orderPos);

int hit_num = 0, miss_num = 0;
const int INDEX_BITS = 5;
typedef map< string, list<string>::iterator > Memory;
typedef pair< string, list<string>::iterator > MemPair;
Memory memory;
list<string> order;

int main(){

    fstream fs;
    fs.open("trace.txt", fstream::in);

    cout <<  "LRU---"  << endl;
    cout << left << setw(10) << "size";
    cout << left << setw(15) << "miss";
    cout << left << setw(20) << "hit";
    cout << "page fault ratio" << endl;
    for(int i=256; i<=512; i*=2){
        runSimulation(i, fs);
        fs.clear();
        fs.seekg(0, ios::beg);
    }

    fs.close();

    return 0;
}

void runSimulation(int frameNum, fstream &fs){
    memory.clear();
    order.clear();
    hit_num = 0;
    miss_num = 0;

    string str;
    while(getline(fs, str)){
        handleAddress(frameNum, str);
    }

    cout << left << setw(10) << frameNum;
    cout << left << setw(15) << miss_num;
    cout << left << setw(20) << hit_num;
    cout << fixed << setprecision(9) <<  (double)miss_num/(miss_num + hit_num) << endl;
}

void handleAddress(int frameNum, string address){
    string index;
    Memory::iterator found;

    index = address.substr(0, INDEX_BITS);
    found = memory.find(index);
    if(found == memory.end()){ // miss
        miss_num++;
        if(memory.size() < frameNum){ // there are empty spaces
            insertValue(index);
        }
        else{
            replaceValue(index);
        }
    }
    else{ // hit
        hit_num++;
        //cout << "hit: " << found->first << endl;
        updateOrder(found->second);
    }
}

void insertValue(string index){
    //cout << "insert: " << index << endl;
    string *newIndex = new string;
    order.push_back(index);
    list<string>::iterator it = order.end();
    it--;
    memory.insert(MemPair(index, it));
}

void replaceValue(string index){
    //cout << "replace: " << index << endl;
    memory.erase(order.front());
    order.pop_front();
    insertValue(index);
}

void updateOrder(list<string>::iterator orderPos){
    string value = *orderPos;
    order.erase(orderPos);
    order.push_back(value);
}

我正在尝试模拟操作系统中最近最少使用的机制。但我想如果你不知道这一点，你仍然可以理解这个问题。

输入将是一系列虚构的内存地址，它们以string的形式被操作在整个程序中。 (我不是在谈论变量的地址或指针或其他东西。)每一行包含一个地址，我使用 getline 逐行读取它们。 .

而且有两个容器我需要一直维护。
第一个是 map ，类型是<string, list<string::iterator>> .这记录虚内存中当前是否存在一个地址，以及该地址在链表(第二个容器)中的位置。
第二个是列表，类型为list<string> .这会跟踪每个地址的“最近”。最近的一个在后面，最近的一个在前面。

得到一个地址后，如果map中不存在该地址(而且虚内存中还有空位)，则先push_back进入列表。然后我会记录该元素在列表中的位置，制作一个 pair<string, list<string::iterator>> (first 是地址，second 是位置)，insert它进入 map 。

如果虚内存已满，则弹出最旧的，插入新的。应维护两个容器。通过访问列表的前面，我知道哪个是最近的。

如果地址已经存在于 map 中(命中)，列表中对应的数据将为erase d 和 push_back再次进入列表，使其成为最新的。

这就是问题所在。

在运行输入时，有时我会发生核心转储。 gdb 告诉我问题总是在 updateOrder 中(我尝试了几种不同的重新排列代码的方法)。我想我没有很好地处理迭代器。

更有趣的是，如果我这样做 runSimulation(64, fs) frameNum 没问题为 64，核心转储为 128。但是，如果我这样做 runSimulation(128, fs)首先，它在 128 时还不错，但在 256 时被抛售。

在runSimulation开始的初始化过程中是否出了问题？ ？还是迭代器指向了错误的位置？

Answer 1

问题出在 updateOrder 中。您删除现有节点并创建一个新节点，但 memory 仍然有一个指向已删除节点的迭代器。您可以使用新位置更新 memory，但更好的解决方案是使用 splice:

void updateOrder(list<string>::iterator orderPos){
    order.splice(order.back(), order, orderpos);
}

这会将现有节点移动到列表的末尾，而不会使任何现有迭代器失效。

顺便说一句，当您分配一个字符串(您不使用)时，您会在 insertValue 中泄漏内存。