STL Sort efficiency & set comparator usage

[dupdupdup]

Q1: First of all, i would like to ask if i have a program which needs to sort a set of data by diffrent ways frequently in a program, which stl should i used. i settleed down with list as it is implemented as a linked list. so i suppose the data movement for sort will not be so heavy?

or should i use a set, as the data set im sorting also have to be unique.

Q2: How do we sort base on diffrent criteria dynamically? like lets say if i have 3 diffrent criteria of sorting.

with reference to the code from the tutorial of this website,
what does the below code mean?

 bool(*fn_pt)(int,int) = fncomp;
  set<int,bool(*)(int,int)> sixth (fn_pt);  // function pointer as Compar 

// constructing sets
#include <iostream>
#include <set>
using namespace std;

bool fncomp (int lhs, int rhs) {return lhs<rhs;}

struct classcomp {
  bool operator() (const int& lhs, const int& rhs) const
  {return lhs<rhs;}
};

int main ()
{
  set<int> first;                           // empty set of ints

  int myints[]= {10,20,30,40,50};
  set<int> second (myints,myints+5);        // pointers used as iterators

  set<int> third (second);                  // a copy of second

  set<int> fourth (second.begin(), second.end());  // iterator ctor.

  set<int,classcomp> fifth;                 // class as Compare

  bool(*fn_pt)(int,int) = fncomp;
  set<int,bool(*)(int,int)> sixth (fn_pt);  // function pointer as Compare

  return 0;
}

[kbw]

Very early on in my Computer Science studies, we covered a data structure that was called a Plex. It's described in Computer Science by C.S. French. But since those days, I've not heard any mention of it.

The idea is this. You want to simultaneously hold data sorted in different ways. This solution uses a linked list. But instead of a single link, there's an array of links, one for each sort order. When an item is inserted, it's inserted into each link using that link's sort criteria.

STL does not have an implementation of this structure, but there's no reason why you can't write your own.

Some time ago, jsmith posted a boost solution on this site.

[dupdupdup]

Hey man, i see whaat yyou are talking about. That is definitely more efficient. but due to time constraints for my assignment, i am not reqired to write complex algorithms. as such im curious on how the list::sort() works. as list is implemented as a linked list.

Does it mean that the sort algorithm it has only moves the pointers but not the data itself? I've been trying to look for answers regarding this, but to no avail none is on the internet.

so if not, using the stl, which will be better to use. vector or list? i went with list initially, but im still not confident that list is better.

[bluecoder]

Hi ,
I have quick question

How do you initialize the value in the fifth and sixth object of the set ?
Ho do you display the element in the fifth and sixth object ?

Thanks in advance .

[D80DSL3A]

I think that the stl std::list::sort() works by reassigning the links rather than by moving the data.
From this sites reference section:

Compared to other base standard sequence containers (vectors and deques), lists perform generally better in inserting, extracting and moving elements in any position within the container, and therefore also in algorithms that make intensive use of these, like sorting algorithms.

@kbw Thanks for the programming exercise idea! I have a plex structure working as a template class now. I'd give more detail here but that would be thread-jacking.
Perhaps I'll start a new thread on it. One aspect of my solution (applying sort criterion in a generic manner in the insert() ) seems less than ideal.