Login | Register   
LinkedIn
Google+
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


Tip of the Day
Language: C++
Expertise: Intermediate
Mar 22, 2005

Using Sort with Arrays

sort, along with many other STL algorithms, works well with arrays. This is because the STL's concept of an iterator is closely modelled on that of a pointer.

The STL provides two forms of sort. Both forms take an iterator pointing to the beginning of the collection to be sorted as their first argument and an iterator marking the end as their second argument. The iterator marking the end points one past the last element to be sorted. When sorting an array x, the first iterator is x, and the second iterator is x + n, where n is the length of the array.

The first form of sort takes no extra arguments. It uses the operator < for its comparisons. The second form of sort takes a function object as its third parameter, which it uses for its comparisons. The function object should return true if its first argument is less than its second. The function object may either be a function pointer or a functor, an instance of a class that overrides the () operator. An example of a functor is provided in the code below.

The major alternative to sort, other than writing your own sorting code, is C's qsort. The STL's sort functions offer a number of advantages over qsort including:

  • Better theoretical run time: sort is guaranteed to run in O(nlog(n)) time in the worst case whereas C's qsort runs in O(n^2) time in the worst case.
  • Better run time in practice: C's qsort requires a function pointer whereas the second form of sort may take a functor (and the first form in effect always does). Function calls via a function pointer are much less likely to be inlined than functor calls; the compiler tends to do a better job optimizing code using STL's sort.
  • Less code to write: When using C's qsort, you will almost invariably have to write your own comparison function. With STL's sort on the other hand, if the operator < is already defined for your data type, there's no need to do any extra coding. For example, you can sort an array of int in one line: sort(x, x + n).
  • Type-safety: C's qsort requires you to provide a function that takes void*, which in turn requires your code to cast from void*. There is no need to do any casting when writing code to use STL's sort.
This example code sorts an array of C-strings:

#include <cstring> //for strcmp
#include <algorithm> //for sort
#include <iostream>
using namespace std;

class CStringCompare {
   public:
//Return true if s1 < s2; otherwise, return false.
bool operator()(const char* s1, const char* s2) {
    return strcmp(s1, s2) < 0;
}
};

int main(int numberOfArgs, char** args) {
    sort(args, args + numberOfArgs, CStringCompare());
    for (int i = 0; i < numberOfArgs; ++i) {
        cout << args[i] << endl;
    }
    return 0;
}
Here's some example compilation and output:

% g++ sort_arrays.cpp
% ./a.out g e s 3 c a j k b
./a.out
3
a
b
c
e
g
j
k
s
%
David Faden
 
Comment and Contribute

 

 

 

 

 


(Maximum characters: 1200). You have 1200 characters left.

 

 

Sitemap