It sounds to me like you are using the wrong tool for the job.
Can you give some more details about your use pattern? (I'm mostly interested in the number of elements you expect to add between using the sorted data, the range of the element values, and the expense of the comparison function.)
I initially just used the list:ush_back function to append all of the additional data structures to the end of the list and then run sort on the entire list.
Depending on the distribution of your data, you may save a lot of time, depending on the sorting algorithm you need to use, by partially sorting the data as you go. (In effect, making a "skip list" of sorts.)
The mechanism of the iterators (for std::list<???>) aren't changed by the element type.
Maybe the ++ operator is very fast when you have a list of say integers, but it seems to be really slow when you have a list of data structures.
Yea. That screams "don't use a linked list" to me. If you are sorting more than you are adding elements, you are using the wrong data structure.
Since my data needs to be sorted so frequently I guess I just have to wait for it to sort.
If he only needs the "shortest guy of the bunch", he only needs to store the "shortest guy of the bunch".
If you're just trying to pick the shortest guy of the bunch or something, you can also brute force that in linear time, after you compile the list, and that is faster than most sorts.