CODEWITHSUNDEEP
c++sortingc++11std
Chiel
Chiel

Reputation: 6194

Fastest way to sort a data structure in C++

I have a data structure that consists of three int values that represent a coordinate, and a double that represents a value at that coordinate. I would like to store them together, and sort them on value. Values are not unique. Right now, I have them in a struct and I sort them using a lambda, as is shown in the code below. As this is a piece of performance-critical code, I am looking for an implementation that gives the fastest sorting. The list will contain 10^6 to 10^7 elements.

What is the most elegant way to solve this? I am not trying to use std::sort, but I am mostly asking whether to store the data in a struct is the best solution, or are there better alternatives?

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

struct Data
{
    int i;
    int j;
    int k;
    double d;
};

int main()
{
    std::vector<Data> v;

    v.push_back({1,2,3,0.6});
    v.push_back({1,2,3,0.2});
    v.push_back({1,2,3,0.5});
    v.push_back({1,2,3,0.1});
    v.push_back({1,2,3,0.4});

    std::sort(v.begin(), v.end(), [](const Data& a, const Data& b)
            { return a.d < b.d; });

    for (auto d : v)
        std::cout << d.i << ", " << d.j << ", "
                  << d.k << ", " << d.d << std::endl;

    return 0;
}

Upvotes: 1

Views: 6074

Answers (2)

Taywee
Taywee

Reputation: 1335

The fastest way to sort them is to not have to sort them.

At the expense of some slightly slower insertion, you could store your entire container sorted, and insert only in the correct place. A std::set could help you here, or you could roll your own.

edit: A std::multiset would provide the same advantages if you need to allow values that compare equal.

Upvotes: 2

Michael Brown
Michael Brown

Reputation: 498

Duplicate Question, Fastest way to search and sort vectors is a far better answer than I could give.

Summary,
You need a better sample set, 5 entries isn't going to tell you anything. You're not going to be able to beat std::sort. In particular to you, the floating point compare will be the painful bit.

Upvotes: 0

Related Questions