Re: Sorting files -- different approaches, your opinion?

From: Alex Fraser (me_at_privacy.net)
Date: 01/31/05 

Date: Mon, 31 Jan 2005 19:04:14 -0000

"Matthias" <nospam@digitalraid.com> wrote in message
news:ctlsjt$rha$01$1@news.t-online.com...
> I am currently implementing a gtkmm component called FileBrowser. It's a
> scrolled window which can be embedded in a gtkmm application. It's
> basically a view on your directory contents and allows, for example, to
> select one or multiple files, which are stored as a collection in an STL
> container. You can then access this selection of files through the
> components interface.
> This is to ease up interaction between graphical applications (taking
> user input) and the filesystem.
[snip]
> Okay. As of now, I only hold *one* container of files (currently it's a
> list, but I already thought about replacing it with std::vector or even
> std::set).
> Each time the client changes the sorting criterion, this container is
> resorted using the new criterion. This seemed to be the obvious way to
> implement the wanted behavior.

My "wanted behaviour" would be that the sorting is stable, which requires
this method as opposed to pre-sorted lists.

> Another solution would be to hold the files in a "central" std::set (for
> example) and have several std::listS or std::vectorS which are
> pre-sorted using a specific criterion, holding pointers to the elements
> in the set. They don't consume much space, since they merely hold
> pointers to files.
[snip]
> I am currently tending to use the first approach, because I think that
> directory changes are more frequent than changing the sorting order, so
> I want the rebuilding of the file list to be as cheap as possible.

I expect that sorting several arrays (or std::vector) of pointers will
usually take less time than creating the file list in the first place.

> Besides, this approach make the implementation much less complicated.

Less and/or simpler code is almost always preferable IMO.

> Now, since I intend to publish the component (including the source code)
> to the community once it is ready, I'd be glad to hear your thoughts
> about this.

I would:
- read the filenames and information into a std::list (or maybe
  std::vector),
- create a std::vector of pointers and fill it with pointers to the list
  entries,
- use std::sort to sort the pointers by the previously selected
  criterion, and
- use std::stable_sort to sort the pointers when a new criterion is
  selected by the user.

Does that sound sensible?

Alex

Relevant Pages

  • Re: parallel structure(s) used in sorting CListCtrl?
    ... As a typical example of the bad programming, it uses an LPTSTR to hold pointers to strings ... be kept in the LPARAM and the pointers don't need to exist anywhere else. ... the LPARAM field of each element of the list control, and use that for the sorting. ...
    (microsoft.public.vc.mfc)
  • Re: Implementation of n stacks using 1 array
    ... >> pointers), but does not require moving anything. ... the only way you meet all his criterion is if the ... > assignments and for tormenting programmers in the workforce. ...
    (comp.theory)
  • Re: External sorting
    ... Which is the best external sorting algorithm to use when you have ... sorting scheme was to read the data and extract keys and file pointers ... Once the runs are all merged, then build the B* or B+ tree, ...
    (comp.programming)
  • Re: How to find memory hog?
    ... Does anyone have any pointers to source the problem, ... Try sorting the top output by memory usage (shift-m) rather than resident set size. ...
    (comp.os.linux.hardware)
  • Re: sort an array of strings
    ... Rainmaker wrote: ... By HUGE i mean giga bytes of data....it may be more.... ... Sorting the pointers seems to me a good solution. ...
    (comp.lang.c)