如何在Rust中对已排序Vec实现`uniq -c`功能并遍历计数与值

方案1：先统计后遍历（简单直观） #

如果你的Vec是有序的（连续重复元素相邻），可以先一次性统计所有连续元素的出现次数，再通过Vec的迭代器实现正向/反向遍历：

fn main() {
    let a = vec![1, 1, 2, 3, 3, 3];
    
    // 统计连续元素的计数
    let counts = count_consecutive(a.iter());
    
    // 正向遍历
    for (&value, count) in &counts {
        println!("{value}\t{count}");
        // 输出：
        // 1	2
        // 2	1
        // 3	3
    }
    
    // 反向遍历
    for (&value, count) in counts.iter().rev() {
        println!("{value}\t{count}");
        // 输出：
        // 3	3
        // 2	1
        // 1	2
    }
}

// 统计连续重复元素的函数，接收迭代器返回值与计数的Vec
fn count_consecutive<I>(mut iter: I) -> Vec<(I::Item, usize)>
where
    I: Iterator,
    I::Item: PartialEq,
{
    let mut result = Vec::new();
    
    // 取出第一个元素作为初始值
    let Some(mut current_val) = iter.next() else {
        return result;
    };
    let mut current_count = 1;
    
    for val in iter {
        if val == current_val {
            current_count += 1;
        } else {
            result.push((current_val, current_count));
            current_val = val;
            current_count = 1;
        }
    }
    
    // 加入最后一组元素
    result.push((current_val, current_count));
    
    result
}

这个方案的优点是简单易懂，适合大部分场景。统计完成后，正向遍历直接用Vec的迭代器，反向遍历调用rev()即可。

方案2：自定义惰性迭代器（更贴合伪代码写法） #

如果想更贴近你伪代码里直接调用a.iter1()、a.iter2().rev()的形式，可以给Vec实现扩展方法，自定义支持正向/反向的连续计数迭代器：

use std::iter::DoubleEndedIterator;

// 定义扩展trait，给Vec添加连续计数迭代器方法
trait ConsecutiveIterExt<T> {
    // 正向连续元素计数迭代器
    fn iter_consecutive(&self) -> ConsecutiveCounter<std::slice::Iter<'_, T>>;
    // 反向连续元素计数迭代器（从末尾开始统计）
    fn iter_consecutive_rev(&self) -> ReverseConsecutiveCounter<std::slice::Iter<'_, T>>;
}

// 为Vec实现扩展trait
impl<T: PartialEq> ConsecutiveIterExt<T> for Vec<T> {
    fn iter_consecutive(&self) -> ConsecutiveCounter<std::slice::Iter<'_, T>> {
        ConsecutiveCounter::new(self.iter())
    }
    
    fn iter_consecutive_rev(&self) -> ReverseConsecutiveCounter<std::slice::Iter<'_, T>> {
        ReverseConsecutiveCounter::new(self.iter().rev())
    }
}

// 正向连续计数迭代器结构体
struct ConsecutiveCounter<I> {
    iter: I,
    current_val: Option<I::Item>,
    current_count: usize,
}

impl<I> ConsecutiveCounter<I>
where
    I: Iterator,
    I::Item: PartialEq,
{
    fn new(mut iter: I) -> Self {
        let current_val = iter.next();
        let current_count = current_val.is_some() as usize;
        Self {
            iter,
            current_val,
            current_count,
        }
    }
}

// 实现Iterator trait
impl<I> Iterator for ConsecutiveCounter<I>
where
    I: Iterator,
    I::Item: PartialEq,
{
    type Item = (I::Item, usize);
    
    fn next(&mut self) -> Option<Self::Item> {
        let Some(mut current_val) = self.current_val.take() else {
            return None;
        };
        let mut current_count = self.current_count;
        
        while let Some(val) = self.iter.next() {
            if val == current_val {
                current_count += 1;
            } else {
                self.current_val = Some(val);
                self.current_count = 1;
                break;
            }
        }
        
        Some((current_val, current_count))
    }
}

// 反向连续计数迭代器结构体
struct ReverseConsecutiveCounter<I> {
    iter: I,
    current_val: Option<I::Item>,
    current_count: usize,
}

impl<I> ReverseConsecutiveCounter<I>
where
    I: Iterator,
    I::Item: PartialEq,
{
    fn new(mut iter: I) -> Self {
        let current_val = iter.next();
        let current_count = current_val.is_some() as usize;
        Self {
            iter,
            current_val,
            current_count,
        }
    }
}

// 实现Iterator trait
impl<I> Iterator for ReverseConsecutiveCounter<I>
where
    I: Iterator,
    I::Item: PartialEq,
{
    type Item = (I::Item, usize);
    
    fn next(&mut self) -> Option<Self::Item> {
        let Some(mut current_val) = self.current_val.take() else {
            return None;
        };
        let mut current_count = self.current_count;
        
        while let Some(val) = self.iter.next() {
            if val == current_val {
                current_count += 1;
            } else {
                self.current_val = Some(val);
                self.current_count = 1;
                break;
            }
        }
        
        Some((current_val, current_count))
    }
}

fn main() {
    let a = vec![1,1,2,3,3,3];
    
    for (&value, count) in a.iter_consecutive(){
        println!("{value}\t{count}");
        // 输出：
        // 1	2
        // 2	1
        // 3	3
    }
    
    for (&value, count) in a.iter_consecutive_rev(){
        println!("{value}\t{count}");
        // 输出：
        // 3	3
        // 2	1
        // 1	2
    }
}

这种方式是惰性迭代，不会一次性把所有统计结果存入内存，适合处理大体积的Vec。

注意事项 #

两种方案都依赖原Vec是有序的（即相同元素是连续排列的），如果Vec无序，需要先调用sort()排序后再使用这些方法。

内容的提问来源于stack exchange，提问作者Moold