在 std::deque 中优化搜索
Optimize search in std::deque
我正在编写一个包含不同类型对象的程序,并且所有对象都是虚拟 class 的子对象。我这样做是为了寻找多态性的优势,它允许我从管理器 class 调用所有对象的特定方法,而无需检查它是特定类型的对象。
重点是不同类型的对象有时需要获取特定类型的对象列表。
在那一刻,我的经理 class 循环考虑所有对象并检查对象的类型。它创建了一个列表,return 像这样:
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 是双端队列。我知道迭代一个数据结构通常 很昂贵,但我想知道是否可以稍微改进一下,因为现在这个函数占用了程序中所有时间的三分之一。
我的问题是:是否有任何我没有考虑到的设计模式或功能,以便在我的程序中降低此操作的成本?
您可以做一些事情来加快速度:
- 将类型存储在基础 class 上,这将删除一个有点昂贵的虚拟查找。
- 如果类型是
string
,等改为
像枚举或整数这样的简单类型
- A
vector
比
更有效
遍历比 deque
- 如果继续使用
deque
,请使用迭代器或基于范围的 for 循环来避免随机查找(在 deque
中成本更高)
基于范围的看起来像这样:
for (auto const& obj : m_objects)
{
if (obj->GetType() == type)
{
objectsOfType.push_back(obj);
}
}
更新:另外,我建议不要使用 std::list
(除非出于某种原因您必须这样做),因为它在许多情况下表现不佳 - 再次出现 std::vector
来救援!
在给定的代码中,只有一个优化可以在本地完成:
for (auto const& obj : m_objects)
{
if (obj->GetType() == type)
{
objectsOfType.push_back(obj);
}
}
理由是 operator[]
通常不是访问 deque
的最有效方式。话虽如此,我预计不会有重大改进。您的引用位置非常差:您实际上是在查看两个取消引用(shared_ptr
和 string
)。
一种合乎逻辑的方法是使 m_objects
成为按类型键入的 std::multimap
。
我正在编写一个包含不同类型对象的程序,并且所有对象都是虚拟 class 的子对象。我这样做是为了寻找多态性的优势,它允许我从管理器 class 调用所有对象的特定方法,而无需检查它是特定类型的对象。
重点是不同类型的对象有时需要获取特定类型的对象列表。
在那一刻,我的经理 class 循环考虑所有对象并检查对象的类型。它创建了一个列表,return 像这样:
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 是双端队列。我知道迭代一个数据结构通常 很昂贵,但我想知道是否可以稍微改进一下,因为现在这个函数占用了程序中所有时间的三分之一。
我的问题是:是否有任何我没有考虑到的设计模式或功能,以便在我的程序中降低此操作的成本?
您可以做一些事情来加快速度:
- 将类型存储在基础 class 上,这将删除一个有点昂贵的虚拟查找。
- 如果类型是
string
,等改为
像枚举或整数这样的简单类型 - A
vector
比
更有效 遍历比deque
- 如果继续使用
deque
,请使用迭代器或基于范围的 for 循环来避免随机查找(在deque
中成本更高)
基于范围的看起来像这样:
for (auto const& obj : m_objects)
{
if (obj->GetType() == type)
{
objectsOfType.push_back(obj);
}
}
更新:另外,我建议不要使用 std::list
(除非出于某种原因您必须这样做),因为它在许多情况下表现不佳 - 再次出现 std::vector
来救援!
在给定的代码中,只有一个优化可以在本地完成:
for (auto const& obj : m_objects)
{
if (obj->GetType() == type)
{
objectsOfType.push_back(obj);
}
}
理由是 operator[]
通常不是访问 deque
的最有效方式。话虽如此,我预计不会有重大改进。您的引用位置非常差:您实际上是在查看两个取消引用(shared_ptr
和 string
)。
一种合乎逻辑的方法是使 m_objects
成为按类型键入的 std::multimap
。