21

What is the canonical method to convert an Iterator<&str> to a String, interspersed with some constant string (e.g. "\n")?

For instance, given:

let xs = vec!["first", "second", "third"];
let it = xs.iter();

There is a way to produce a string s by collecting into some Iterable and joining the result:

let s = it
    .map(|&x| x)
    .collect::<Vec<&str>>()
    .join("\n");

However, this unnecessarily allocates memory for a Vec<&str>. Is there a more direct method?

Mateen Ulhaq
  • 21,459
  • 16
  • 82
  • 123
  • 1
    Apologies - my original answer removed the iterator but your question is asking how to join an iterator and not allocate the extra vector. – Simon Whitehead May 08 '19 at 04:41
  • @SimonWhitehead No worries; I was wondering if I should have made that clearer. – Mateen Ulhaq May 08 '19 at 04:43
  • 1
    Looks like the `itertools` crate [doesn't allocate the vector](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=e208a26d869de89f6b998e6bcf6b5a77) – Simon Whitehead May 08 '19 at 05:09
  • 2
    Note that depending on the exact characteristics of your iterator, collecting into a vector of slices and then joining could actually be faster than using Websterix's method or `itertools`, since `SliceConcatExt::join` can calculate the needed size for the full string ahead of time and thus definitely doesn't need to reallocate during accumulation; whereas the other methods may have to reallocate the string. You should definitely benchmark. – Sebastian Redl May 08 '19 at 06:04
  • @SebastianRedl But `collect::>` would need to reallocate, but it's a lot smaller than the string buffer, so i guess that would be a faster? – chpio May 08 '19 at 09:37
  • 1
    @chpio It has to allocate, but not reallocate if the iterator gives a good size hint. – Sebastian Redl May 08 '19 at 12:45
  • @SebastianRedl yeah, you're right. – chpio May 08 '19 at 13:11
  • [The `once` plus `skip` trick works nicely for this](https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=b5eedf3f4537a263435b35942f7a5334). See also [this answer](https://stackoverflow.com/a/66951473/4039050). – schneiderfelipe Jan 14 '22 at 15:17

3 Answers3

17

You could use the itertools crate for that. I use the intersperse helper in the example, it is pretty much the join equivalent for iterators.

cloned() is needed to convert &&str items to &str items, it is not doing any allocations. It can be eventually replaced by copied() when rust@1.36 gets a stable release.

use itertools::Itertools; // 0.8.0

fn main() {
    let words = ["alpha", "beta", "gamma"];
    let merged: String = words.iter().cloned().intersperse(", ").collect();
    assert_eq!(merged, "alpha, beta, gamma");
}

Playground

chpio
  • 687
  • 3
  • 15
9

You can do it by using fold function of the iterator easily:

let s = it.fold(String::new(), |a, b| a + b + "\n");

The Full Code will be like following:

fn main() {
    let xs = vec!["first", "second", "third"];
    let it = xs.into_iter();

    // let s = it.collect::<Vec<&str>>().join("\n");

    let s = it.fold(String::new(), |a, b| a + b + "\n");
    let s = s.trim_end();

    println!("{:?}", s);
}

Playground

EDIT: After the comment of Sebastian Redl I have checked the performance cost of the fold usage and created a benchmark test on playground.

You can see that fold usage takes significantly more time for the many iterative approaches.

Did not check the allocated memory usage though.

Akiner Alkan
  • 5,023
  • 25
  • 58
  • 5
    The reason this is slow is because you're using + to create two new Strings on every iteration. If you use a single string ([playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=f2740a132f69b5d41d14a3472c98674e)) it can work better than collect and join ([playground](https://play.rust-lang.org/?version=stable&mode=release&edition=2018&gist=5fa149bbd78707d7ff4e257d38318361)). – mdonoughe Dec 21 '20 at 07:15
  • added `black_box` and create the vec for each test individually (because of cache warming) ([playgroud](https://play.rust-lang.org/?version=nightly&mode=release&edition=2018&gist=9316d8202ee375f35305c8ec938f5f47)). Playground isn't that good for benchmarking due to massive variance in latency/duration, but the fold variant seems to be slightly slower (over multiple runs). – chpio Apr 19 '21 at 12:23
  • [v2](https://play.rust-lang.org/?version=nightly&mode=release&edition=2018&gist=6d7a6e7427a715d853ce32440a0ad59e) with `black_box(xs).iter().copied()` takes now twice as long for collect+join over fold (the `black_box(xs)` doesn't matter, `xs` is the same). <3 for microbenchmarking – chpio Apr 19 '21 at 12:54
  • I guess they optimize something like `vec!["hey"; 100_000].into_iter().collect>` to just return the original vec?! – chpio Apr 19 '21 at 13:02
  • Yes, [they do](https://doc.rust-lang.org/stable/src/alloc/vec/spec_from_iter.rs.html#41) – chpio Apr 19 '21 at 13:14
-2

there's relevant example in rust documentation: here. 

let words = ["alpha", "beta", "gamma"];

// chars() returns an iterator
let merged: String = words.iter()
                          .flat_map(|s| s.chars())
                          .collect();
assert_eq!(merged, "alphabetagamma");

You can also use Extend trait:

fn f<'a, I: Iterator<Item=&'a str>>(data: I) -> String {
    let mut ret = String::new();
    ret.extend(data);
    ret
}
Laney
  • 1,465
  • 8
  • 7
  • 4
    This answer does not reproducing the OP's needs. OP is asking about interspersed with some constant string (e.g. "\n")?. – Akiner Alkan May 08 '19 at 05:29
  • 1
    also this should work without `flat_map`, as *String* already implements `Extend`. – chpio May 08 '19 at 09:16