How to Use Std::Sort to Sort an Array in C++

How to use std::sort to sort an array in C++

In C++0x/11 we get std::begin and std::end which are overloaded for arrays:

#include <algorithm>

int main(){
  int v[2000];
  std::sort(std::begin(v), std::end(v));
}

If you don't have access to C++0x, it isn't hard to write them yourself:

// for container with nested typedefs, non-const version
template<class Cont>
typename Cont::iterator begin(Cont& c){
  return c.begin();
}

template<class Cont>
typename Cont::iterator end(Cont& c){
  return c.end();
}

// const version
template<class Cont>
typename Cont::const_iterator begin(Cont const& c){
  return c.begin();
}

template<class Cont>
typename Cont::const_iterator end(Cont const& c){
  return c.end();
}

// overloads for C style arrays
template<class T, std::size_t N>
T* begin(T (&arr)[N]){
  return &arr[0];
}

template<class T, std::size_t N>
T* end(T (&arr)[N]){
  return arr + N;
}

Can I sort C-style array (in my case of struct) using std::sort?

You can use std::begin and std::end to determine the start and end points of your array, assuming you are on C++11.

So:

int someArray[10]
std::sort(std::begin(someArray), std::end(someArray));

Using std::sort to sort an array of C strings

std::sort: The comparison object expected by it has to return ​true if the first argument is less than (i.e. is ordered before) the second.

strcmp, the function you provided has another return convention:

• Negative value if lhs is less than rhs.
• ​0​ if lhs is equal to rhs.
• Positive value if lhs is greater than rhs.

_{(here lhs and rhs reffer to left hand operator and right hand operator)}

So you have to create your own wrapper function around strcmp.

If you could use c++11 and if you could use c++ for real (i.e. std::string and std::vector) you can use other cool tricks like lambdas.

---

The classic solution:

bool cmp(char const *lhs, char const *rhs) {
  return strcmp(lhs, rhs) < 0;
}

std::sort(tab, tab + n, cmp);

The lambda solution:

std::sort(tab, tab + n, [](char const *lhs,
                           char const *rhs) { return strcmp(lhs, rhs) < 0; });

The real C++ solution

std::vector<std::string> v = ...;

std::sort(std::begin(v), std::end(b));

Sort 2 dimensional c array with std::sort

Maybe there is some way to turn it into a std::array without copying
it?

Perhaps not turning into a std::array per se, but an alternative approach might be to cast the 2D C-style arrays into a std::array reference just for the sorting. Doing so in reliance on the standard saying an std::array representation in memory at least begins with its C-style array equivalent. See here under [array.overview§2]:

An array is an aggregate that can be list-initialized with up to N
elements whose types are convertible to T.

In practice, the following usage of reinterpret_cast is most probably safe, but do note that unless there is a special exception for it somewhere in the standard, it would formally be undefined behaviour:

#include <algorithm>
#include <array>
#include <iostream>

int main() {
  auto two_dim_less = [](std::array<int, 2>& a, std::array<int, 2>& b) {
      return a[1] < b[1]; };

  int two_dim[][2] = {{1, 8}, {2, 4}, {3, 10}, {4, 40}, {5, 1}};

  std::array<std::array<int, 2>, 5>& arr =
    *reinterpret_cast<std::array<std::array<int, 2>, 5>*>(&two_dim);

  std::sort(arr.begin(), arr.end(), two_dim_less);

  for (int i = 0; i < 5; i++)
    std::cout << two_dim[i][0] << ", " << two_dim[i][1] << '\n';

  return 0;
}

Output:

5, 1
2, 4
1, 8
3, 10
4, 40

---

Regarding the use of std::qsort(), note that it is potentially slower than std::sort() due to the latter allowing to inline the comparisons while the former doesn't.

How to sort a standard array in descending order - C++ 11

Unlike the raw arrays, std::array won't convert to pointer implicitly (even you can get the pointer explicitly from std::array::data), you should use begin() and end(), which are commonly used to get iterators from STL containers. e.g.

sort(myArray.begin(), myArray.end(), greater<int>());

or

sort(std::begin(myArray), std::end(myArray), greater<int>());

PS: The latter works with raw arrays too.

Sorting a C 2D array via std::sort

The problem is not in iterating a 2D array. Provided the columns size is a constexpr value, pointers to arrays are nice iterators.

But all C++ sort (or mutating) algorithms require the underlying type to be move constructible and move assignable and an array is not assignable. But wrapping the underlying arrays can be enough:

template <class T, int sz>
class wrapper {
    T* base;
    bool own;            // a trick to allow temporaries: only them have own == true
public:
    // constructor using a existing array
    wrapper(T* arr): base(arr), own(false) {}

    ~wrapper() {              // destructor
        if (own) {
            delete[] base;    // destruct array for a temporary wrapper
        }
    }
    // move constructor - in fact copy to a temporary array
    wrapper(wrapper<T, sz>&& src): base(new T[sz]), own(true) {
        for(int i=0; i<sz; i++) {
            base[i] = src.base[i];
        }
    }
    // move assignment operator - in fact also copy
    wrapper<T, sz>& operator = (wrapper<T, sz>&& src) {
        for(int i=0; i<sz; i++) {
            base[i] = src.base[i];
        }
        return *this;
    }
    // native ordering based on lexicographic string order
    bool operator < (const wrapper<T, sz>& other) const {
        return std::char_traits<char>::compare(base, other.base, sz) < 0;
    }
    const T* value() const {    // access to the underlying string for tests
        return base;
    }
};

Then, you can sort a C compatible 2D array with any C++ sort algo:

std::vector<wrapper<char, 40> > v { &arr[0], &arr[sz] };  // pointer are iterators...
std::sort(v.begin(), v.end());                            // and that's all!

for (int i=0; i<sz; i++) {                                // control
    std::cout << arr[i] << std::endl;
}

The overhead is a vector of structures containing a pointer and a bool, but what is sorted is actually the original 2D array.

Of course, as the C library is accessible from C++, qsort would certainly be easier for sorting a C compatible 2D array. But this way allows the use of stable_sort or partial_sort if they are relevant.

How to use std::sort to sort an array in a 'custom' way, in place

Something like this:

struct A
{
    float x, y, z, w;

    bool operator < (const A &other) const
    {
        return z < other.z;
    }
};

enum { N = 1000 };
float v[4 * N];
...
A *w = reinterpret_cast<A*>(v);
sort(w, w + N);

---

Related Topics