fork(3) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <list>
  4. #include <deque>
  5. #include <iterator>
  6. #include <cassert>
  7. using namespace std;
  8.  
  9. //Forward declarations:
  10. template<typename Container> const typename Container::value_type&
  11. getNthElement(const Container& container, size_t n);
  12. template<typename Container> const typename Container::value_type&
  13. getNthElementImpl(const Container& container, size_t n, random_access_iterator_tag);
  14. template<typename Container> const typename Container::value_type&
  15. getNthElementImpl(const Container& container, size_t n, forward_iterator_tag);
  16.  
  17. int main() {
  18.   assert(getNthElement(vector<int>{0, 1, 2, 3, 4}, 3) == 3);
  19.   assert(getNthElement(list<int>{0, 1, 2, 3, 4}, 3) == 3);
  20.   assert(getNthElement(deque<int>{0, 1, 2, 3, 4}, 3) == 3);
  21.   return 0;
  22. }
  23.  
  24.  
  25. template<typename Container> const typename Container::value_type&
  26. getNthElement(const Container& container, size_t n) {
  27.   auto tag = typename iterator_traits<typename Container::iterator>::iterator_category{};
  28.   return getNthElementImpl(container, n, tag);
  29. }
  30.  
  31. template<typename Container> const typename Container::value_type&
  32. getNthElementImpl(const Container& container, size_t n, random_access_iterator_tag) {
  33.   cout << "O(1) implementation used" << endl;
  34.   auto iteratorToNthElement = begin(container) + n;
  35.   return *iteratorToNthElement;
  36. }
  37.  
  38. template<typename Container> const typename Container::value_type&
  39. getNthElementImpl(const Container& container, size_t n, forward_iterator_tag) {
  40.   cout << "O(N) implementation used" << endl;
  41.   auto itr = begin(container);
  42.   for (auto i = 0u; i < n; ++i) {
  43.     ++itr;
  44.   }
  45.   return *itr;
  46. }
  47.  
Success #stdin #stdout 0s 3432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
O(1) implementation used
O(N) implementation used
O(1) implementation used
https://ideone.com/NduJ32
language:
C++14 (gcc 8.3)
created:
9 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!