Unable to apply std::sort to a list of structs

Question

I am having trouble using std::sort to sort a std::list of struct. My setup is as follows.

Macbook Air, Apple M2
g++
- Apple clang version 14.0.3 (clang-1403.0.22.14.1)
- Target: arm64-apple-darwin22.4.0
- Thread model: posix
- InstalledDir: /Library/Developer/CommandLineTools/usr/bin

Here are the various things I have tried according to SO posts here, here, here and the documentation.

Option 1, use lambda.

#include <list>
#include <algorithm>

struct _item {
    int age;
    int weight;

};

int main() {
    std::list<_item> items {
        {34, 155},
        {16, 125}
    };

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

Option 2, use a struct function object.

#include <list>
#include <algorithm>

struct _item {
    int age;
    int weight;
};

int main() {
    std::list<_item> items {
        {34, 155},
        {16, 125}
    };

    struct
    {
        bool operator()(const _item& a, const _item& b) const { 
            return a.age < b.age; 
        }
    } comparator;

    std::sort(items.begin(), items.end(), comparator);
}

Option 3, overload the < operator in the struct.

#include <list>
#include <algorithm>

struct _item {
    int age;
    int weight;

    bool operator<(const _item& b) const {
        return age < b.age; 
    }
};

int main() {
    std::list<_item> items {
        {34, 155},
        {16, 125}
    };

    std::sort(items.begin(), items.end());
}

Option 4, create a static method.

#include <list>
#include <algorithm>

struct _item {
    int age;
    int weight;
};

static bool comparator(const _item& a, const _item& b) {
    return a.age < b.age; 
}

int main() {
    std::list<_item> items {
        {34, 155},
        {16, 125}
    };

    std::sort(items.begin(), items.end(), comparator);
}

In VS Code with the C++ plugin/extension, there are absolutely no errors/warnings flagged.

When I compile these programs, I use the follow the form below.

g++ -std=c++17 do-sort.cpp -o do-sort.out

I can't say all the errors are the same, but they appear to be. None of these programs compile although they seem fine according to VS Code and the documentations. Here's the error during compilation for the first program using lambda.

g++ -std=c++17 do-sort-a.cpp -o do-sort-a.out
In file included from do-sort-a.cpp:1:
In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/list:207:
In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/algorithm:1760:
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/make_heap.h:33:32: error: invalid operands to binary expression ('std::__list_iterator' and 'std::__list_iterator')
  difference_type __n = __last - __first;
                        ~~~~~~ ^ ~~~~~~~
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/partial_sort.h:39:8: note: in instantiation of function template specialization 'std::__make_heap>' requested here
  std::__make_heap(__first, __middle, __comp);
       ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/partial_sort.h:67:27: note: in instantiation of function template specialization 'std::__partial_sort_impl, std::__list_iterator>' requested here
  auto __last_iter = std::__partial_sort_impl(__first, __middle, __last, static_cast(__comp));
                          ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/sort.h:681:10: note: in instantiation of function template specialization 'std::__partial_sort, std::__list_iterator>' requested here
    std::__partial_sort(__first, __last, __last, __comp);
         ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/sort.h:694:8: note: in instantiation of function template specialization 'std::__sort_impl, (lambda at do-sort-a.cpp:16:43)>' requested here
  std::__sort_impl(std::move(__first), std::move(__last), __comp);
       ^
do-sort-a.cpp:16:10: note: in instantiation of function template specialization 'std::sort, (lambda at do-sort-a.cpp:16:43)>' requested here
    std::sort(items.begin(), items.end(), [](const _item& a, const _item& b) {
         ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__iterator/move_iterator.h:283:6: note: candidate template ignored: could not match 'move_iterator' against '__list_iterator'
auto operator-(const move_iterator& __x, const move_iterator& __y)
     ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__iterator/reverse_iterator.h:296:1: note: candidate template ignored: could not match 'reverse_iterator' against '__list_iterator'
operator-(const reverse_iterator& __x, const reverse_iterator& __y)
^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__iterator/wrap_iter.h:245:6: note: candidate template ignored: could not match '__wrap_iter' against '__list_iterator'
auto operator-(const __wrap_iter& __x, const __wrap_iter& __y) _NOEXCEPT
     ^
In file included from do-sort-a.cpp:1:
In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/list:207:
In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/algorithm:1760:
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/make_heap.h:37:72: error: invalid operands to binary expression ('std::__list_iterator' and 'difference_type' (aka 'long'))
        std::__sift_down(__first, __comp_ref, __n, __first + __start);
                                                               ~~~~~~~ ^ ~~~~~~~
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__iterator/move_iterator.h:310:1: note: candidate template ignored: could not match 'move_iterator' against 'difference_type' (aka 'long')
operator+(typename move_iterator::difference_type __n, const move_iterator& __x)
^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__iterator/reverse_iterator.h:314:1: note: candidate template ignored: could not match 'reverse_iterator' against 'difference_type' (aka 'long')
operator+(typename reverse_iterator::difference_type __n, const reverse_iterator& __x)
^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__iterator/wrap_iter.h:259:21: note: candidate template ignored: could not match '__wrap_iter' against 'difference_type' (aka 'long')
__wrap_iter operator+(typename __wrap_iter::difference_type __n, __wrap_iter __x) _NOEXCEPT
                    ^
In file included from do-sort-a.cpp:1:
In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/list:207:
In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/algorithm:1774:
In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/nth_element.h:15:
In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/sort.h:16:
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/partial_sort.h:41:85: error: invalid operands to binary expression ('std::__list_iterator' and 'std::__list_iterator')
  typename iterator_traits::difference_type __len = __middle - __first;
                                                                           ~~~~~~~~ ^ ~~~~~~~
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/partial_sort.h:67:27: note: in instantiation of function template specialization 'std::__partial_sort_impl, std::__list_iterator>' requested here
  auto __last_iter = std::__partial_sort_impl(__first, __middle, __last, static_cast(__comp));
                          ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/sort.h:681:10: note: in instantiation of function template specialization 'std::__partial_sort, std::__list_iterator>' requested here
    std::__partial_sort(__first, __last, __last, __comp);
         ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/sort.h:694:8: note: in instantiation of function template specialization 'std::__sort_impl, (lambda at do-sort-a.cpp:16:43)>' requested here
  std::__sort_impl(std::move(__first), std::move(__last), __comp);
       ^
do-sort-a.cpp:16:10: note: in instantiation of function template specialization 'std::sort, (lambda at do-sort-a.cpp:16:43)>' requested here
    std::sort(items.begin(), items.end(), [](const _item& a, const _item& b) {
         ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__iterator/move_iterator.h:283:6: note: candidate template ignored: could not match 'move_iterator' against '__list_iterator'
auto operator-(const move_iterator& __x, const move_iterator& __y)
     ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__iterator/reverse_iterator.h:296:1: note: candidate template ignored: could not match 'reverse_iterator' against '__list_iterator'
operator-(const reverse_iterator& __x, const reverse_iterator& __y)
^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__iterator/wrap_iter.h:245:6: note: candidate template ignored: could not match '__wrap_iter' against '__list_iterator'
auto operator-(const __wrap_iter& __x, const __wrap_iter& __y) _NOEXCEPT
     ^
In file included from do-sort-a.cpp:1:
In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/list:207:
In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/algorithm:1774:
In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/nth_element.h:15:
In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/sort.h:16:
In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/partial_sort.h:17:
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/sort_heap.h:34:37: error: invalid operands to binary expression ('std::__list_iterator' and 'std::__list_iterator')
  for (difference_type __n = __last - __first; __n > 1; --__last, (void) --__n)
                             ~~~~~~ ^ ~~~~~~~
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/partial_sort.h:52:8: note: in instantiation of function template specialization 'std::__sort_heap>' requested here
  std::__sort_heap(std::move(__first), std::move(__middle), __comp);
       ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/partial_sort.h:67:27: note: in instantiation of function template specialization 'std::__partial_sort_impl, std::__list_iterator>' requested here
  auto __last_iter = std::__partial_sort_impl(__first, __middle, __last, static_cast(__comp));
                          ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/sort.h:681:10: note: in instantiation of function template specialization 'std::__partial_sort, std::__list_iterator>' requested here
    std::__partial_sort(__first, __last, __last, __comp);
         ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/sort.h:694:8: note: in instantiation of function template specialization 'std::__sort_impl, (lambda at do-sort-a.cpp:16:43)>' requested here
  std::__sort_impl(std::move(__first), std::move(__last), __comp);
       ^
do-sort-a.cpp:16:10: note: in instantiation of function template specialization 'std::sort, (lambda at do-sort-a.cpp:16:43)>' requested here
    std::sort(items.begin(), items.end(), [](const _item& a, const _item& b) {
         ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__iterator/move_iterator.h:283:6: note: candidate template ignored: could not match 'move_iterator' against '__list_iterator'
auto operator-(const move_iterator& __x, const move_iterator& __y)
     ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__iterator/reverse_iterator.h:296:1: note: candidate template ignored: could not match 'reverse_iterator' against '__list_iterator'
operator-(const reverse_iterator& __x, const reverse_iterator& __y)
^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__iterator/wrap_iter.h:245:6: note: candidate template ignored: could not match '__wrap_iter' against '__list_iterator'
auto operator-(const __wrap_iter& __x, const __wrap_iter& __y) _NOEXCEPT
     ^
In file included from do-sort-a.cpp:1:
In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/list:207:
In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/algorithm:1774:
In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/nth_element.h:15:
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/sort.h:621:54: error: invalid operands to binary expression ('std::__list_iterator' and 'std::__list_iterator')
  difference_type __depth_limit = 2 * __log2i(__last - __first);
                                              ~~~~~~ ^ ~~~~~~~
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/sort.h:687:10: note: in instantiation of function template specialization 'std::__sort>' requested here
    std::__sort(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __wrapped_comp);
         ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__algorithm/sort.h:694:8: note: in instantiation of function template specialization 'std::__sort_impl, (lambda at do-sort-a.cpp:16:43)>' requested here
  std::__sort_impl(std::move(__first), std::move(__last), __comp);
       ^
do-sort-a.cpp:16:10: note: in instantiation of function template specialization 'std::sort, (lambda at do-sort-a.cpp:16:43)>' requested here
    std::sort(items.begin(), items.end(), [](const _item& a, const _item& b) {
         ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__iterator/move_iterator.h:283:6: note: candidate template ignored: could not match 'move_iterator' against '__list_iterator'
auto operator-(const move_iterator& __x, const move_iterator& __y)
     ^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__iterator/reverse_iterator.h:296:1: note: candidate template ignored: could not match 'reverse_iterator' against '__list_iterator'
operator-(const reverse_iterator& __x, const reverse_iterator& __y)
^
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__iterator/wrap_iter.h:245:6: note: candidate template ignored: could not match '__wrap_iter' against '__list_iterator'
auto operator-(const __wrap_iter& __x, const __wrap_iter& __y) _NOEXCEPT
     ^
5 errors generated.

Any ideas what's going on?

[`std::sort`](https://en.cppreference.com/w/cpp/algorithm/sort) needs random access iterators: _"...RandomIt must meet the requirements of ValueSwappable and LegacyRandomAccessIterator...."_. [`std::list`](https://en.cppreference.com/w/cpp/container/list) is not random access container and does not provide random access iterators only bidirectional iterators. — Richard Critten, May 09 '23 at 00:46
yikes. what's an alternative container? vector? I'm coming from the java mothership so i shy away from vector. — Jane Wayne, May 09 '23 at 00:49
If you still want to use `std::list`, [`std::list::sort`](https://en.cppreference.com/w/cpp/container/list/sort). — user4581301, May 09 '23 at 00:58
If you want something like an array and know the size at compile time, `std::array`. If you want something like an array and don't know the size at compile time , `std::vector`. If you want something like a doubly linked list, `std::list`. Singly linked list, `std::forward_list`. Hash table, `std::unordered_map`. Smurf it. Here's the whole shebang: https://en.cppreference.com/w/cpp/container . Watch out for `std::vector` because it's a packed bit array and behaves a bit oddly. `std::bitset` is also useful, but technically not a container. — user4581301, May 09 '23 at 01:11
Side note: it's good to familiarize yourself with the [Iterator Invalidation Rules](https://stackoverflow.com/questions/6438086/iterator-invalidation-rules-for-c-containers). A lot of people dropping into C++ from other languages, especially the garbage-collected ones, trip over holding a reference or iterator after a iterator-nuking modification to the container. — user4581301, May 09 '23 at 01:17

Unable to apply std::sort to a list of structs

0 Answers0