IndexIntervalDesc contains a std::string, which is expensive to copy, because it allocates and deallocates memory on the heap.
So, sorting through patches may trigger a lot of copy calls, depending on how much there is to sort. Triggering a lot of copy calls will trigger a lot of heap activity, which is slow, espectially in debug mode, because there the heap is often checked a lot.
But even release mode code will be slower than it could be.
Fortunately you have some options to get rid of the expensive string copy call:
1) Make nodeID a std::string*. Copying a pointer is a very cheap operation.
2) Implement a swap method for IndexIntervalDesc, that's recognized by STL, effectively changing the expensive copy calls into much cheaper swap calls.
This may be trickier than it sounds. Read
this.
3) Get rid of nodeId altogether or make it a different type, that's cheaper to copy.
I hope that helps!