Skip to content

Subslice search #54961

New issue

Have a question about this project? # for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “#”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? # to your account

Open
leonardo-m opened this issue Oct 10, 2018 · 6 comments
Open

Subslice search #54961

leonardo-m opened this issue Oct 10, 2018 · 6 comments
Labels
C-feature-request Category: A feature request, i.e: not implemented / a PR. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.

Comments

@leonardo-m
Copy link

leonardo-m commented Oct 10, 2018

As enhancement, I think stdlib should contain functions that search a subslice inside a given slice:

fn contains_subslice<T: PartialEq>(data: &[T], needle: &[T]) -> bool {
    data
    .windows(needle.len())
    .any(|w| w == needle)
}

fn position_subslice<T: PartialEq>(data: &[T], needle: &[T]) -> Option<usize> {
    data
    .windows(needle.len())
    .enumerate()
    .find(|&(_, w)| w == needle)
    .map(|(i, _)| i)
}

fn main() {
    println!("{}", contains_subslice(b"hello", b"ll"));
    println!("{:?}", position_subslice(b"hello", b"ll"));
}

For the common case of T:Copy items the true stdlib functions should specialize using a smarter algorithm, like:
https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

(Similar functions are useful for iterators too).

@estebank estebank added the T-libs-api Relevant to the library API team, which will review and decide on the PR/issue. label Oct 10, 2018
@Shnatsel
Copy link
Member

I am baffled that this is actually not in the standard library. Functions contains and find are apparently implemented for strings but not slices?

@Shnatsel
Copy link
Member

At least there is a third-party crate based on stdlib implementation for strings: https://github.com/strake/subslice.rs

@Mark-Simulacrum Mark-Simulacrum added the C-feature-request Category: A feature request, i.e: not implemented / a PR. label Dec 10, 2019
@qingyunha
Copy link

I think this is a common function that should live in the standard library of any programming language.

@hikari-no-yume
Copy link

I'm also surprised by this. &[u8] is commonly used as a byte string type, and all the reasons you'd search a &str for a substring also apply to a &[u8].

It seems that [T]::contains() is taken (it's a function that searches for a single element). [T]::contains_slice() would make sense?

@hikari-no-yume
Copy link

Though actually, bytes.windows(3).any(|window| window == b"foo") isn't that bad.

@ByteNybbler
Copy link

ByteNybbler commented Feb 29, 2024

I've also very much desired this functionality, particularly to check if a byte slice exists within a [u8] without having to convert it to a str first.

It seems that [T]::contains() is taken (it's a function that searches for a single element). [T]::contains_slice() would make sense?

[T]::contains could probably be upgraded to take a generic impl Pattern argument, making it more analogous to str::contains while also being backward-compatible.

# for free to join this conversation on GitHub. Already have an account? # to comment
Labels
C-feature-request Category: A feature request, i.e: not implemented / a PR. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.
Projects
None yet
Development

No branches or pull requests

7 participants