swap()? (g++)

This is a discussion on swap()? (g++) within the C++ Programming forums, part of the General Programming Boards category; EDIT: This problem has been solved. I didn't notice that "swap" identifier had been overloaded in bubblesort(). :blush: The error ...

  1. #1
    Registered User
    Join Date
    Mar 2006
    Posts
    725

    swap()? (g++) {SOLVED}

    EDIT: This problem has been solved.


    I didn't notice that "swap" identifier had been overloaded in bubblesort(). :blush: The error from g++ was rather cryptic, to say the least. Well, it's been solved. This thread may be closed/deleted/removed if necessary.





    So here I am, trying to implement bubblesort (for fun, what else is bubblesort good for ):

    Code:
    template <classname>
    void swap(classname &x, classname &y)
    {
    	classname temp = x;
    	x = y;
    	y = temp;
    }
    
    template <class iterator>
    void bubblesort(iterator start, iterator end)
    {
    	bool swapped = true;
    	iterator swap;
    	for(iterator i = end; i != start && swapped; --i)
    	{
    		swapped = false;
    		iterator j = start, k = start;
    		++k;
    		for(; k != i; ++j, ++k)
    		{
    			if(*k < *j)
    			{
    				swap(*j, *k);
    				swapped = true;
    			}
    		}
    	}
    }
    
    int main()
    {
    	int array[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    	bubblesort(array, array + 10);
    }
    In GCC it fails to compile:
    Code:
    In function `void bubblesort(iterator, iterator) [with iterator = int*]':
    `swap' cannot be used as a function
    Even when I specialize the functions to int types and int* iterators, it outputs more or less the same thing.

    When I remove swap() completely, gcc again produces the same error "`swap' cannot be used as a function".

    If you want it, here's is my build line:
    Code:
    g++.exe "test.cpp" -o "test.exe"
    -W -ansi  -I"lib\gcc\mingw32\3.4.2\include" -I"include\c++\3.4.2\backward"
    -I"include\c++\3.4.2\mingw32" -I"include\c++\3.4.2" -I"include" -L"lib" -s
    I'm compiling from Dev-C++ using MinGW 3.4.2, by the way.
    Last edited by jafet; 07-29-2006 at 10:13 PM.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Note that there's a function in the standard library called swap() which does exactly what you want. This might lead to ambiguity errors on compilers that properly implement two-phase lookup if you sort anything from namespace std, such as std::string or std::complex. (Not that std::complex can be sorted ...)
    Anyway, you should either
    1) just use the std::sort function (it's optimized for various types, such as std::string) or
    2) completely qualify the call to your swap() in bubblesort as ::swap(*j, *k).
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    I knew that. I just didn't want my sort algorithms to rely on the standard library. And I was re-implementing many major algorithms, for practice. I tried to make a variety of drop-in iterator-based std::sort replacements. I just finished a while ago, with introsort. That way, I've learned a lot about how shellsort and heapsort work, and how quicksort partitions in-place.

    I put all the functions into a namespace sort{}, to avoid the conflicts you mentioned. I just didn't include them in the posted code.

    Introsort is still around half as fast as std::sort! Well, that's a start, at least that means I'm already half as good as the standards commitee
    Last edited by jafet; 08-05-2006 at 04:49 PM.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  4. #4
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,438
    Quote Originally Posted by jafet
    Introsort is still around half as fast as std::sort! Well, that's a start, at least that means I'm already half as good as the standards commitee
    Introsort is what's behind std::sort so you may want to recheck your implementation.

    Also, since std::sort runs at O(N log(N)) you will have an hard time predicting your algorithm speed against std::sort in such accurate terms as "half as fast"
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  5. #5
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    As in "half" I meant the constant factor. As you know, big-O isn't so big at measuring those. I know it's half because I benchmarked both at varying input sizes. Haven't had time to test against quicksort killer sequences yet... prolly never will.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list swap function
    By Axel in forum C Programming
    Replies: 32
    Last Post: 01-16-2011, 08:40 AM
  2. Atomic compare and swap.
    By Maz in forum C Programming
    Replies: 3
    Last Post: 04-07-2009, 02:47 PM
  3. using swap to make assignment operator exception safe
    By George2 in forum C++ Programming
    Replies: 9
    Last Post: 01-10-2008, 05:32 AM
  4. Double Link List Swap function
    By kennny2004 in forum C++ Programming
    Replies: 1
    Last Post: 04-12-2006, 11:52 AM
  5. Skipping DX swap chain node - not good...
    By Magos in forum Game Programming
    Replies: 0
    Last Post: 03-02-2006, 07:37 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21