How to Sort an Stl Vector

Sorting a vector of custom objects

A simple example using std::sort

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}
};

struct less_than_key
{
    inline bool operator() (const MyStruct& struct1, const MyStruct& struct2)
    {
        return (struct1.key < struct2.key);
    }
};

std::vector < MyStruct > vec;

vec.push_back(MyStruct(4, "test"));
vec.push_back(MyStruct(3, "a"));
vec.push_back(MyStruct(2, "is"));
vec.push_back(MyStruct(1, "this"));

std::sort(vec.begin(), vec.end(), less_than_key());

---

Edit: As Kirill V. Lyadvinsky pointed out, instead of supplying a sort predicate, you can implement the operator< for MyStruct:

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}

    bool operator < (const MyStruct& str) const
    {
        return (key < str.key);
    }
};

Using this method means you can simply sort the vector as follows:

std::sort(vec.begin(), vec.end());

Edit2: As Kappa suggests you can also sort the vector in the descending order by overloading a > operator and changing call of sort a bit:

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}

    bool operator > (const MyStruct& str) const
    {
        return (key > str.key);
    }
};

And you should call sort as:

std::sort(vec.begin(), vec.end(),greater<MyStruct>());

How to sort an STL vector?

Overload less than operator, then sort. This is an example I found off the web...

class MyData
{
public:
  int m_iData;
  string m_strSomeOtherData;
  bool operator<(const MyData &rhs) const { return m_iData < rhs.m_iData; }
};

std::sort(myvector.begin(), myvector.end());

Source: here

How to sort a vector containing objects of class in C++?

I'm sure that this has been answered before, but for your specific case;

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>

struct staff {
    int ID;
    std::string Name;
    std::string Class;
};

int main() {
    std::vector <staff> s = { 
        { 234, "Mark", "biology" },
        { 3455, "Mitch", "English" }, 
        { 1234, "Hen", "Maths" }
    };

    std::sort(s.begin(), s.end(), []( const auto& a, const auto& b) { return a.ID < b.ID; });

    for (const auto& staff_member : s) 
        std::cout << staff_member.ID << ": " << staff_member.Name << ", " << staff_member.Class << "\n";

    return 0;
}

This uses the std::sort algorithm from the <algorithm> header, invoked with a comparison function that returns true when a is considered smaller than b.

Sorting an STL vector on two values

You need to combine the two criteria into one.
Heres an example of how you'd sort a struct with a first and second field
based on the first field, then the second field.

#include <algorithm>

struct MyEntry {
  int first;
  int second;
};

bool compare_entry( const MyEntry & e1, const MyEntry & e2) {
  if( e1.first != e2.first)
    return (e1.first < e2.first);
  return (e1.second < e2.second);
}

int main() {
  std::vector<MyEntry> vec = get_some_entries();
  std::sort( vec.begin(), vec.end(), compare_entry );
}

NOTE: implementation of compare_entry updated to use code from Nawaz.

Sorting a vector in descending order

With c++14 you can do this:

std::sort(numbers.begin(), numbers.end(), std::greater<>());

What is the best way to sort a vector leaving the original one unaltered?

Use partial_sort_copy. Here is an example:

vector<int> v{9,8,6,7,4,5,2,0,3,1};
vector<int> v_sorted(v.size());
partial_sort_copy(begin(v), end(v), begin(v_sorted), end(v_sorted));

Now, v remains untouched but v_sorted contains {0,1,2,3,4,5,6,7,8,9}.

I have a list of STL vectors and I want to sort them by the first element of each vector

A small clarification for other answers: the std::vector<T> already has operator< with exactly the same behavior as you described (cplusplus description).

template < class T, class Alloc >
bool operator < (const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs);

Description:

The less-than comparison (operator<) behaves as if using algorithm lexicographical_compare, which compares the elements sequentially using operator< in a reciprocal manner (i.e., checking both a < b and b < a) and stopping at the first occurrence.

So, you can just write

sort(sol.begin(), sol.end());

UP: It's written in the comments that you have an array of std::vector, not std::list<std::vector>. The array has no methods begin() and end(), so this exact code will not work. The solution is

sort(sol, sol + SIZE);

where SIZE is size of the part of the array you want to sort.

Performance gap between sorting a list and a vector of structs. C++

No a std::vector is not sorted using merge sort (in most implementations; the standard doesn't specify the algorithm).

std::list does not have O(1) random access, so it cannot use algorithms like Quick sort* which requires O(1) random access to be fast (this is also why std::sort doesn't work on std::list.)

With this, you'll have to use algorithms that forward iteration is enough, such as the Merge sort**.

And merge sort is typically slower [1][2].

See also: what's the difference between list.sort and std::sort?

*: libstdc++ actually uses introsort.

**: libstdc++ actually uses a variant of merge sort

sorting vector using sets

Copying the data from the vector to the set will be slower, because it will involve creating a data structure on the heap (typically a red-black tree), while sorting can be done in-place (effectively using the stack as a temporary data store).

#include <iostream>
#include <vector>
#include <set>

size_t gAllocs;
size_t gDeallocs;

void * operator new ( size_t sz )   { ++gAllocs; return std::malloc ( sz ); }
void   operator delete ( void *pt ) { ++gDeallocs; return std::free ( pt ); }

int main () {
    gAllocs = gDeallocs = 0;
    std::vector<int> v { 8, 6, 7, 5, 3, 0, 9 };
    std::cout << "Allocations = " << gAllocs << "; Deallocations = " << gDeallocs << std::endl;
    std::set<int> s(v.begin(), v.end());
    std::cout << "Allocations = " << gAllocs << "; Deallocations = " << gDeallocs << std::endl;
    std::sort ( v.begin(), v.end ());
    std::cout << "Allocations = " << gAllocs << "; Deallocations = " << gDeallocs << std::endl;

    return 0;
    }

On my system (clang, libc++, Mac OS 10.8), this prints:

$ ./a.out 
Allocations = 1; Deallocations = 0
Allocations = 8; Deallocations = 0
Allocations = 8; Deallocations = 0

Building the set takes 7 memory allocations (one per entry). Sorting the vector takes none.

---

Related Topics