title: "Not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation"
body: <p>I'm beginning a program using heaps in which I must insertSort, mergeSort, and quickSort into the heap. I was instructed to use the code from my textbook as a basis and I cannot even get the example code to compile. I keep receiving the error:</p>
  
  <pre><code>not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation
  </code></pre>
  
  <p>Now I think it has something to do with the order in which the template&lt;> classes were declared in the Sort.h file. However, I can't imagine a textbook would publish code that simply doesn't compile. Would you guys mind taking a look?</p>
  
  <p>Full errors: </p>
  
  <pre><code>In file included from Driver.cpp:4:0:
  Sort.h: In instantiation of 'void heapsort(std::vector&lt;Comparable&gt;&amp;) [with Comparable = int]':
  Driver.cpp:47:21:   required from here
  Sort.h:79:9: error: 'percDown' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation [-fpermissive]
  Sort.h:104:6: note: 'template&lt;class Comparable&gt; void percDown(std::vector&lt;Comparable&gt;&amp;, int, int)' declared here, later in the translation unit
  Sort.h:83:9: error: 'percDown' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation [-fpermissive]
  Sort.h:104:6: note: 'template&lt;class Comparable&gt; void percDown(std::vector&lt;Comparable&gt;&amp;, int, int)' declared here, later in the translation unit
  Sort.h: In instantiation of 'void mergeSort(std::vector&lt;Comparable&gt;&amp;, std::vector&lt;Comparable&gt;&amp;, int, int) [with Comparable = int]':
  Sort.h:150:5:   required from 'void mergeSort(std::vector&lt;Comparable&gt;&amp;) [with Comparable = int]'
  Driver.cpp:53:22:   required from here
  Sort.h:138:9: error: 'merge' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation [-fpermissive]
  Sort.h:163:6: note: 'template&lt;class Comparable&gt; void merge(std::vector&lt;Comparable&gt;&amp;, std::vector&lt;Comparable&gt;&amp;, int, int, int)' declared here, later in the translation unit
  </code></pre>
  
  <p>Sort.h:</p>
  
  <pre><code>#ifndef SORT_H
  #define SORT_H
  
  /**
   * Several sorting routines.
   * Arrays are rearranged with smallest item first.
   */
  
  #include &lt;vector&gt;
  #include &lt;functional&gt;
  using namespace std;
  
  /**
   * Simple insertion sort.
   */
  template &lt;typename Comparable&gt;
  void insertionSort( vector&lt;Comparable&gt; &amp; a )
  {
      for( int p = 1; p &lt; a.size( ); ++p )
      {
          Comparable tmp = std::move( a[ p ] );
  
          int j;
          for( j = p; j &gt; 0 &amp;&amp; tmp &lt; a[ j - 1 ]; --j )
              a[ j ] = std::move( a[ j - 1 ] );
          a[ j ] = std::move( tmp );
      }
  }
  
  
  /**
   * Internal insertion sort routine for subarrays
   * that is used by quicksort.
   * a is an array of Comparable items.
   * left is the left-most index of the subarray.
   * right is the right-most index of the subarray.
   */
  template &lt;typename Comparable&gt;
  void insertionSort( vector&lt;Comparable&gt; &amp; a, int left, int right )
  {
      for( int p = left + 1; p &lt;= right; ++p )
      {
          Comparable tmp = std::move( a[ p ] );
          int j;
  
          for( j = p; j &gt; left &amp;&amp; tmp &lt; a[ j - 1 ]; --j )
              a[ j ] = std::move( a[ j - 1 ] );
          a[ j ] = std::move( tmp );
      }
  }
  
  
  
  /**
   * Shellsort, using Shell's (poor) increments.
   */
  template &lt;typename Comparable&gt;
  void shellsort( vector&lt;Comparable&gt; &amp; a )
  {
      for( int gap = a.size( ) / 2; gap &gt; 0; gap /= 2 )
          for( int i = gap; i &lt; a.size( ); ++i )
          {
              Comparable tmp = std::move( a[ i ] );
              int j = i;
  
              for( ; j &gt;= gap &amp;&amp; tmp &lt; a[ j - gap ]; j -= gap )
                  a[ j ] = std::move( a[ j - gap ] );
              a[ j ] = std::move( tmp );
          }
  }
  
  /**
   * Standard heapsort.
   */
  template &lt;typename Comparable&gt;
  void heapsort( vector&lt;Comparable&gt; &amp; a )
  {
      for( int i = a.size( ) / 2 - 1; i &gt;= 0; --i )  /* buildHeap */
          percDown( a, i, a.size( ) );
      for( int j = a.size( ) - 1; j &gt; 0; --j )
      {
          std::swap( a[ 0 ], a[ j ] );               /* deleteMax */
          percDown( a, 0, j );
      }
  }
  
  /**
   * Internal method for heapsort.
   * i is the index of an item in the heap.
   * Returns the index of the left child.
   */
  inline int leftChild( int i )
  {
      return 2 * i + 1;
  }
  
  /**
   * Internal method for heapsort that is used in
   * deleteMax and buildHeap.
   * i is the position from which to percolate down.
   * n is the logical size of the binary heap.
   */
  template &lt;typename Comparable&gt;
  void percDown( vector&lt;Comparable&gt; &amp; a, int i, int n )
  {
      int child;
      Comparable tmp;
  
      for( tmp = std::move( a[ i ] ); leftChild( i ) &lt; n; i = child )
      {
          child = leftChild( i );
          if( child != n - 1 &amp;&amp; a[ child ] &lt; a[ child + 1 ] )
              ++child;
          if( tmp &lt; a[ child ] )
              a[ i ] = std::move( a[ child ] );
          else
              break;
      }
      a[ i ] = std::move( tmp );
  }
  
  /**
   * Internal method that makes recursive calls.
   * a is an array of Comparable items.
   * tmpArray is an array to place the merged result.
   * left is the left-most index of the subarray.
   * right is the right-most index of the subarray.
   */
  template &lt;typename Comparable&gt;
  void mergeSort( vector&lt;Comparable&gt; &amp; a,
                  vector&lt;Comparable&gt; &amp; tmpArray, int left, int right )
  {
      if( left &lt; right )
      {
          int center = ( left + right ) / 2;
          mergeSort( a, tmpArray, left, center );
          mergeSort( a, tmpArray, center + 1, right );
          merge( a, tmpArray, left, center + 1, right );
      }
  }
  
  /**
   * Mergesort algorithm (driver).
   */
  template &lt;typename Comparable&gt;
  void mergeSort( vector&lt;Comparable&gt; &amp; a )
  {
      vector&lt;Comparable&gt; tmpArray( a.size( ) );
  
      mergeSort( a, tmpArray, 0, a.size( ) - 1 );
  }
  
  
  /**
   * Internal method that merges two sorted halves of a subarray.
   * a is an array of Comparable items.
   * tmpArray is an array to place the merged result.
   * leftPos is the left-most index of the subarray.
   * rightPos is the index of the start of the second half.
   * rightEnd is the right-most index of the subarray.
   */
  template &lt;typename Comparable&gt;
  void merge( vector&lt;Comparable&gt; &amp; a, vector&lt;Comparable&gt; &amp; tmpArray,
              int leftPos, int rightPos, int rightEnd )
  {
      int leftEnd = rightPos - 1;
      int tmpPos = leftPos;
      int numElements = rightEnd - leftPos + 1;
  
      // Main loop
      while( leftPos &lt;= leftEnd &amp;&amp; rightPos &lt;= rightEnd )
          if( a[ leftPos ] &lt;= a[ rightPos ] )
              tmpArray[ tmpPos++ ] = std::move( a[ leftPos++ ] );
          else
              tmpArray[ tmpPos++ ] = std::move( a[ rightPos++ ] );
  
      while( leftPos &lt;= leftEnd )    // Copy rest of first half
          tmpArray[ tmpPos++ ] = std::move( a[ leftPos++ ] );
  
      while( rightPos &lt;= rightEnd )  // Copy rest of right half
          tmpArray[ tmpPos++ ] = std::move( a[ rightPos++ ] );
  
      // Copy tmpArray back
      for( int i = 0; i &lt; numElements; ++i, --rightEnd )
          a[ rightEnd ] = std::move( tmpArray[ rightEnd ] );
  }
  
  
  /**
   * Return median of left, center, and right.
   * Order these and hide the pivot.
   */
  template &lt;typename Comparable&gt;
  const Comparable &amp; median3( vector&lt;Comparable&gt; &amp; a, int left, int right )
  {
      int center = ( left + right ) / 2;
  
      if( a[ center ] &lt; a[ left ] )
          std::swap( a[ left ], a[ center ] );
      if( a[ right ] &lt; a[ left ] )
          std::swap( a[ left ], a[ right ] );
      if( a[ right ] &lt; a[ center ] )
          std::swap( a[ center ], a[ right ] );
  
          // Place pivot at position right - 1
      std::swap( a[ center ], a[ right - 1 ] );
      return a[ right - 1 ];
  }
  
  /**
   * Internal quicksort method that makes recursive calls.
   * Uses median-of-three partitioning and a cutoff of 10.
   * a is an array of Comparable items.
   * left is the left-most index of the subarray.
   * right is the right-most index of the subarray.
   */
  template &lt;typename Comparable&gt;
  void quicksort( vector&lt;Comparable&gt; &amp; a, int left, int right )
  {
      if( left + 10 &lt;= right )
      {
          const Comparable &amp; pivot = median3( a, left, right );
  
              // Begin partitioning
          int i = left, j = right - 1;
          for( ; ; )
          {
              while( a[ ++i ] &lt; pivot ) { }
              while( pivot &lt; a[ --j ] ) { }
              if( i &lt; j )
                  std::swap( a[ i ], a[ j ] );
              else
                  break;
          }
  
          std::swap( a[ i ], a[ right - 1 ] );  // Restore pivot
  
          quicksort( a, left, i - 1 );     // Sort small elements
          quicksort( a, i + 1, right );    // Sort large elements
      }
      else  // Do an insertion sort on the subarray
          insertionSort( a, left, right );
  }
  
  /**
   * Quicksort algorithm (driver).
   */
  template &lt;typename Comparable&gt;
  void quicksort( vector&lt;Comparable&gt; &amp; a )
  {
      quicksort( a, 0, a.size( ) - 1 );
  }
  
  
  /**
   * Internal selection method that makes recursive calls.
   * Uses median-of-three partitioning and a cutoff of 10.
   * Places the kth smallest item in a[k-1].
   * a is an array of Comparable items.
   * left is the left-most index of the subarray.
   * right is the right-most index of the subarray.
   * k is the desired rank (1 is minimum) in the entire array.
   */
  template &lt;typename Comparable&gt;
  void quickSelect( vector&lt;Comparable&gt; &amp; a, int left, int right, int k )
  {
      if( left + 10 &lt;= right )
      {
          const Comparable &amp; pivot = median3( a, left, right );
  
              // Begin partitioning
          int i = left, j = right - 1;
          for( ; ; )
          {
              while( a[ ++i ] &lt; pivot ) { }
              while( pivot &lt; a[ --j ] ) { }
              if( i &lt; j )
                  std::swap( a[ i ], a[ j ] );
              else
                  break;
          }
  
          std::swap( a[ i ], a[ right - 1 ] );  // Restore pivot
  
              // Recurse; only this part changes
          if( k &lt;= i )
              quickSelect( a, left, i - 1, k );
          else if( k &gt; i + 1 )
              quickSelect( a, i + 1, right, k );
      }
      else  // Do an insertion sort on the subarray
          insertionSort( a, left, right );
  }
  
  /**
   * Quick selection algorithm.
   * Places the kth smallest item in a[k-1].
   * a is an array of Comparable items.
   * k is the desired rank (1 is minimum) in the entire array.
   */
  template &lt;typename Comparable&gt;
  void quickSelect( vector&lt;Comparable&gt; &amp; a, int k )
  {
      quickSelect( a, 0, a.size( ) - 1, k );
  }
  
  
  template &lt;typename Comparable&gt;
  void SORT( vector&lt;Comparable&gt; &amp; items )
  {
      if( items.size( ) &gt; 1 )
      {
          vector&lt;Comparable&gt; smaller;
          vector&lt;Comparable&gt; same;
          vector&lt;Comparable&gt; larger;
  
          auto chosenItem = items[ items.size( ) / 2 ];
  
          for( auto &amp; i : items )
          {
              if( i &lt; chosenItem )
                  smaller.push_back( std::move( i ) );
              else if( chosenItem &lt; i )
                  larger.push_back( std::move( i ) );
              else
                  same.push_back( std::move( i ) );
          }
  
          SORT( smaller );     // Recursive call!
          SORT( larger );      // Recursive call!
  
          std::move( begin( smaller ), end( smaller ), begin( items ) );
          std::move( begin( same ), end( same ), begin( items ) + smaller.size( ) );
          std::move( begin( larger ), end( larger ), end( items ) - larger.size( ) );
  
  /*
          items.clear( );
          items.insert( end( items ), begin( smaller ), end( smaller ) );
          items.insert( end( items ), begin( same ), end( same ) );
          items.insert( end( items ), begin( larger ), end( larger ) );
  */
      }
  }
  
  /*
   * This is the more public version of insertion sort.
   * It requires a pair of iterators and a comparison
   * function object.
   */
  template &lt;typename RandomIterator, typename Comparator&gt;
  void insertionSort( const RandomIterator &amp; begin,
                      const RandomIterator &amp; end,
                      Comparator lessThan )
  {
      if( begin == end )
          return;
  
      RandomIterator j;
  
      for( RandomIterator p = begin+1; p != end; ++p )
      {
          auto tmp = std::move( *p );
          for( j = p; j != begin &amp;&amp; lessThan( tmp, *( j-1 ) ); --j )
              *j = std::move( *(j-1) );
          *j = std::move( tmp );
      }
  }
  
  /*
   * The two-parameter version calls the three parameter version, using C++11 decltype
   */
  template &lt;typename RandomIterator&gt;
  void insertionSort( const RandomIterator &amp; begin,
                      const RandomIterator &amp; end )
  {
      insertionSort( begin, end, less&lt;decltype(*begin )&gt;{ } );
  }
  
  
  
  #endif
  </code></pre>
  
  <p>And Driver.cpp</p>
  
  <p>//Driver.cpp</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include "Sort.h"
  #include &lt;vector&gt;
  #include &lt;string&gt;
  #include &lt;time.h&gt; 
  
  using namespace std;
  
  void checkSort( const vector&lt;int&gt; &amp; a )
  {
      for( int i = 0; i &lt; a.size( ); ++i )
          if(a.size( ) != i )
              cout &lt;&lt; "Error at " &lt;&lt; i &lt;&lt; endl;
      cout &lt;&lt; "Finished checksort" &lt;&lt; endl;
  }
  
  int main( )
  {
      srand(time(NULL)); 
  
      int vec_length;
  
      cout &lt;&lt; "What would you like the length of the vector to be?" &lt;&lt; endl;
      cin &gt;&gt; vec_length;
  
      vector&lt;int&gt; a(vec_length);
  
      for(int i = 0; i &lt; a.size(); i++)
      {
          a[i] = rand() % 100 + 1;
      }
  
      //vector&lt;string&gt; a( NUM_ITEMS );        // This input adds factor of N to running time
      //for( int i = 1; i &lt; a.size( ); ++i )  // but we want to test std::move logic
        //  a[ i ] = a[ i - 1 ] + 'a';
  
      for( int theSeed = 0; theSeed &lt; 10; ++theSeed )
      {
          insertionSort( a );
          checkSort( a );
  
          insertionSort( begin( a ), end( a ) );
          checkSort( a );
  
          heapsort( a );
          checkSort( a );
  
          shellsort( a );
          checkSort( a );
  
          mergeSort( a );
          checkSort( a );
  
          quicksort( a );
          checkSort( a );
  
          SORT( a );
          checkSort( a );
  
          quickSelect( a, vec_length / 2 );
          //cout &lt;&lt; a[vec_length / 2 - 1].size( ) &lt;&lt; " " &lt;&lt; vec_length / 2 &lt;&lt; endl;
      }
  
      cout &lt;&lt; "Checking SORT, Fig 7.13" &lt;&lt; endl;
      int N = vec_length * vec_length;
      vector&lt;int&gt; b( N );
      for( int i = 0; i &lt; N; ++i )
          b[ i ] = i;
      SORT( b );
      for( int i = 0; i &lt; N; ++i )
          if( b[ i ] != i )
              cout &lt;&lt; "OOPS!!" &lt;&lt; endl;
  
      return 0;
  }
  </code></pre>