Sort lists

[Geckoo]

Hello everyone.

I have a question about lists. I have an empty list A which I populate with integers according to an external computation. When the process finds a new integer which is not in the list A, it adds it in A and, in a second list (B), it creates at the same index an integer for the previous integer's occurrence. So it starts with 0 and increment B[index]++ when process finds an integer which exists in A. At the end, lists can be like this :

List A = {4, 2, 8, 6}
List B = {2, 3, 4, 1}

So it means that the process found ;
2 times an integer 4,
3 times an integer 2,
4 times an integer 8
and 1 time an integer 6.

Before the output, I want to sort integers in the list A, but (and this is my question) I would like that B could imitate A because of I sorted A, so B is no more exact according to new A values' indexes.

List A = {2, 4, 6, 8} <- sorted list
List B = {2, 3, 4, 1} <- how to sort it according to new A

Do you have an idea how I should develop this function ? Thank you for your help. I wish you the best ++

[mbozzi]

Combine the list of integers and the list of their frequencies into a single data structure.

Also I'm obliged to tell you not to use linked lists unless you have a reason to do so.

#include <list>
#include <iostream>
#include <algorithm>

struct value_count { int value, count; };
bool operator<(value_count a, value_count b) { return a.value < b.value; } 

int main()
{
  std::list<value_count> xs;
  
  for (int x; std::cin >> x; )
  {
    auto const it = std::find_if(xs.begin(), xs.end(), [x](value_count a) { return a.value == x; });
    if (it != xs.end()) it->count++; else xs.push_back({x, 0});
  }
  
  xs.sort();
  
  for (value_count x: xs) std::cout << x.value << " occurred " << x.count << " time(s).\n";
}

[Geckoo]

Thank you mbozzi for you explanation. It seems really interesting and more efficient than my previous code. However I tested your code and it does not work as expected. There is something wrong with the occurrences. The final output is wrong ++

PS : Quickly I found a way, but I don't know if my fix is the better way (x.count + 1) :

for (value_count x : xs) std::cout << x.value << " occurred " << x.count + 1<< " time(s).\n";

[mbozzi]

Yes, thanks. Line 15 should have read
if (it != xs.end()) it->count++; else xs.push_back({x, 1});

[kigar64551]

Just wanted to add:

Alternatively you could use std::pair instead of defining a custom struct:
std::list<std::pair<int,int>> xs;

C++11-style sorting can then be done like this:

std::sort(xs.begin(), xs.end(),
              [] (const auto &x, const auto &y) { return x.first < y.first; });

[mbozzi]

C++11-style sorting can then be done like this:

std::sort(xs.begin(), xs.end(),
              [] (const auto &x, const auto &y) { return x.first < y.first; });

std::list<std::pair<int, int>> cannot be sorted using std::sort because its iterators do not satisfy LegacyRandomAccessIterator.
https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator

Alternatively you could use std::pair instead of defining a custom struct

I chose not to use pair because the member names value and count leave less to be inferred from context than first and second. Additionally, value_count is much less complicated than std::pair - its behavior holds no surprises.

An argument in pair<int, int>'s favor is that it supports all six comparison operators out of the box, and that its associated operator< predictably implements a strong total order.

[kigar64551]

mbozzi wrote:

std::list<std::pair<int, int>> cannot be sorted using std::sort because its iterators do not satisfy LegacyRandomAccessIterator.

This code seems to be working for me though:

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

int main() {
    std::vector<std::pair<int, int>> list = { {12, 1}, {32, 2}, {6, 3}, {43, 4} };

    std::sort(list.begin(), list.end(),
        [](const auto& x, const auto& y) { return x.first < y.first; });

    for (auto iter = list.cbegin(); iter != list.cend(); ++iter)
    {
        std::cout << '{' << iter->first << ',' << iter->second << '}' << std::endl;
    }
}

(tested in MSVC 2022)


IMO, std::vector almost always is preferred over a linked-list (std::list) anyway.

Phillip Johnston wrote:

General Rules of Thumb

There are some general rules of thumb that will guide you through most situations:

- Use sequential containers when you need to access elements by position
- Use std:vector as your default sequential container
- If you add or remove elements frequently at both the front and back of a container, use std::deque
- Use a std::list (not std::deque) iff you need to insert/remove elements in the middle of the sequence
- Do not use std::list if you need random access to objects

[seeplus]

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

int main() {
	std::vector<std::pair<int, int>> list {{12, 1}, {32, 2}, {6, 3}, {43, 4}};

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

	for (const auto& [no1, no2] : list)
		std::cout << '{' << no1 << ',' << no2 << '}' << '\n';
}

{6,3}
{12,1}
{32,2}
{43,4}

[mbozzi]

This code seems to be working for me though

Okay, but that program sorts a std::vector, not a std::list.

OP did say "list", though it might not have been deliberate.

[kigar64551]

OP did say "list", though it might not have been deliberate.

As mentioned above, one should probably use std::vector as the default "list" (sequence container) implementation and only resort to std::deque or std::list when actually required for specific reason.