Sort lists

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 ++
Last edited on
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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";
}
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";
Last edited on
Yes, thanks. Line 15 should have read
if (it != xs.end()) it->count++; else xs.push_back({x, 1});
Last edited on
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:
1
2
std::sort(xs.begin(), xs.end(),
              [] (const auto &x, const auto &y) { return x.first < y.first; });


Last edited on
C++11-style sorting can then be done like this:
1
2
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.
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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
Last edited on
1
2
3
4
5
6
7
8
9
10
11
12
#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}

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.
Last edited on
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.
Last edited on
Registered users can post here. Sign in or register to post.