8
\$\begingroup\$

Let's say that we have a list of strings and we want to find the steps (pair representing swaps to be made) to sort it. Here is my current implementation:

#include <algorithm>
#include <unordered_map>
#include <vector>

auto is_lexicographically_ordered = [](const std::string &s1, const std::string &s2) {
    return std::lexicographical_compare(s1.begin(), s1.end(), s2.begin(), s2.end());
};

std::vector<std::pair<std::string, std::string>> find_unsorted(const std::vector<std::string> &list) {
    std::vector<std::string> cpy(list);
    std::vector<std::string> sorted(list);
    std::vector<std::pair<std::string, std::string>> result;

    std::sort(sorted.begin(), sorted.end(), is_lexicographically_ordered);

    // Cache indices for faster retrieval in loop
    auto index_in_cpy = std::unordered_map<std::string, int>();

    for (int i = 0; i < cpy.size(); ++i)
        index_in_cpy.insert({cpy.at(i), i});

    // Find mistmatched between sorted and current list
    auto it = std::mismatch(cpy.begin(), cpy.end(), sorted.begin());

    while (it.first != cpy.end()) {
        result.push_back(std::make_pair(*it.first, *it.second));

        auto new_it = cpy.begin() + index_in_cpy.at(*it.second);

        std::iter_swap(it.first, new_it);
        it = std::mismatch(++it.first, cpy.end(), ++it.second);
    }

    // Merging paths because for { c, a, b, d }, we would get { c, a }, { c, b } and { c, d }
    // but we only need to move c after d
    auto u = std::unique(result.rbegin(), result.rend(), [](const auto &p1, const auto &p2) {
        return p1.first == p2.first;
    });
    result.erase(result.begin(), u.base());

    return result;
}

and here is an example on how to run it:

int main(int argc, char const *argv[]) {
    for (auto &item : find_unsorted({ "a", "c", "b", "d" })) {
        std::cout << "(" << item.first << ", " << item.second << ")" << std::endl;
    }
    return 0;
}

Any feedback on how to improve runtime or storage space is welcome. Also, if you have more modern way of writing this (eg: range, etc.), feel free to recommend.

\$\endgroup\$
0

3 Answers 3

7
\$\begingroup\$
  1. Avoid copies of complex/big objects, especially if it involves a heap-allocation or anything similarly expensive.

    Just sort a list of indices.

  2. Use views (std::span) instead of constant references. It results in a more flexible interface without additional cost.

  3. Are you sure you want to return copies of pairs of objects, instead of indices?

\$\endgroup\$
0
6
\$\begingroup\$

I recommend you use the Ranges functions where appropriate. For example, compare

    std::sort(sorted.begin(), sorted.end(), is_lexicographically_ordered);

with

    std::ranges::sort(sorted, is_lexicographically_ordered);

The latter is easier to read and understand.


Why do we need is_lexicographically_ordered() anyway? That seems to be exactly the same as the default (std::less<std::string>). The name is misleading; I expect any is_x() to be a predicate, i.e. returning bool.


Consider generating the list as you do the sorting (by recording the swaps you make as you sort), rather than calling std::sort() and then looking to see what's moved. That might be easiest with insertion sort or similar.

\$\endgroup\$
2
  • \$\begingroup\$ Is using ranges simply for writing more modern c++ or there are other reasons ? For the generating list, could you give more details ? \$\endgroup\$ Jan 31, 2023 at 11:08
  • 3
    \$\begingroup\$ Ranges code is often shorter and easier to read; that's why I recommend it. \$\endgroup\$ Jan 31, 2023 at 11:34
1
\$\begingroup\$

Make it more generic

Your function will work for std::vectors of std::strings, but what if you want to sort a regular array of ints? Or a std::deque of std::chrono::time_points? You can do this by turning your function into a template.

It also helps to look at the declaration of std::ranges::sort(), and copy most of it. You might want to keep the first parameter a const reference, and of course the return value should still be a container of swaps. I'd start with:

template<std::ranges::random_access_range R,
         class Comp = std::ranges::less,
         class Proj = std::identity>
requires std::sortable<std::ranges::iterator_t<R>, Comp, Proj>
auto find_unsorted(const R& list, Comp comp = {}, Proj proj = {}) {
    …
}

It doesn't require that many changes to make your function work with that. It helps to make an alias for the type of values the list holds:

using value_type = typename R::value_type;

And then you can copy the input and create the vector holding the output like so:

auto cpy = list;
auto sorted = list;
auto result = std::vector<std::pair<value_type, value_type>>();

Then you pass the parameters on to std::ranges::sort():

std::ranges::sort(list, comp, proj);

This gives you a lot of benefits: the caller can now decide to pass a custom comparison and/or projection function, and it can pass any kind of container that can be sorted.

Avoid making copies

A big problem with your function is that it makes lots of copies of the contents of list: cpy and sorted are two obvious copies, but index_in_cpy and result also contain copies of values stored in list. If the strings (or whatever type the values are) are very large, that will waste a lot of memory, and cost CPU cycles to copy.

Ideally, you will not make any copies of the elements in list. You can do this, for example, by having sorted store iterators into list, and then sort it using a custom projection function that returns the value pointed to by the iterator. That way it will still sort the iterators the way you want.

At the end you should have result hold pairs of iterators into list. The caller can then dereference them if they want to access the values pointed to.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.