lists

Full source code

C++

// -*- mode: c++ -*-
// $Id$
// http://www.bagley.org/~doug/shootout/
// from Bill Lear

#include <cstdlib>
#include <iostream>
#include <list>
#include <numeric>

using namespace std;

#ifdef SMALL_PROBLEM_SIZE
const size_t SIZE = 1000;
#else
const size_t SIZE = 10000;
#endif

template <class _ForwardIterator, class _Tp>
void 
iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
{
  while (__first != __last)
    *__first++ = __value++;
}

size_t test_lists() {
    std::list<size_t> li1(SIZE);

    ::iota(li1.begin(), li1.end(), 1);

    std::list<size_t> li2(li1);

    std::list<size_t> li3;

    size_t N = li2.size();
    while (N--) {
        li3.push_back(li2.front());
        li2.pop_front();
    }

    N = li3.size();
    while (N--) {
        li2.push_back(li3.back());
        li3.pop_back();
    }

    li1.reverse();

    return (li1.front() == SIZE) && (li1 == li2) ? li1.size() : 0;
}

int main(int argc, char* argv[]) {
#ifdef SMALL_PROBLEM_SIZE
#define LENGTH 300
#else
#define LENGTH 3000
#endif
    size_t ITER = (argc == 2 ? (atoi(argv[1]) < 1 ? 1 : atoi(argv[1])): LENGTH);

    size_t result = 0;
    while (ITER > 0) {
        result = test_lists();
        --ITER;
    }

    std::cout << result << std::endl;
}

Rust

// Adapted from https://github.com/llvm/llvm-test-suite and
// http://www.bagley.org/~doug/shootout/
// from Bill Lear
use std::env;
use std::collections::LinkedList;
use std::collections::linked_list::IterMut;

#[cfg(feature = "small_problem_size")]
const SIZE: usize = 1000;

#[cfg(not(feature = "small_problem_size"))]
const SIZE: usize = 10000;

#[cfg(feature = "small_problem_size")]
const LENGTH: i32 = 300;

#[cfg(not(feature = "small_problem_size"))]
const LENGTH: i32 = 3000;

fn iota(iter: IterMut<'_, usize>, v: usize) {
    let mut i = 0;
    for e in iter {
        *e = i + v;
        i += 1;
    }
}

fn list_reverse<T>(list: LinkedList<T>) -> LinkedList<T> {
    let mut reversed = LinkedList::new();
    for elem in list {
        reversed.push_front(elem);
    }
    return reversed
}

fn test_lists() -> usize {
    let mut li1 = LinkedList::<usize>::new();
    for _i in 0..SIZE {
        li1.push_back(Default::default());
    }

    iota(li1.iter_mut(), 1);

    let mut li2 = li1.clone();

    let mut li3 = LinkedList::<usize>::new();

    let mut n = li2.len();
    while n != 0 {
        n -= 1;
        li3.push_back(li2.pop_front().unwrap());
    }

    n = li3.len();
    while n != 0 {
        n -= 1;
        li2.push_back(li3.pop_back().unwrap());
    }

    li1 = list_reverse(li1);

    return if *li1.front().unwrap() == SIZE && li1.eq(&li2) {
        li1.len()
    } else {
        0 as usize
    };
}

fn main() {
    let mut args = env::args();
    let mut iter = if args.len() == 2 {
        if args.nth(1).unwrap().parse::<i32>().unwrap() < 1 {
            1
        } else {
            args.nth(1).unwrap().parse::<i32>().unwrap()
        }
    } else {
        LENGTH
    };

    let mut result: usize = 0;
    while iter > 0 {
        result = test_lists();
        iter -= 1;
    }

    println!("{}", result);
}

Porting notes

Initializing a list with incrementing values (iota)

C++

template <class _ForwardIterator, class _Tp>
void 
iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
{
  while (__first != __last)
    *__first++ = __value++;
}

Rust

#![allow(unused)]
fn main() {
fn iota(iter: IterMut<'_, usize>, v: usize) {
    let mut i = 0;
    for e in iter {
        *e = i + v;
        i += 1;
    }
}
}

I omitted the use of generics in the Rust version because it's used only for one call site.

In Rust, an iterator is a single entity, an IterMut in this case (an Iter if mutation isn't needed) and the iteration over the iterator uses the for range loop, as opposed to a pair of separate, pointer-like iterators and more free-style iteration over them in C++. I think this helps make the handling of iterators safer in Rust.

Reversing a linked list

C++ none.

Rust

#![allow(unused)]
fn main() {
fn list_reverse<T>(list: LinkedList<T>) -> LinkedList<T> {
    let mut reversed = LinkedList::new();
    for elem in list {
        reversed.push_front(elem);
    }
    return reversed
}
}

Rust's LinkedList interestingly doesn't have a reverse method.

I implemented a simple reverse function that copies to a new linked list in the reverse order. I'd imagine that this could be slower than a built-in reversemethod that reverses the directions of the internal pointers without copying the nodes, but the benchmark results show the Rust version is no slower.

The type inference allows the type T to be inferred in the LinkedList::new() call.

Initializinga linked list of a given size with the default element value

C++

    std::list<size_t> li1(SIZE);

Rust

#![allow(unused)]
fn main() {
    let mut li1 = LinkedList::<usize>::new();
    for _i in 0..SIZE {
        li1.push_back(Default::default());
    }
}

Similar to Vec, there isn't a way to initialize a LinkedList with a given size, unlike std::list in C++. I used a two-step approach of allocating a zero-sized linked list and then resizing it with the default element value. Default::default() is a convenient way to specify the default value of a certain type without typing the type name.

Copying a linked list

C++

    std::list<size_t> li2(li1);

Rust

#![allow(unused)]
fn main() {
    let mut li2 = li1.clone();
}

Rust's LinkedList doesn't provide a way to initialize a linked list as a copy of another. There is no copy constructor as in C++. We use clone() to achieve the same.

Popping the front of a linked list and capturing the front

C++

        li3.push_back(li2.front());
        li2.pop_front();

Rust

#![allow(unused)]
fn main() {
        li3.push_back(li2.pop_front().unwrap());
}

Rust's pop_front() returns an std::optional value in addition to removing the front element from the linked list and achieves what both front() and pop_front() need to be used to achieve the same in C++.

An if expression

C++

    return (li1.front() == SIZE) && (li1 == li2) ? li1.size() : 0;

Rust

#![allow(unused)]
fn main() {
    return if *li1.front().unwrap() == SIZE && li1.eq(&li2) {
        li1.len()
    } else {
        0 as usize
    };
}

To peek the value of the front element of a linked list, we get a std::optional by calling front(), takes the reference by calling unwrap on the std::optional and dereference it. This would normally force programmars to think about the case where the linked list is empty but here we bypass that for simplicity by asserting otherwise.

The == operator in C++ would compare the two linked lists as a whole. For that, we use the eq method in Rust.

We use the if statement instead of a ternary operator which doesn't exist in Rust.