c++ - 如何优化 C++ 中有关 CPU 和内存的大量映射插入

Question

我正在迭代一个 map ，我需要根据未找到元素的条件(可能是任何其他条件)在该 map 上添加元素。

我的主要问题是，随着要添加的大量更新，应用程序占用了整个 CPU 和所有内存。

状态类:

class State {

    int id;

    int timeStamp;

    int state;

}

状态中的方法:

void State::updateStateIfTimeStampIsHigher(const State& state) {
    if (this->id == state.getId() && state.getTimeStamp() > this->getTimeStamp()) {
        this->timeStamp = state.getTimeStamp();
        this->state = state.getState();
    }
}

循环代码:

std::map<int, State> data;

const std::map<int, State>& update;

for (auto const& updatePos : update) {
    if (updatePos.first != this->toNodeId) {
        std::map<int, State>::iterator message = data.find(updatePos.first);
        if (message != data.end() && message->first) {
            message->second.updateStateIfTimeStampIsHigher(updatePos.second);
        } else {
            data.insert(std::make_pair(updatePos.first, updatePos.second));
        }
    }
}

观察 KCacheGrind 数据，看起来 data.insert() 行占用了大部分时间/内存。我是 KCacheGrind 的新手，但这条线似乎占了成本的 72% 左右。

你对如何改进这个有什么建议吗？

Answer 1

你的问题很笼统，但我看到了让它运行得更快的东西:

1. 使用提示插入/放置。当您添加新元素时，将返回其迭代器。假设两个 map 都以相同的方式排序，您可以知道最后一个插入的位置，因此查找应该更快(可以在此处使用一些基准测试)。
2. 使用 emplace_hint 加快插入速度

此处示例代码:

std::map<int, long> data;

const std::map<int, long> update;
auto recent = data.begin();

for (auto const& updatePos : update) {
    if (updateElemNotFound) { 
        recent = data.emplace_hint(recent, updatePos);
    }
}

此外，如果您想用 CPU 换取内存，您可以使用 unordered_map (Is there any advantage of using map over unordered_map in case of trivial keys?)，但第一个点不再重要。