c++ - 优化 std::deque 中的搜索

Question

我正在编写一个程序，其中包含不同类型的对象，并且所有对象都是虚拟类的子对象。我这样做是为了寻找多态性的优势，它允许我从管理器类调用所有对象的特定方法，而无需检查它是特定类型的对象。

重点是不同类型的对象有时需要获取特定类型的对象列表。

在那一刻，我的管理器类循环遍历所有对象并检查对象的类型。它创建一个列表并像这样返回它:

std::list<std::shared_ptr<Object>> ObjectManager::GetObjectsOfType(std::string type)
{
    std::list<std::shared_ptr<Object>> objectsOfType;

    for (int i = 0; i < m_objects.size(); ++i)
    {
        if (m_objects[i]->GetType() == type)
        {
            objectsOfType.push_back(m_objects[i]);
        }
    }

    return objectsOfType;
}

m_objects 是双端队列。我知道迭代数据结构通常很昂贵，但我想知道是否可以稍微改进它，因为现在这个函数占用了程序中所有时间的三分之一。

我的问题是:是否有任何我没有考虑到的设计模式或功能，以便在我的程序中降低此操作的成本？

Answer 1

在给定的代码中，只有一个可以在本地完成的优化:

for (auto const& obj : m_objects)
{
    if (obj->GetType() == type)
    {
        objectsOfType.push_back(obj);
    }
}

理由是 operator[] 通常不是访问 deque 的最有效方式。话虽如此，我预计不会有重大改进。您的引用位置非常差:您实际上是在查看两个取消引用(shared_ptr 和 string)。

一种合乎逻辑的方法是使 m_objects 成为按类型键入的 std::multimap。