Finding similar items in two arrays with multithreading in C++
The cost of starting up a thread is generally considered expensive. For your example of only 10 items, you won't ever see it because the application quits before you notice it started. Generally for something like this, you'd want to start up a thread to process some large portion of the array rather than one thread per element of the array. At 10 elements, it's no big deal. But once you have thousands of elements, you don't want thousands of threads running. In fact, many operating systems will limit the number of threads you can start. According to @user673679, you can get the number of concurrent threads by calling std::thread::hardware_concurrency.

I recommend limiting the number of threads to something like the number of available CPU cores on the machine. Then split the input arrays into that many parts and have each thread work on one part of the array. So if you have 8 cores, split the work into 8 parts and have each thread work on 1/8th of the array.

I ran your code with Thread Sanitizer and it's telling me you have a data race. Here's what it says:

WARNING: ThreadSanitizer: data race (pid=7975)
  Read of size 8 at 0x7ffeefbff2f0 by thread T4:
    #0 process(unsigned char const*, unsigned char const*, unsigned long, unsigned char)::$_0::operator()() const main.cpp:34 (CPlusPlusTester:x86_64+0x100006b4a)
    #1 decltype(std::__1::forward&lt;process(unsigned char const*, unsigned char const*, unsigned long, unsigned char)::$_0&gt;(fp)()) std::__1::__invoke&lt;process(unsigned char const*, unsigned char const*, unsigned long, unsigned char)::$_0&gt;(process(unsigned char const*, unsigned char const*, unsigned long, unsigned char)::$_0&amp;&amp;) type_traits:4339 (CPlusPlusTester:x86_64+0x100006a00)
    #2 void std::__1::__thread_execute&lt;std::__1::unique_ptr&lt;std::__1::__thread_struct, std::__1::default_delete&lt;std::__1::__thread_struct&gt; &gt;, process(unsigned char const*, unsigned char const*, unsigned long, unsigned char)::$_0&gt;(std::__1::tuple&lt;std::__1::unique_ptr&lt;std::__1::__thread_struct, std::__1::default_delete&lt;std::__1::__thread_struct&gt; &gt;, process(unsigned char const*, unsigned char const*, unsigned long, unsigned char)::$_0&gt;&amp;, std::__1::__tuple_indices&lt;&gt;) thread:342 (CPlusPlusTester:x86_64+0x100006868)
    #3 void* std::__1::__thread_proxy&lt;std::__1::tuple&lt;std::__1::unique_ptr&lt;std::__1::__thread_struct, std::__1::default_delete&lt;std::__1::__thread_struct&gt; &gt;, process(unsigned char const*, unsigned char const*, unsigned long, unsigned char)::$_0&gt; &gt;(void*) thread:352 (CPlusPlusTester:x86_64+0x1000059f9)

  Previous write of size 8 at 0x7ffeefbff2f0 by main thread:
    #0 process(unsigned char const*, unsigned char const*, unsigned long, unsigned char) main.cpp:32 (CPlusPlusTester:x86_64+0x1000018e2)
    #1 main main.cpp:47 (CPlusPlusTester:x86_64+0x100001fa1)

  Location is stack of main thread.

  Thread T4 (tid=669186, running) created by main thread at:
    #0 pthread_create &lt;null&gt;:2673600 (libclang_rt.tsan_osx_dynamic.dylib:x86_64h+0x2a17d)
    #1 std::__1::__libcpp_thread_create(_opaque_pthread_t**, void* (*)(void*), void*) __threading_support:328 (CPlusPlusTester:x86_64+0x10000593e)
    #2 std::__1::thread::thread&lt;process(unsigned char const*, unsigned char const*, unsigned long, unsigned char)::$_0, void&gt;(process(unsigned char const*, unsigned char const*, unsigned long, unsigned char)::$_0&amp;&amp;) thread:368 (CPlusPlusTester:x86_64+0x1000055e7)
    #3 std::__1::thread::thread&lt;process(unsigned char const*, unsigned char const*, unsigned long, unsigned char)::$_0, void&gt;(process(unsigned char const*, unsigned char const*, unsigned long, unsigned char)::$_0&amp;&amp;) thread:360 (CPlusPlusTester:x86_64+0x100001ad8)
    #4 process(unsigned char const*, unsigned char const*, unsigned long, unsigned char) main.cpp:33 (CPlusPlusTester:x86_64+0x10000189f)
    #5 main main.cpp:47 (CPlusPlusTester:x86_64+0x100001fa1)

SUMMARY: ThreadSanitizer: data race main.cpp:34 in process(unsigned char const*, unsigned char const*, unsigned long, unsigned char)::$_0::operator()() const


Line 34 is the call to process_element(). @pschill pointed out: 


  The lambda captures all variables by reference, including i. So if the thread starts a little bit too late, the for loop already incremented i and the call to process_element recieves the wrong value. A solution would be changing the lambda capture from [&amp;] to [&amp;, i], so that i is captured by value.


You ask:


  Is this just an artifact of the fact that process_element is very simple and takes almost no time at all, or will the output in general be ordered according to the order in which I run the threads?


I think it's just because there's so little work being done that the threads end up executing in order. One is probably done before the next is even started.