templated function doesn't work

[nuderobmonkey]

I had written a sorting function that worked fine. But then I tried to make it templated and but don't got it right.

#include <iostream>
#include <utility>
#include <cstdlib>
#include <vector>
//#include "sort.hpp"

// sort.cpp
template <typename T>
void bubble_sort( T * start, T * end)
{
    for( int i = 0; i < end-start; ++i)
    {
        for( auto it = start; it < end-1; ++it)
        {
            if( *it > *(it+1))
            {
                T tmp = std::move( *it);
                *it = std::move( *(it+1));
                *(it+1) = std::move( tmp);
            }
        }
    }
}


int main()
{
    const int SIZE = 10;
    const int SEED =  0;
    
    std::vector<int> arr(SIZE);
    
    std::srand(SEED);
  
    for( size_t i = 0; i < SIZE; ++i)
    {
        arr[i] = std::rand() % 10;
        std::cout << arr[i] << (i < SIZE-1?',':' ');
    }
    
    bubble_sort<std::vector<int>>( arr.begin(), arr.end() );
    
    // output
    std::cout << "\nsorted to:\n";
    for( int i = 0;  i < SIZE;  ++i)
        std::cout << arr[i] << (i < SIZE-1?',':' ');
        std::cout << '\n';
 }

[Repeater]

bubble_sort<std::vector<int>>
Okay, so T is "std::vector<int>".

So the bubble_sort function becomes:

void bubble_sort(std::vector<int> * start, std::vector<int> * end)
{
    for( int i = 0; i < end-start; ++i)
    {
        for( auto it = start; it < end-1; ++it)
        {
            if( *it > *(it+1))
            {
                T tmp = std::move( *it);
                *it = std::move( *(it+1));
                *(it+1) = std::move( tmp);
            }
        }
    }
}

This templated function is expected two pointers to vectors as the input. This makes no sense.

[nuderobmonkey]

I have changed the sort algorithm to:

// sort.cpp
template <typename Iterator>
void bubble_sort( Iterator start, Iterator end)
{
    for( int i = 0; i < end-start; ++i)
    {
        for( auto it = start; it < end-1; ++it)
        {
            if( *it > *(it+1))
            {
                T tmp = std::move( *it);
                *it = std::move( *(it+1));
                *(it+1) = std::move( tmp);
            }
        }
    }
}

And Invoking with:
bubble_sort<std::vector<int>::iterator>( arr.begin(), arr.end() );

But now I have the problem that I cannot anymore Instantiate T tmp = std::move(*it) because there typename T is missed. If I add to it, invocation will become yet more complicated. But std::sort doesn't needs any template arguments. How could I make my sort algorithm working like std::sort?

[tpb]

Try auto instead of T. And just call it normally, like this:

bubble_sort(arr.begin(), arr.end());

[doug4]

Can you show us the original non-template function that worked fine? From that we can show you how to make it a template function.

[Thomas1965]

Why not keeping things simple ?

template <typename T>
void bubble_sort( T *data, size_t size )
{
  // use array subscript here to sort
}

To sort a vector you could call it like this: bubble.sort(v.data(), .size());

[nuderobmonkey]

@doug4 That's the original, which was implemented as a pure C function.

 void bubble_sort( int *arr,  int *end)
 {
     const int SIZE = end - arr;
     
     for( int i = 0;  i < SIZE-1;  ++i)
     {
         for( int k = 0;  k < SIZE-1; ++k)
         {
             if( arr[k] > arr[k+1])
             {
                 int tmp  = arr[k];
                 arr[k]   = arr[k+1];
                 arr[k+1] = tmp;
             }
         }
     }
 }

[tpb]

Maybe he wants it to have a standard container interface. And it works fine for c-style arrays, too.

#include <iostream>
#include <vector>
#include <cstdlib>

template<typename Iter>
void bubble_sort(Iter start, Iter end) {
    for (int i = 0; i < end - start; ++i)
        for (auto it = start; it < end - 1; ++it)
            if (*(it+1) < *it) {
                auto tmp = std::move(*it);
                *it = std::move(*(it+1));
                *(it+1) = std::move(tmp);
            }
}

int main() {
    const int SIZE = 10;
    const int SEED =  0;
    std::vector<int> arr(SIZE);
    std::srand(SEED);
  
    for( size_t i = 0; i < SIZE; ++i) {
        arr[i] = std::rand() % 10;
        std::cout << arr[i] << (i < SIZE-1?',':' ');
    }
    
    bubble_sort(arr.begin(), arr.end());

    std::cout << "\nsorted to:\n";
    for( int i = 0;  i < SIZE;  ++i)
        std::cout << arr[i] << (i < SIZE-1?',':' ');
    std::cout << '\n';

    int a[] {6, 2, 4, 9, 0, 7, 3, 1, 5, 8};
    bubble_sort(std::begin(a), std::end(a));   // or bubble_sort(a, a + 10);
    for (int n: a) std::cout << n << ' ';
    std::cout << '\n';
}

[nuderobmonkey]

Maybe he wants it to have a standard container interface.

That's it. Thanks for help @all.

[nuderobmonkey]

I've still a question:
Why we don't need to tell buble_sort for which type it needs to work? So why we needn't to write
bubble_sort<std::vector<int>::iterator>(...) ?

[mbozzi]

Why we don't need to tell bubble_sort for which type it needs to work?

Template argument deduction
https://en.cppreference.com/w/cpp/language/template_argument_deduction

By the way, if you need the type the iterator refers to for some reason and auto isn't suitable, you can get it like this: typename std::iterator_traits<Iterator>::value_type.