Optimize search in std::deque

Question

I'm doing a program that has a different kind of objects and all of them are children of a virtual class. I'm doing this looking for the advantages of polymorphism that allow me to call from a manager class a certain method of all the objects without checking the specific kind of object it is.

The point is the different kind of objects need sometimes get a list of objects of a certain type.

In that moment my manager class loop thought all the objects and check the type of the object. It creates a list and return it like this:

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 is a deque. I know iterate a data structure is normally expensive but I want to know if is possible to polish it a little bit because now this function takes a third of all the time used in the program.

My question is: is there any design pattern or fuction that I'm not taking into account in order to reduce the cost of this operation in my program?

Answer 1

In the code as given, there is just a single optimization that can be done locally:

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

The rationale is that operator[] is generally not the most efficient way to access a deque. Having said that, I don't expect a major improvement. Your locality of reference is very poor: You're essentially looking at two dereferences (shared_ptr and string).

A logical approach would be to make m_objects a std::multimap keyed by type.