5

I have a Vec<(A, B)> and I want to group by A but not just consecutive but all elements in the Vec. The closest thing I found is Itertools::group_by which only works on consecutive values. I understand that the consecutiveness is related to optimizing allocation but I just want a regular C# group by. Priority is to not have to use a new library just for this.

A is not hashable, only Ord. I want a resulting Vec<(A, Vec<(A, B))> or equivalent

ditoslav
  • 4,563
  • 10
  • 47
  • 79
  • 1
    As in you have a `Vec<(A, b)>` and you want groups of `B` based on `A`? – Aplet123 Dec 21 '20 at 13:38
  • 3
    Also, what trait implementations are `A` guaranteed to have? If it has `Hash`, then this can be easily done by folding onto a `HashMap>`. – Aplet123 Dec 21 '20 at 13:43
  • 2
    Related: [How to fold using a HashMap as an accumulator?](https://stackoverflow.com/questions/31884309/how-to-fold-using-a-hashmap-as-an-accumulator) Instead of counting, just append to the vector. – Sven Marnach Dec 21 '20 at 13:48
  • 2
    If `A: Ord`, you can also use a `BTreeMap` instead of a `HashMap`. – EvilTak Dec 21 '20 at 13:50
  • 2
    Does "comparable" mean `A: Eq`, `A: Ord`, `A: PartialEq` or `A: PartialOrd`? – Sven Marnach Dec 21 '20 at 13:58
  • it is partial ord – ditoslav Dec 21 '20 at 14:19
  • 1
    @ditoslav With just `PartialOrd`, you don't even have the guarantee that `a == a` for all elements of `A`. It's completely unclear what grouping even means in that context. – Sven Marnach Dec 21 '20 at 14:36
  • guys, I'm new to rust, help me out. As I said, I want something similar to C# group_by. If I need the Eq and I forgot PartialOrd doesn't have it then can't you assume I wanted Org which has it. You don't have to be so hostile – ditoslav Dec 21 '20 at 14:43
  • 4
    @ditoslav Hey, slowly! I really didn't mean to be hostile – it's just that these differences _matter_ for the solution. I already provided an answer for the case that `A: Ord`, but if you only have `A: PartialOrd` this will be useless for you. And regarding "can't you assume I wanted Or[d]", well, that's exactly what I did in the first sentence of my answer. – Sven Marnach Dec 21 '20 at 14:55

1 Answers1

12

Assuming that "comparable" means A: Ord, i.e. that there is a total ordering on A, you can fold an iterator over items of type (A, B) into a BTreeMap from A to Vec<B>:

use std::collections::BTreeMap;

fn group_pairs<A, B, I>(v: I) -> BTreeMap<A, Vec<B>>
where
    A: Ord,
    I: IntoIterator<Item = (A, B)>,
{
    v.into_iter().fold(BTreeMap::new(), |mut acc, (a, b)| {
        acc.entry(a).or_default().push(b);
        acc
    })
}

Some people prefer a for loop over a fold:

fn group_pairs<A, B, I>(v: I) -> BTreeMap<A, Vec<B>>
where
    A: Ord,
    I: IntoIterator<Item = (A, B)>,
{
    let mut result = BTreeMap::<A, Vec<B>>::new();
    for (a, b) in v {
        result.entry(a).or_default().push(b);
    }
    result
}

Example:

let data = vec![(1, 2), (2, 3), (1, 1), (2, 4), (3, 5)];
let grouped = vec![(1, vec![2, 1]), (2, vec![3, 4]), (3, vec![5])];
assert_eq!(group_pairs(data).into_iter().collect::<Vec<_>>(), grouped);
Sven Marnach
  • 574,206
  • 118
  • 941
  • 841
  • 2
    *I want a resulting `Vec<(A, Vec<(A, B))>`* — you may want to touch on why they cannot have that exact type with the requirements they've provided. – Shepmaster Dec 21 '20 at 14:19
  • 1
    See also [How to use a struct's member as its own key when inserting the struct into a map without duplicating it?](https://stackoverflow.com/q/41035869/155423) – Shepmaster Dec 21 '20 at 14:19
  • Thank you for the answer, the fold is extremely succinct while doing exactly what was required – Gyfis Oct 06 '21 at 12:53