Search function

[Hemhek]

Is there a search function for arrays in the standard library? The binary_search family of functions does not work on unordered Strings, and contains doesn't return the index.

[minimum]

Maybe you can use Iterator in std::iter - Rust .

fn main() {
    let array = [1, 2, 3];
    let index = array.iter().position(|&x| x == 2);
    println!("{:?}", index);
}

[Hemhek]

Thanks!
Yes I tried that. But apparently position consumes the iterator, which makes it unsuitable for my purpose.

[H2CO3]

It consumes the iterator, but if the iterator only borrows (which is exactly what .iter() does on arrays and slices), then that leaves the array itself intact.

[Hemhek]

In my scenario the I am using the position to find a start position for a Cycle. If I use position to find the the start position then I can no longer use nth to advance to that position - 1 (as it would be a negative number)

[H2CO3]

I don't understand what exactly you mean – you should provide actual code, not a vague natural language description.

Anyway, it seems like an entirely different problem. I.e., you are not trying to simply find an element in an array, because the problem is apparently not only that the iterator is being consumed.

If you want an iterator to not be consumed, then use by_ref().

[farnz]

I've put @minimum's code into the Rust Playground, and extended it slightly to show us using position to find a string, then consuming the array to use nth to get the element before the one I found.

Can you rewrite this code to show the problem that you're having? In general, it's much easier to help if you can convert your problem into a sample in the Rust Playground, since then it's obvious what you've tried and what problem you're running into.

[Hemhek]

fn create_counter(start_day: &String) -> Cycle<IntoIter<String, 7>> {

    let day_names = [
        String::from("Sunday"),
        String::from("Monday"),
        String::from("Tuesday"),
        String::from("Wednesday"),
        String::from("Thursday"),
        String::from("Friday"),
        String::from("Saturday"),
    ];
    let mut start_pos = //search function here

    let mut iter = day_names.into_iter().cycle();
    
    if start_pos == 0 {
        start_pos = 7;
    }
    iter.nth(start_pos - 1);

    iter
}

Sorry, didn't provide code as my issue was not how to solve the problem but whether there was a solution in std.

as_ref still advances the iterator

[farnz]

Does Rust Playground look helpful?

There's a few changes I've made from your sample:

1. Use &str in preference to &String - this makes your code more flexible, and doesn't cost anything (since all you're losing is the ability to reallocate the String, but you can't do that via a shared reference.
2. Use impl Iterator rather than writing out the full type - this hides your implementation details from the caller.
3. Implement start_pos.
4. Handle the case where the supplied string is not in the set.

[H2CO3]

@Hemhek

as_ref still advances the iterator

Yeah, searching an iterator must advance it.

I still don't get why position is not good enough. This seems to compile and work how you want it to.

[Hemhek]

Yes that works, as does the solution of @farnz.
Both solutions require creating two iterators (one iter() one to_iter()) which hadn't occured to me.
I still think a search function that simply searches the array is the best solution, but such a functiion does not exist as is in std. It is easy to write one though.

Thanks for the help.

[Hemhek]

Thanks! and for the other tips as well!

[farnz]

A search function of the form you want always iterates over the array - that's how you do a linear search (which is your best option for searching an unsorted array).

And in release mode, I'd expect fn search<T: PartialEq, const N: usize>(array: &[T; N], target: &T) -> Option<usize> to be best implemented as array.iter().position(|item| item == target), because any other implementation will generate the same or worse code. If that's not true, then because idiomatic Rust does make use of Iterator for iteration (a for item in source loop, for example, is nice syntax for let iter = source.into_iter(); while let Some(item) = iter.next() { … }), I'd expect people to care hugely about why the compiler's getting it wrong, and fix the optimization bugs.

In that sense, Rust makes a lot of effort to have so-called "zero-cost abstraction", of which Iterator is an example; the point of "zero-cost abstraction" is not that the code you write compiles down to nothing, but rather that there's no way to iterate over an array or other data structure that's going to result in better code than just using Iterator. Even hand-writing optimal assembly language should not help you, as opposed to just writing the abstract version using Iterator and the methods on Iterator. This does mean that you need to get used to thinking in terms of using the abstractions whenever they're offered, rather than looking for methods on concrete type, but has the advantage that you can change data types later (for example, you're using an array here - but what happens if you want to change to a Vec (so that the list of items to search is dynamic at runtime), or a BTreeSet (so that they're guaranteed ordered and unique)?

[Hemhek]

I see.
I meant that I would have expected a general puprose search function in std, but I understand what you are saying about the design considerations.
Thanks again.

[farnz]

There is a general purpose search function in std: if you have something that can be iterated over, Iterator::find will search for the item based on a user-supplied predicate, and return the found item, or None. If you need the index instead, there's Iterator::position, and if you want to take an item and everything after it, there's Iterator::skip_while (or Iterator::take_while for everything up to an item).

This leads to another way to implement your requirement; you could use contains to check that the array contains the item you want, then do something like day_names.into_iter().cycle().skip_while(|item| item != start_day). I wouldn't recommend this, since it's an infinite loop if start_day is not in the array, but it's another way to do it using search functionality.