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 value(objective);
    const  Real  inserteeValue =  insertee_->value(objective);
    const bool lower = referenceValue >= inserteeValue;
    const  int directionTowardsInsertee = lower ? -1 : 1;
    Iterator it = referencePositions_[objective];

    ReferenceSet& referenceSet = lower ? lowerReferenceSet_:
                                         upperReferenceSet_;
    const  auto comparison = lower ? [](Real a, Real b){return a >= b;}:
                                     [](Real a, Real b){return a value(), inserteeValue))
    {
        referenceSet.insert(it->individual());
        std::advance(it, directionTowardsInsertee);
    }

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

Each list is of type std::list 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 funct

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 value(objective);
    const  Real  inserteeValue =  insertee_->value(objective);
    const bool lower = referenceValue >= inserteeValue;
    Iterator it = referencePositions_[objective];
    if (!lower)
    {
        it = std::reverse_iterator(it);
    }
    ReferenceSet& referenceSet = lower ? lowerReferenceSet_:
                                         upperReferenceSet_;

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

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

StackExchange Code Review Q#32027, answer score: 3