# Anything like C++ std::includes?

**URL:** <https://discourse.julialang.org/t/anything-like-c-std-includes/52288>\
**Category:** General Usage\
**Created:** [December 23, 2020, 5:38pm UTC](https://discourse.julialang.org/t/anything-like-c-std-includes/52288 "2020-12-23T17:38:55Z")\
**Posts on this page:** 16\
**Page:** 1

<div class="post-metadata">

**Author:** ![phendric](https://avatars.discourse-cdn.com/v4/letter/p/58f4c7/32.png) [@phendric](https://discourse.julialang.org/u/phendric)\
**Post date:** [December 23, 2020, 5:38pm UTC](https://discourse.julialang.org/t/anything-like-c-std-includes/52288/1 "2020-12-23T17:38:55Z")

</div>

Question: does Julia have an analog to C++'s [std::includes](https://en.cppreference.com/w/cpp/algorithm/includes)? `issubset` doesn’t do what I’m looking for (_I want following to return false, as the first array isn’t a sub-array of the 2nd_):

```julia
julia> issubset([4,4,1],[1,4,2])
true

```

There’s a [Stack Overflow post](https://stackoverflow.com/questions/36346005/julia-does-an-array-contain-a-specific-sub-array) asking for something similar, but it’s several years old and the code samples there (`issubvec`, `subset2`) don’t appear to be compatible with a more-or-less current version of Julia (1.5.1).

I wrote a function to do what I want:

```julia
julia> function subset4(a::Array{Int},b::Array{Int})
           a_unq=unique(a)
           b_unq=unique(b)
           subset::Bool=true
           if issubset(a_unq, b_unq)
               for val in a_unq
                   if count(x->x==val,a)>count(y->y==val,b)
                       subset=false
                       break
                   end
               end
           else
               subset=false
           end
           return subset
       end
subset4 (generic function with 1 method)

```

It behaves correctly, but is much slower than either `issubset` or a C++ version of the thing.

`issubset` (after compile):

```julia
julia> @time for ii in 1:1000000 issubset(rand(1:10,3),rand(1:10,10)) end
  0.168592 seconds (2.00 M allocations: 259.399 MiB, 9.08% gc time)

```

`subset4` (after compile):

```julia
julia> @time for ii in 1:1000000 subset4(rand(1:10,3),rand(1:10,10)) end
  0.795771 seconds (15.00 M allocations: 1.461 GiB, 11.04% gc time)

```

This is almost 5x slower.

C++ `std::includes`:

```julia
#include <iostream>
#include <array>
#include <random>
#include <algorithm>

int main() {
  std::array<int, 3> a;
  std::array<int, 10> b; 
  bool subset;
  
  std::mt19937_64 randomGenerator;
  randomGenerator.seed(std::random_device{}());
  std::uniform_int_distribution<int> digitDistro{1, 10};
  
  for(int j=0; j<1000000; j++) {
    for(int i=0; i<3; i++) a[i]=digitDistro(randomGenerator);
    for(int i=0; i<10; i++) b[i]=digitDistro(randomGenerator);
    
    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());
    
    subset = std::includes(b.begin(), b.end(), a.begin(), a.end());
  }
  return 0;
}

```

```julia
$ g++ -o includesTest includesTest.cpp -O3
$ time ./includesTest

real 0m0.166s
user 0m0.166s
sys 0m0.000s

```

`issubset` is about as fast as `std::includes`.

I need something ideally as fast as the “fast” functions in this post, as I’m going to be iterating through a large number of combinations of numbers and checking if they’re a subset of a master list.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [December 23, 2020, 5:48pm UTC](https://discourse.julialang.org/t/anything-like-c-std-includes/52288/2 "2020-12-23T17:48:35Z")

</div>

using `Accumulator`s from `DataStructures.jl` gives a more efficient approach.

```julia
using DataStructures

function subset5(a::AbstractVector,b::AbstractVector)
    count_a = counter(a)
    count_b = counter(b)
    return all(count_a[key]<=count_b[key] for key in keys(count_a))
end

```

I time it at 3x slower than `issubset` for small inputs, and 17% slower for large inputs.

Edit: adding an early bailout for `!issubset` brings it to about 2x in both cases. There’s probably a size based heuristic that could give you the best of both worlds.

---

<div class="post-metadata">

**Author:** ![phendric](https://avatars.discourse-cdn.com/v4/letter/p/58f4c7/32.png) [@phendric](https://discourse.julialang.org/u/phendric)\
**Post date:** [December 23, 2020, 6:18pm UTC](https://discourse.julialang.org/t/anything-like-c-std-includes/52288/3 "2020-12-23T18:18:15Z")

</div>

I’m seeing a factor of 6x slower for small inputs. Not sure what you mean by “early bailout for `!issubset`.”

```julia
julia> @time for ii in 1:1000000 subset5(rand(1:10,3),rand(1:10,10)) end
  1.022921 seconds (15.00 M allocations: 1.490 GiB, 8.67% gc time)

julia> 1.022921/0.168592
6.067434990984151

```

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [December 23, 2020, 6:27pm UTC](https://discourse.julialang.org/t/anything-like-c-std-includes/52288/4 "2020-12-23T18:27:09Z")

</div>

I meant

```julia
function subset6(a::AbstractVector,b::AbstractVector)
    !issubset(a,b) && return false
    count_a = counter(a)
    count_b = counter(b)
    return all(count_a[key]<=count_b[key] for key in keys(count_a))
end

```

---

<div class="post-metadata">

**Author:** ![phendric](https://avatars.discourse-cdn.com/v4/letter/p/58f4c7/32.png) [@phendric](https://discourse.julialang.org/u/phendric)\
**Post date:** [December 23, 2020, 6:31pm UTC](https://discourse.julialang.org/t/anything-like-c-std-includes/52288/5 "2020-12-23T18:31:51Z")

</div>

Thanks - I’m still very much a Julia newbie.

I’m also seeing 2x, which is the best I’ve seen in Julia to this point:

```julia
julia> @time for ii in 1:1000000 subset6(rand(1:10,3),rand(1:10,10)) end
  0.336311 seconds (4.36 M allocations: 601.466 MiB, 9.98% gc time)

julia> 0.336311/0.168592
1.9948218183543707

```

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [December 23, 2020, 6:47pm UTC](https://discourse.julialang.org/t/anything-like-c-std-includes/52288/6 "2020-12-23T18:47:23Z")

</div>

**Edit** : dont’ use this. It’s wrong

```julia
function subset7(a::AbstractVector,b::AbstractVector)
	length(a)>length(b) && return false
	sort!(a)
	sort!(b)
	cur = a[1]
	cur != b[1] && return false 
	for i in 2:length(a)
		if cur == a[i]
			cur != b[i] && return false
		else
			new_cur = a[i]
			i=findfirst(x-> x!=cur, @view b[i:end])
			i === nothing || i>length(a) && return
			new_cur != b[i] && return false
			cur = new_cur
		end
	end
	return true
end

```

Here is a version that is even faster (it uses a slightly better version of the C++ algorithm.

---

<div class="post-metadata">

**Author:** ![carstenbauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carstenbauer/32/4981_2.png) [@carstenbauer](https://discourse.julialang.org/u/carstenbauer)\
**Post date:** [December 23, 2020, 7:08pm UTC](https://discourse.julialang.org/t/anything-like-c-std-includes/52288/7 "2020-12-23T19:08:29Z")

</div>

Direct translation of what is listed as “possible implementation” in the [C++ reference](https://en.cppreference.com/w/cpp/algorithm/includes) you linked.

```julia
function includes(a::AbstractVector,b::AbstractVector)
    first2 = firstindex(a)
    first1 = firstindex(b)
    last2 = lastindex(a)
    last1 = lastindex(b)

    while first2 != last2
        if (first1 == last1) || (b[first2] < a[first1])
            return false
        else !(a[first1] < b[first2])
            first2 += 1
        end
        first1 += 1
    end
    return true
end

```

```julia
julia> @btime subset4(x,y) setup=(x=rand(1:10,3);y=rand(1:10,10))
  410.442 ns (12 allocations: 1.19 KiB)

julia> @btime subset5(x,y) setup=(x=rand(1:10,3);y=rand(1:10,10))
  354.789 ns (8 allocations: 1.19 KiB)

julia> @btime subset7(x,y) setup=(x=rand(1:10,3);y=rand(1:10,10))
  63.083 ns (1 allocation: 16 bytes)

julia> @btime issubset(x,y) setup=(x=rand(1:10,3);y=rand(1:10,10))
  7.455 ns (0 allocations: 0 bytes)

julia> @btime includes(x,y) setup=(x=rand(1:10,3);y=rand(1:10,10))
  3.464 ns (0 allocations: 0 bytes)

```

This is about **100x faster** than your original function (assuming that my Julia translation is correct).

**Update** : I noted that you sort the arrays as well. Adding corresponding `sort!` statements to the includes function I find

```julia
julia> @btime includes(x,y) setup=(x=rand(1:10,3);y=rand(1:10,10))
  45.820 ns (0 allocations: 0 bytes)
false

```

---

<div class="post-metadata">

**Author:** ![phendric](https://avatars.discourse-cdn.com/v4/letter/p/58f4c7/32.png) [@phendric](https://discourse.julialang.org/u/phendric)\
**Post date:** [December 23, 2020, 7:33pm UTC](https://discourse.julialang.org/t/anything-like-c-std-includes/52288/8 "2020-12-23T19:33:33Z")

</div>

> [@carstenbauer](#):
>
> Direct translation of what is listed as “possible implementation” in the [C++ reference](https://en.cppreference.com/w/cpp/algorithm/includes) you linked.
> 
> [snip]
> 
> This is about 100x faster than your original function (assuming that my Julia translation is correct).
> 
> **Update** : I noted that you sort the arrays as well. Adding corresponding `sort!` statements to the includes function I find

Yes, that **is** fast. I saw the sample implementation(s) on that page, and thought “Maybe someday I’ll be good enough at Julia (_or maybe just programming_) to be able to translate that C++ code.” For what it’s worth, your translation looks remarkably like the C++ code it came from.

FYI, I sorted the arrays (in the C++ code) because `std::includes` requires it, not because I have any particular need to:

> Returns true if the sorted range `[first2, last2)` is a [subsequence](https://en.wikipedia.org/wiki/subsequence) of the sorted range `[first1, last1)` .

While I was wondering why @Oscar_Smith’s last function wasn’t doing what I expect…

```julia
julia> subset7([1,4],[2,4,1])
false

```

…you jumped in with your translation, which does. 😃

```julia
julia> includes([1,4],[2,4,1])
true

```

Thanks everyone!

---

<div class="post-metadata">

**Author:** ![cchderrick](https://avatars.discourse-cdn.com/v4/letter/c/ecd19e/32.png) [@cchderrick](https://discourse.julialang.org/u/cchderrick)\
**Post date:** [December 23, 2020, 8:03pm UTC](https://discourse.julialang.org/t/anything-like-c-std-includes/52288/9 "2020-12-23T20:03:20Z")

</div>

Not sure if you had `a` and `b` swapped, and also the possible implementation did not seems to handle the case for the last element of `b` (`first2!=last2`) ?.

```julia
function includes(a::AbstractVector,b::AbstractVector)
    first2 = firstindex(b)
    last2 = lastindex(b)
    first1 = firstindex(a)
    last1 = lastindex(a)
    
    while first2 != last2
        if (first1 == last1) || (b[first2] < a[first1])
            return false
        else !(a[first1] < b[first2])
            first2 += 1
        end
        first1 += 1
    end
    first2 == last2 && return (b[first2] in a) 
    return true
end

v1 = ['a', 'b', 'c', 'f', 'h', 'x']
v2 = ['a', 'b', 'c']
v3 = ['a', 'c']
v4 = ['a', 'a', 'b']
v5 = ['g']
v6 = ['a', 'c', 'g']
v7 = ['A', 'B', 'C']

"""
$(v1)
includes:
a b c : $(includes(v1, v2))
a c : $(includes(v1, v3))
a a b : $(includes(v1, v4))
g : $(includes(v1, v5))
a c g : $(includes(v1, v6))
\$v1 : $(includes(v1, v1))
""" |> print

```

Produce this, which is closer to the expected behavior.

```julia
['a', 'b', 'c', 'f', 'h', 'x']
includes:
a b c : true
a c : true
a a b : false
g : false
a c g : false
$v1 : true

```

Edit:  
Should be this instead.  
`first2 == last2 && return (b[first2] in a[first1:end])`

```julia
['a', 'b', 'c', 'f', 'h', 'x']
includes:
a b c : true
a c : true
a a b : false
g : false
a c a : false
a b c g : false
a b c f h x : true

```

---

<div class="post-metadata">

**Author:** ![carstenbauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carstenbauer/32/4981_2.png) [@carstenbauer](https://discourse.julialang.org/u/carstenbauer)\
**Post date:** [December 23, 2020, 8:04pm UTC](https://discourse.julialang.org/t/anything-like-c-std-includes/52288/10 "2020-12-23T20:04:53Z")

</div>

Yes, I swapped a and b because of what the OP wrote in his initial post (first arrays is/isn’t subarray of the second).

---

<div class="post-metadata">

**Author:** ![phendric](https://avatars.discourse-cdn.com/v4/letter/p/58f4c7/32.png) [@phendric](https://discourse.julialang.org/u/phendric)\
**Post date:** [December 23, 2020, 9:23pm UTC](https://discourse.julialang.org/t/anything-like-c-std-includes/52288/11 "2020-12-23T21:23:38Z")

</div>

> [@cchderrick](#):
>
> …the possible implementation did not seems to handle the case for the last element of `b` (`first2!=last2`) ?.

Not sure I follow you. Using @carstenbauer’s code, the following is correct and…I think…tests the thing you bring up (“_last element of ‘b’_”):

```julia
julia> includes(['a', 'b', 'c', 'f', 'h', 'x'], ['a', 'b', 'c', 'f', 'h', 'x'])
true

```

> [@cchderrick](#):
>
> Not sure if you had `a` and `b` swapped…

Yes, it’s swapped from the C++ function, but I don’t need an identical function signature. I used `std::includes` as an example of a) a thing that computes what I want it to, and b) is fast.

---

<div class="post-metadata">

**Author:** ![cchderrick](https://avatars.discourse-cdn.com/v4/letter/c/ecd19e/32.png) [@cchderrick](https://discourse.julialang.org/u/cchderrick)\
**Post date:** [December 23, 2020, 9:44pm UTC](https://discourse.julialang.org/t/anything-like-c-std-includes/52288/12 "2020-12-23T21:44:18Z")

</div>

> [@phendric](#):
>
> `includes(['a', 'b', 'c', 'f', 'h', 'x'], ['a', 'b', 'c', 'f', 'h', 'x'])`

`includes(['a', 'b', 'c', 'g'], ['a', 'b', 'c', 'f', 'h', 'x'])`  
This will return true.  
‘g’ is not even in the sequence.  
The problem is this: `(first2!=last2)`  
When the `b` sequence at its last position `(first2==last2)`, which is ‘g’, it breaks out the while-loop and return true, without checking for any more ‘g’ in `a` after ‘c’.

Which makes me think the “possible implementation” from the reference page is just a partial solution, not a C++ expert so I am not sure.

---

<div class="post-metadata">

**Author:** ![phendric](https://avatars.discourse-cdn.com/v4/letter/p/58f4c7/32.png) [@phendric](https://discourse.julialang.org/u/phendric)\
**Post date:** [December 23, 2020, 10:21pm UTC](https://discourse.julialang.org/t/anything-like-c-std-includes/52288/13 "2020-12-23T22:21:56Z")

</div>

> [@cchderrick](#):
>
> `includes(['a', 'b', 'c', 'g'], ['a', 'b', 'c', 'f', 'h', 'x'])`  
> This will return true.  
> ‘g’ is not even in the sequence.  
> The problem is this: `(first2!=last2)`  
> When the `b` sequence at its last position `(first2==last2)`, which is ‘g’, it breaks out the while-loop and return true, without checking for any more ‘g’ in `a` after ‘c’.
> 
> Which makes me think the “possible implementation” from the reference page is just a partial solution, not a C++ expert so I am not sure.

Oof. Yeah:

```julia
julia> includes(['a', 'b', 'c', 'd', 'U', 'f'], ['a', 'b', 'c', 'd', 'e', 'f'])
true

```

---

<div class="post-metadata">

**Author:** ![cchderrick](https://avatars.discourse-cdn.com/v4/letter/c/ecd19e/32.png) [@cchderrick](https://discourse.julialang.org/u/cchderrick)\
**Post date:** [December 23, 2020, 11:06pm UTC](https://discourse.julialang.org/t/anything-like-c-std-includes/52288/14 "2020-12-23T23:06:58Z")

</div>

For that particular implementation, I don’t think you can swap `a` and `b`, and it needed that last element checks.

```julia
first2 == last2 && return (b[first2] in a[first1:end]) 

```

And `first2 == last2` is redundant.

```julia
function includes(a::AbstractVector,b::AbstractVector)
    @assert issorted(a)
    @assert issorted(b)
    first2 = firstindex(b)
    last2 = lastindex(b)
    first1 = firstindex(a)
    last1 = lastindex(a)
    
    while first2 != last2
        if (first1 == last1) || (b[first2] < a[first1])
            return false
        else !(a[first1] < b[first2])
            first2 += 1
        end
        first1 += 1
    end
    return (b[first2] in a[first1:end])
end

```

Here is how I tested it.

```julia
v1 = ['a', 'b', 'c', 'f', 'h', 'x']
v2 = ['a', 'b', 'c']
v3 = ['c','h']
v4 = ['x']
v5 = ['h','x']
v6 = ['g']
v7 = ['a', 'c', 'z']
v8 = ['a', 'b', 'c', 'g', 'x']
v9 = ['0', 'b', 'c', 'd', 'h', 'x']

"""
$(join(v1,' '))
includes:
$(rpad(join(v2,' '),20)) : $(includes(v1, v2))
$(rpad(join(v3,' '),20)) : $(includes(v1, v3))
$(rpad(join(v4,' '),20)) : $(includes(v1, v4))
$(rpad(join(v5,' '),20)) : $(includes(v1, v5))
$(rpad(join(v6,' '),20)) : $(includes(v1, v6))
$(rpad(join(v7,' '),20)) : $(includes(v1, v7))
$(rpad(join(v8,' '),20)) : $(includes(v1, v8))
$(rpad(join(v9,' '),20)) : $(includes(v1, v9))
""" |> print

```

And `a b c g x` still make no sense:

```julia
a b c f h x
includes:
a b c : true
c h : true
x : true
h x : true
g : false
a c z : false
a b c g x : true
0 b c d h x : false

```

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [December 24, 2020, 3:05pm UTC](https://discourse.julialang.org/t/anything-like-c-std-includes/52288/15 "2020-12-24T15:05:00Z")

</div>

Could you please call your new implementation `issublist`, so as not to confuse with `issubset`, which compares `Set`s, and have a name which reflects better what it does?

---

<div class="post-metadata">

**Author:** ![carstenbauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carstenbauer/32/4981_2.png) [@carstenbauer](https://discourse.julialang.org/u/carstenbauer)\
**Post date:** [December 24, 2020, 5:03pm UTC](https://discourse.julialang.org/t/anything-like-c-std-includes/52288/16 "2020-12-24T17:03:44Z")

</div>

AFAIU, the semi-official term is _subsequence_. So I suggest calling it `issubsequence`.