Have a look at your compare operator! It orders two pairs of values (A,B)(C,D) like this: (A<B) || (!(A<B) && (C<D)) this expession equals: (A<B) || (C<D) lets consider the test case: (1,2) (2,1) Your operator will return return true in whatever order this pair is compared... I think an operator like (A<B) || ((A==B) && (C<D)) will help

... typedef multiset<DataEdge,ltSubgraph> Edges; ... struct ltSubgraph : public std::binary_function<DataEdge,DataEdge,bool> { bool operator() (const DataEdge& s1, const DataEdge& s2) const { return s1.m_source < s2.m_source || (!(s1.m_source < s2.m_source) && s1.m_target < s2.m_target); } };