Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


iMalc

Member Since 05 Mar 2004
Offline Last Active May 03 2015 02:43 AM

Topics I've Started

Detecting if std::swap is specialised (C++)

04 February 2011 - 02:55 PM

Hi all.
I came upon an interesting conundrum yesterday. I realised that when writing generic (i.e. templated) code for things such as sorting algorithms (a hobby of mine) that it would be useful to know whether or not a given data type has a specialised std::swap.
Take for example an insertion sort algorithm. When moving items over to insert an item into place there are two ways of doing it:

1. We can copy the item that we want to insert into a temporary variable, then move items over using one assignment operator call for each one, and then copy the desired item into its place. Or...
2. We can use std::swap to shuffle all those items along until we find the spot where the item should be inserted.

Now for a type which does not have std::swap specialised, (e.g. double) option 1 is the best because most items can be moved with just one assignment operator call. If we used std::swap then moving each item would involve three assignments.
However, for a type which does have std::swap specialised, such as a vector or other such class that has a throwing asignment operator but non-throwing std::swap, option 2 is better and more efficient. With option 2 we can in fact go as far as performing the whole thing without ever invoking the assignment operator. But with option 1 we invoke the potentially expensive and throwing assignment operator many times.

Now the question is. Is there a way of detecting if std::swap is specialised for a given type? Perhaps using SFINAE?
Any other thoughts?

In case it helps, some code for thought:
template <typename T>
void InsertionSort1(T a[], int n) {
    for (int i = 1; i < n; ++i) {
        if (a[i] < a[i - 1]) {
            int j = i - 1;
            const T tempItem = a[i];
            do {
                a[j + 1] = a[j];
                --j;
            } while (j >= 0 && tempItem < a[j]);
            a[j + 1] = tempItem;
        }
    }
}

template <typename T>
void InsertionSort2(T a[], int n) {
    for (int i = 1; i < n; ++i) {
        if (a[i] < a[i - 1]) {
            int j = i - 1;
            T tempItem;
            std::swap(tempItem, a[i]);
            do {
                std::swap(a[j + 1], a[j]);
                --j;
            } while (j >= 0 && tempItem < a[j]);
            std::swap(a[j + 1], tempItem);
        }
    }
}

[C++] Function References

06 March 2010 - 07:41 AM

It just recently came to my attention that there are probably a lot of C++ programmers out there that don't know about function references. People discuss function pointers from time to time, but almost never discuss function referencs. It's hard to find any info about them on the web too. I've actually been using them for a few years now. Example usage:
typedef int Func(int x);

int bar2(int x) { return x*2; }
int bar3(int x) { return x*3; }

void foo(Func &foobar)
{
    std::cout << foobar(5);
}

int main()
{
    foo(bar2);
    foo(bar3);
}
As you can see, they are actually cleaner to use than function pointers! Also, just like the difference between regular pointers and references, function references can't be made to point to a different function, and can't be NULL. Surely they'd thererfore allow for more optimisation possibilities? The only thing that isn't the same as regular references is that there's no usefulness to making them const. i.e.
void foo(const Func &foobar)
Such code causes the following in VS2008:
warning C4180: qualifier applied to function type has no meaning; ignored
Does anyone have any thoughts as to why they might not be very popular? Should we actually be preferring these over function pointers for the same reasons that we should prefer regular references over pointers? Do they work equally as well on all compilers?

Slow web page scrolling only on this site

11 December 2009 - 07:37 AM

Has anyone else noticed extremely slow redraw speed when scrolling on this site? This is really odd. It takes about a second to draw the whole page for each scroll using the mouse wheel. I have to scroll a little bit and then wait for it to redraw, and then continue, so I don't get totally lost. It's running about the speed redrawing goes when you don't have graphics card drivers installed, or worse. But I have the latest drivers for my graphics card installed, and update them regularly. Secondly, it happens for every page I go to on this site and only this site. Every other web page I visit the scrolling is virtually instantaneous, but here it isn't even close to realtime. NVIDIA GeForce 9600 GT (driver 8.16.11.9107), Windows Vista Home Premium, Internet Explorer 8. It's an overall pretty fast machine, Windows experience rating 5.6: AMD Athlon II X2 250 Processor @ 3.00GHz, 4GB Ram, 32-bit OS So, is this happening for anyone else, and does anyone have any idea what causes it? Does anyone else use this same configuration successfully?

C++ Ternary operator question

01 January 2008 - 02:49 PM

Hi guys,
Something has just been bugging me today with regards to part of an implementation of Merge Sort, whereby the merging loop uses the ternary operator. I suddenly had the thought that my code might actually be undefined behaviour. I initially thought it was fine, but now I'm not sure. The line of code in question is:
        sortArr[c++] = (rightArr[b] < leftArr[a]) ? rightArr[b++] : leftArr[a++];
The assumption this code makes is that only either rightArr[b++] OR leftArr[a++] is executed.

Now, all is fine and dandy when the second and third expressions used in the ternary operator don't have side effects. E.g.
int foo = (bar == 42) ? 10 : 20;
But can someone check the standard and see if it is possible that in the first example I gave that both a and b might be incremented? It is working as desired in VS2005 Express, but I'm worried that even though only the result of one of those expressions will be assigned to sortArr[c++], that it might actually evaluate both anyway, on a different compiler and increment a and b.

I guess a simpler example that hilights the issue would be:
int foo = (bar == 42) ? a++ : b++;
The reason I'm particularly unsure whether it will execute only one of the side effects is that when using the ternary operator in template meta-programming in the past I've seen evidence that it evaluates both sides.

I've done a bit of a search on the net, but couldn't find anything that goes into enough detail to answer my question. Perhaps I just need some reasusrance.

Notepad - WTF!!!

03 April 2007 - 10:32 PM

I was just busy making some batch scripts for compiling some D stuff. Actually I've just installed the thing and are trying to compile tango examples. (probably not important) Anyway one of the bat files I wrote contains exactly the following (48 chars):
\dmd\bin\build dmd/tango/example/console/hello.d
When I open this file in wordpad, everything is as you would expect (in English). But when I open it up in notepad... you're not going to believe this... The whole thing is in Chinese![totally][totally][totally] 摜摭扜湩扜極摬搠摭琯湡潧支慸灭敬振湯潳敬栯汥潬搮 I have a totally English OS install, and have nothing foreign selected in any regional settings etc. I've retyped this from scratch over again and it does the same thing. If I add extra characters from wordpad, or change some characters it displays correctly in English. The file name and extension makes no difference. Out of interest I used google translator to translate the Chinese back to English and got this: Brief fling degrees Breast degrees daub 摭 acting very revered King 湡 潧 support 慸 eliminate vibration King Huazhong 汥 潬 determine 潳 Can someone please please let me know if it is just my PC that has lost the plot!

PARTNERS