Optimizing iteration through linked lists I have a data structure composed of several std::lists, each sorted by a specific criterion. When a new item is inserted into this data structure, there is a need for a reference item already in this data structure. Also all the items between the reference and insertee need to be collected into sets.

According to the profiler, this insertion is the bottleneck of the entire program. Here I present a simplified version of my insertion method.



upperReferenceSet_.clear();
lowerReferenceSet_.clear();
for (int objective = 0; objective &lt; nObjectives_; ++objective)
{
    const  Real referenceValue = reference_-&gt;value(objective);
    const  Real  inserteeValue =  insertee_-&gt;value(objective);
    const bool lower = referenceValue &gt;= inserteeValue;
    const  int directionTowardsInsertee = lower ? -1 : 1;
    Iterator it = referencePositions_[objective];

    ReferenceSet&amp; referenceSet = lower ? lowerReferenceSet_:
                                         upperReferenceSet_;
    const  auto comparison = lower ? [](Real a, Real b){return a &gt;= b;}:
                                     [](Real a, Real b){return a &lt;= b;};

    while (comparison(it-&gt;value(), inserteeValue))
    {
        referenceSet.insert(it-&gt;individual());
        std::advance(it, directionTowardsInsertee);
    }

    lists_[objective].insert(it, Node(insertee_, inserteeValue));
}


Each list is of type std::list&lt;Node&gt; where the Node is defined by:

class Node
{
public:
    Node(Individual* ind, Real val)       :individual_(ind),value_(val){}
    const Individual* individual() const  {return individual_;}
    Real value() const                     {return value_;}

private:
    Individual* const individual_;
    const Real value_;
};


The Individual is an entity which has n values (objectives), where each value can be accessed by an Individual::value(int index) member function. There are n lists, each containing the same set of Individuals, each sorted by one objective (value). Also the objective pertaining to that list is cached in the node and can be accessed by the Node::value() member function.

I would like to ask how can I make this method faster. I suspect that there are three sources of slowness:


The access to reference sets indirectly using a C++ reference.
The use of lambda functions which produce another indirection.
The use of std::advance just to perform one step.


I am thinking of refactoring the function to pass the data structure in two passes, first for the upper reference sets and then for the lower ones. This would solve all three problems.

I am hesitating since it would result in some code duplicity. Also I am curious about any opinions on my theories and my code.
I haven't tested this solution, but I believe that your code could be simplified by using a reverse_iterator.

upperReferenceSet_.clear();
lowerReferenceSet_.clear();
for (int objective = 0; objective &lt; nObjectives_; ++objective)
{
    const  Real referenceValue = reference_-&gt;value(objective);
    const  Real  inserteeValue =  insertee_-&gt;value(objective);
    const bool lower = referenceValue &gt;= inserteeValue;
    Iterator it = referencePositions_[objective];
    if (!lower)
    {
        it = std::reverse_iterator&lt;Iterator&gt;(it);
    }
    ReferenceSet&amp; referenceSet = lower ? lowerReferenceSet_:
                                         upperReferenceSet_;

    do
    {
        referenceSet.insert(it-&gt;individual());
    } while (it++-&gt;value() != inserteeValue);

    lists_[objective].insert(--it, Node(insertee_, inserteeValue));
}