fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <list>
  4. #include <cstring>
  5. #include <iterator>
  6. #include <type_traits>
  7. #include <algorithm> //for std::equal
  8. #include <cassert>
  9.  
  10. using std::cout;
  11. using std::endl;
  12. using std::boolalpha;
  13. using std::vector;
  14. using std::list;
  15. using std::equal;
  16. using std::memmove;
  17. using std::begin;
  18. using std::end;
  19. using std::distance;
  20. using std::back_inserter;
  21. using std::true_type;
  22. using std::is_pointer;
  23. using std::is_same;
  24.  
  25. //Would prefer std::is_trivally_copyable, but libstdc++ hasn't implemented it yet.
  26. using std::is_literal_type;
  27.  
  28.  
  29. /*
  30.  
  31.   This code demonstrates the use of tag-dispatch to internally optimize std::copy
  32.   by calling std::memcpy as an implementation detail whenever it is safe to do so.
  33.  
  34.   Tag-dispatch is a technique whereby you use type traits to select a function
  35.   implementation at compile-time by leveraging overloading.
  36.  
  37.   I chose to use 4 type-traits to make the determination of whether or not it is
  38.   safe. You may be able to optimize for more cases if you used more, or a different
  39.   set of, traits.
  40.  
  41.   -Mark
  42.  
  43.  */
  44.  
  45. namespace mine { //Kill compiler error because of libstdc++ bug (somehow std::copy was in scope)
  46.  
  47. //Declarations:
  48. template<typename InputIt, typename OutputIt>
  49. OutputIt copy(InputIt in_first, InputIt in_last, OutputIt out_first);
  50.  
  51. namespace detail {
  52.  
  53. template<typename InputIt, typename OutputIt>
  54. OutputIt copyImpl(InputIt in_first, InputIt in_last, OutputIt out_first,
  55.                   true_type, true_type, true_type, true_type);
  56.  
  57. template<typename InputIt, typename OutputIt,
  58.          typename InputIsPointerTag, typename OutputIsPointerTag,
  59.          typename SameTypesTag, typename TriviallyCopyableTag>
  60. OutputIt copyImpl(InputIt in_first, InputIt in_last, OutputIt out_first,
  61.                   InputIsPointerTag, OutputIsPointerTag, SameTypesTag, TriviallyCopyableTag);
  62.  
  63. } //!detail
  64. } //!mine
  65.  
  66.  
  67.  
  68. int main() {
  69.   {
  70.     int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  71.     int b[10];
  72.     mine::copy(begin(a), end(a), begin(b));
  73.     assert(equal(begin(a), end(a), begin(b)));
  74.   }
  75.   {
  76.     vector<int> a { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  77.     vector<int> b;
  78.     b.resize(10);
  79.     mine::copy(begin(a), end(a), begin(b));
  80.     assert(equal(begin(a), end(a), begin(b)));
  81.   }
  82.   {
  83.     list<int> a { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  84.     list<int> b;
  85.     mine::copy(begin(a), end(a), back_inserter(b));
  86.     assert(equal(begin(a), end(a), begin(b)));
  87.   }
  88.  
  89.   return 0;
  90. }
  91.  
  92.  
  93.  
  94. namespace mine {
  95.  
  96. template<typename InputIt, typename OutputIt>
  97. OutputIt copy(InputIt in_first, InputIt in_last, OutputIt out_first) {
  98.   using InputElementType = decltype(*in_first);
  99.   using OutputElementType = decltype(*out_first);
  100.  
  101.   cout << boolalpha
  102.        << "\nInput iterator is pointer:\t"
  103.        << is_pointer<InputIt>::value << '\n'
  104.        << "Output iterator is pointer:\t"
  105.        << is_pointer<OutputIt>::value << '\n'
  106.        << "Input and output iterators deref to the same type:\t"
  107.        << is_same<InputElementType, OutputElementType>::value << '\n'
  108.        << "Element is trivially copyable:\t"
  109.        << is_literal_type<InputElementType>::value << '\n' << endl;
  110.  
  111.   //Use tag-dispatch technique to select the right implementation function.
  112.   //The objects we create for tag dispatch will be optimized out at compile-time.
  113.   detail::copyImpl(in_first, in_last, out_first,
  114.                    typename is_pointer<InputIt>::type{},
  115.                    typename is_pointer<OutputIt>::type{},
  116.                    typename is_same<InputElementType, OutputElementType>::type{},
  117.                    typename is_literal_type<InputElementType>::type{});
  118. }
  119.  
  120.  
  121.  
  122. namespace detail {
  123.  
  124. //The input and output ranges are contiguous, both contain elements of type T and elements are trivially copyable:
  125. template<typename InputIt, typename OutputIt>
  126. OutputIt copyImpl(InputIt in_first, InputIt in_last, OutputIt out_first,
  127.               true_type, true_type, true_type, true_type) {
  128.  
  129.   cout << "Chose memset optimized version" << endl;
  130.  
  131.   auto numberOfElements = distance(in_first, in_last);
  132.   auto numberOfBytes = numberOfElements * sizeof(*in_first);
  133.   //We actually need to use memmove because the range requirements differ between
  134.   //memcpy and copy. You could further optimize to call memcpy in certain safe cases.
  135.   memmove(out_first, in_first, numberOfBytes);
  136. }
  137.  
  138. //All other cases:
  139. template<typename InputIt, typename OutputIt,
  140.          typename InputIsPointerTag, typename OutputIsPointerTag,
  141.          typename SameTypesTag, typename TriviallyCopyableTag>
  142. OutputIt copyImpl(InputIt in_first, InputIt in_last, OutputIt out_first,
  143.               InputIsPointerTag, OutputIsPointerTag, SameTypesTag, TriviallyCopyableTag) {
  144.  
  145.   cout << "Chose the safe, but general version" << endl;
  146.  
  147.   auto curInItr = in_first;
  148.   auto curOutItr = out_first;
  149.   while(curInItr != in_last) {
  150.     *curOutItr = *curInItr;
  151.     ++curInItr;
  152.     ++curOutItr;
  153.   }
  154. }
  155.  
  156. } //!detail
  157. } //!mine
  158.  
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Input iterator is pointer:	true
Output iterator is pointer:	true
Input and output iterators deref to the same type:	true
Element is trivially copyable:	true

Chose memset optimized version

Input iterator is pointer:	false
Output iterator is pointer:	false
Input and output iterators deref to the same type:	true
Element is trivially copyable:	true

Chose the safe, but general version

Input iterator is pointer:	false
Output iterator is pointer:	false
Input and output iterators deref to the same type:	false
Element is trivially copyable:	true

Chose the safe, but general version
https://ideone.com/AK5Faw
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

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!