fork download
copy 
  1. #include <iostream>
  2. #include <list>
  3. #include <vector>
  4.  
  5. template <typename InIt1, typename InIt2, typename Compare = std::equal_to<>>
  6. bool is_subsequence(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, Compare cmp = Compare{})
  7. {
  8. 	if (first2 == last2) {
  9. 		return false; // sub empty (should this return true?)
  10. 	}
  11. 	for (; first1 != last1; ++first1) {
  12. 		if (cmp(*first1, *first2)) {
  13. 			if (++first2 == last2) {
  14. 				return true; // sub exhausted
  15. 			}
  16. 		}
  17. 	}
  18. 	return false; // seq exhausted
  19. }
  20.  
  21. template <typename Seq, typename Sub, typename Compare = std::equal_to<>>
  22. bool is_subsequence(const Seq &seq, const Sub &sub, Compare cmp = Compare{})
  23. {
  24. 	return is_subsequence(std::begin(seq), std::end(seq), std::begin(sub), std::end(sub), cmp);
  25. }
  26.  
  27. int main()
  28. {
  29.     std::vector<int> a = { 1, 2, 3, 4 }, b = { 2, 4 };
  30.     std::list<int> c = { 4, 2 };
  31.     std::vector<int> d = { 3, 6, 3, 1, 2, 3 };
  32.     int e[] = { 3, 1, 3 };
  33.  
  34.     std::cout << is_subsequence(a, b) << '\n';
  35.     std::cout << is_subsequence(a, b, [](int lhs, int rhs) { return lhs == rhs; }) << '\n';
  36.     std::cout << is_subsequence(a, c) << '\n';
  37.     std::cout << is_subsequence(d, e) << '\n';
  38. }
  39.  
Success #stdin #stdout 0s 3456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
1
0
1
https://ideone.com/mAPbc6
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!