C++: Scott Meyers “Effective STL”: item 31: know your sorting options: help to understand

Question

Good day!

In his "Effective STL" Scott Meyers wrote

A third is to use the information in an ordered container of iterators to iteratively splice the list's elements into the positions you'd like them to be in. As you can see, there are lots of options. (Item 31, second part)

Can someone explain me this way?

---

More text (to understand the context):

The algorithms sort, stable_sort, partial_sort, and nth_element require random access iterators, so they may be applied only to vectors, strings, deques, and arrays. It makes no sense to sort elements in standard associative containers, because such containers use their comparison functions to remain sorted at all times. The only container where we might like to use sort, stable_sort, partial_sort, or nth_element, but can't, is list, and list compensates somewhat by offering its sort member function. (Interestingly, list::sort performs a stable sort.) If you want to sort a list, then, you can, but if you want to use partial_sort, or nth_element on the objects in a list, you have to do it indirectly. One indirect approach is to copy the elements into a container with random access iterators, then apply the desired algorithm to that. Another is to create a container of list::iterators, use the algorithm on that container, then access the list elements via the iterators. A third is to use the information in an ordered container of iterators to iteratively splice the list's elements into the positions you'd like them to be in. As you can see, there are lots of options.

Answer 1

I'm not sure what the confusion is but I suspect that it is what "splicing" refers to: the std::list<T> has an splice() member function (well, actually several overloads) which transfer nodes between lists. That is, you create a std::vector<std::list<T>::const_iterator> and apply the sorting algorithm (e.g. std::partial_sort()) to this. Then you create a new std::list<T> and use the splice() member with the iterators from the sorted vector to put the nodes into their correct order without moving the objects themselves.

This would look something like this:

std::vector<std::list<T>::const_iterator> tmp;
for (auto it(list.begin()), end(list.end()); it != end; ++it) {
    tmp.push_back(it);
}
some_sort_of(tmp);
std::list<T> result;
for (auto it(tmp.begin()), end(tmp.end()); it != end; ++it) {
    result.splice(result.end(), list, it);
}

Answer 2

Let's say you wanted to do a partial_sort on a list. You could store the iterators to the list in a set, by providing a comparison function that can sort using the iterators, like this:

struct iterator_less
{   
    bool operator() (std::list<int>::iterator lhs,
                 std::list<int>::iterator rhs) const
    {
        return (*lhs < *rhs);
    }
};
typedef std::multiset<
    std::list<int>::iterator, iterator_less
> iterator_set;

The you could let set perform the sort, but since it contains iterators to list, you could you list::splice to splice them into a partial_sorted list:

std::list<int> unsorted, partialSorted;
unsorted.push_back(11);
unsorted.push_back(2);
unsorted.push_back(2);
unsorted.push_back(99);
unsorted.push_back(2);
unsorted.push_back(4);
unsorted.push_back(5);
unsorted.push_back(7);
unsorted.push_back(34);

    // First copy the iterators into the set
iterator_set itSet;
for( auto it = unsorted.begin(); it!=unsorted.end();++it)
{
    itSet.insert(it);
}
    // now if you want a partial_sort with the first 3 elements, iterate through the
    // set grabbing the first item in the set and then removing it.
int count = 3;
while(count--)
{
    iterator_set::iterator setTop = itSet.begin();
    partialSorted.splice(
        partialSorted.begin(),
        unsorted,
        *setTop);
    itSet.erase(setTop);
}

partialSorted.splice(
        partialSorted.end(),
        unsorted,
        unsorted.begin(),
        unsorted.end());

Answer 3

An ordered container would be either std::set or std::map. If you're willing to make a comparator that takes iterators you would use std::set<std::list<mydata>::iterator,comparator>, otherwise you could use std::map<mydata,std::list<mydata>::iterator>. You go through your list from begin() to end() and insert the iterators into the set or map; now you can use it to access the items in the list in sorted order by iterating the set or map, because it's automatically sorted.

Answer 4

Ordered containers are std::set and std::multiset. std::set implements a BST. So what it says is that you should crate an std::set<std::list::iterators> and then use the inherent BST structure to do the sorting. Here is a link on BST to get you started.

Answer 5

Edit Ah. Just noticed "ordered container of iterators". That would imply creating an index into another container.

Boost Multi Index has many example of such things (where a single collections is indexed by several different ordering predicates and the indices are nothing more than collections of 'pointers' (usually iterators) into the base container.

---

"A third is to use the information in an ordered container of iterators to iteratively splice the list's elements into the positions you'd like them to be in"

One thing I think would match that description is when doing std::sort_heap of a list/vector which has had std::make_heap/push_heap/pop_heap operating on it.

• make_heap : convert a sequence to a heap
• sort_heap : sort a heap
• push_heap : insert an element in a heap
• pop_heap : remove the top element from a heap

Heaps are organizations of elements within sequences, which make it (relatively) efficient to keep the collection in a known ordering under insert/removal. The order is implicit (like a recursive defined binary tree stored in a contiguous array) and can be transformed into the corresponding properly sorted sequence by doing the (highly efficient) sort_heap algorithm on it.