resorting ONE value in a sorted vector

MEsc

hello, is it possible to resort only ONE value in a vector?
vor example:

QVector<int> vec  = {1; 4; 6; 15}

and vec[2] changes value to 3.
Then vec would be {1; 4; 3; 15}

But I want the correct order.

So thats the easy part. In reality I have for example

QVector<QString> vec  = {0 - 1; 1 - 4; 2 - 6; 3 - 15}

and vec[2] -> 2 - 6 -> should change the 6 to 3.
Then vec would be {0 - 1; 1 - 4; 2 - 3; 3 - 15}

But I want that the Vector will be sortet by last element
last element begins when there is the second whitespace.

As result vec should be {0 - 1; 2 - 3; 1 - 4; 3 - 15}

mchinand

I think you could use std::upper_bound with a custom comparison operator to handle your data and then use QVector::move().

Chris Kawa

It should rather be std::lower_bound. Anyway, both of these work on a partitioned range, so you have to first take the changed element out, otherwise the precondition is not satisfied. Put it back in afterwards to where std::lower_bound points to.

Paul Colby

@MEsc said in resorting ONE value in a sorted vector:

But I want that the Vector will be sortet by last element
last element begins when there is the second whitespace.

One example:

        qDebug() << "before" << vec;
        std::sort(vec.begin(), vec.end(), [](const QString &a, const QString &b){
            const QStringList aParts = a.split(QLatin1Char(' '));
            const QStringList bParts = b.split(QLatin1Char(' '));
            return (aParts.size() == 3) && (bParts.size() == 3) &&
                   (aParts.at(2).toInt() < bParts.at(2).toInt());
        });
        qDebug() << "sorted" << vec;

Output:

before QVector("0 - 1", "1 - 4", "2 - 3", "3 - 15")
sorted QVector("0 - 1", "2 - 3", "1 - 4", "3 - 15")

Cheers.

Chris Kawa

@Paul-Colby Please don't use split for such things. It's sorting, so the lambda is gonna be executed many times. Each time you do two splits and each split is an allocation of a list and a bunch of allocations and copy of strings. It's super wasteful.

If you really have to do a read-only split use a QStringView. It still allocates a list, but does not have to copy substrings.

In this case you don't need to split the string at all. Just use a.lastIndexOf(' ')to get the position of the second number, make a QStringView and do toInt() on that. Avoids all dynamic allocations.

Paul Colby

Thanks @Chris-Kawa, but I'll have to respectively disagree :)

Although I do agree with your suggestion in general (it is indeed likely to be faster), that's also a form of premature optimisation. Since my example was just one possible solution, intended for inspiration only, I optimised for readability and correctness. If the vector is typically ~4 items (we don't actually know yet), then a simple easier-to-read example is a good place to start (not necessarily a final implementation).

In this case you don't need to split the string at all. Just use a.lastIndexOf(' ')

You're suggestion is actually incorrect - while it works for the example inputs provided, it doesn't actually match the stated requirement of "last element begins when there is the second whitespace." Of course, your assumption about the intention might be correct, but it is just an assumption. Thus, if I was optimising for performance, I would have gone with something more like:

const int pos = a.indexOf(' ', a.indexOf(' ')); // Find the second space (if any).

But of course, if performance really mattered, I would be recommending to either change the QVector<QString> to something like QVector<QPair<int,int>> instead, if possible.

Anyway, all of those thoughts (yours and mine) are good for @MEsc to ponder I reckon :)

Cheers.

JonB

@Paul-Colby said in resorting ONE value in a sorted vector:

const int pos = a.indexOf(' ', a.indexOf(' ')); // Find the second space (if any).

Hi Paul. Good for sticking up for yourself in this discussion! However, although to be fair you only said "something more like" your code above is not going to find a second space! It will re-find the first space :) I think you intended:

const int pos = a.indexOf(' ', a.indexOf(' ') + 1); // Find the second space (if any).

This also has the advantage that it does not exhibit "undefined behaviour" if there is no space at all in the string, I don't know what would happen (docs don't say) if your tried calling a.indexOf(' ', a.indexOf(' ')) => a.indexOf(' ', -1), might give an "out of range".

MEsc

@Paul-Colby I have solved this problem with vector pair thanks.

Chris Kawa

@Paul-Colby "Premature optimization" is a term I grew to really dislike, because nowadays it's often used to simply excuse bad code. And please don't get offended, but I consider what you proposed a bad code. I'd call this "premature pessimization". There's this notion that code that performs well is somehow doomed to be unreadable. I politely disagree. Getting in habit of writing performant code by default also trains you in writing it in a way that doesn't sacrifice readability. Without that training yes - one tends to create unreadable technical debt when they are forced to optimize something.

You're suggestion is actually incorrect

That's just nitpicking. Technically your solution is incorrect too, because it only does comparison if split produces exactly 3 parts i.e. string has two spaces. What if it had more?. See how that works? Nitpicking. I don't treat forum posts as technical specification and OP's intent was quite clear here. In reality that's something you would clarify with the requester probably in one sentence.
You can see from OP's last response they have no problem adjusting the format. Now they probably copied your solution and there's just one more piece of software floating out there that is unnecessarily slow and resource intensive.

Oh well, life.

Chris Kawa

Btw. to put my money where my mouth is this is my proposal for this problem. Yes, I'm assuming the format is fixed and search operations won't return -1. If that isn't the case you can add one if to range check the indices.

std::ranges::sort(vec, [](QStringView a, QStringView b)
{
    int pos_a = a.lastIndexOf(' ');
    int pos_b = b.lastIndexOf(' ');

    int int_a = a.sliced(pos_a).toInt();
    int int_b = b.sliced(pos_b).toInt();

    return int_a < int_b;
});

Do you consider this unreadable? And no, this is not fully optimized either, because it does the same int conversions multiple times, but I consider something like this to be a "good enough starting point" and in-depth optimization is possible if need arises e.g. by caching the conversions or changing the data structure.

EDIT Just after posting I realized you can do the QStringView creation right in the params, so even simpler.