Struggling with bind syntax

[Paul]

I am trying to write two versions of Quicksort, one that uses randomised partition, and one that doesn't randomise the partition. However, I want them to have signatures std::vector<int> f(std::vector<int> vec) and so I want to bind the quicksorts to Boolean parameters.

I can't find the syntax to do this though. Just so that I haven't left out any context, I will copy-paste my entire code. However, I will mark out the offending line with asterisks.
Many thanks for your help.

#include <vector>
#include <cstdlib>
#include <cstdio>
#include <stdexcept>
#include <functional>

// Basic swapping useful for many sorts.
void Swap(int& x, int& y)
{
int temp = x;
x = y;
y = temp;
}

// Creating a random integer array of size N.
// Integers are randomly chosen between 0 and randmax.
std::vector<int> CreateRandomArray(int N)
{
std::vector<int> data;

for(int i = 0; i < N; ++i)
data.push_back(rand());

return data;
}

// Testing our sorts by checking that every vector is sorted.
// True if sorted.
bool TestSort(const std::vector<int>& vec)
{
if(vec.empty())
return true;

for(int i = 0; i < vec.size() - 1; ++i)
if(vec[i] > vec[i + 1] )
return false;

return true;
}

// Testing a sort -- generalised for any function of the required type
bool TestSortGeneral( std::vector<int> (*const & f)(std::vector<int>), int length)
{
return TestSort(f(CreateRandomArray(length)));
}

// Testing a collection of sorts
void TestSortCollection(std::vector<std::vector<int>(*) (std::vector<int>) > sortTypes, int length)
{
for(auto& alg : sortTypes)
printf(TestSortGeneral(alg, length) ? "Results as expected\n" : "Problem with sort\n");
}

std::vector<int> InsertionSort(std::vector<int> vec)
{
for(int i = 1; i < vec.size(); ++i)
{
// Vector is sorted up to i - 1.
int j = i - 1;
int key = vec[i];

while(j >= 0 && key < vec[j])
{
vec[j + 1] = vec[j];
--j;
}

vec[j + 1] = key;

}

return vec;
}

std::vector<int> BubbleSort(std::vector<int> vec)
{
if(vec.empty())
return vec;

const int j = vec.size()-1;
bool sorted;
do
{
sorted = true;
for(int i = 0; i != j; ++i)
if(vec[i] > vec[i + 1])
{
Swap(vec[i], vec[i + 1]);
sorted = false;
}
}
while(!sorted);

return vec;
}

std::vector<int> SelectionSort(std::vector<int> vec)
{
for(int i = 0; i < vec.size(); ++i)
{
int minIndex = i;
for(int j = i+1; j < vec.size(); ++j)
if(vec[j] < vec[minIndex])
minIndex = j;

Swap(vec[i], vec[minIndex]);
}

return vec;
}

// Randomly selecting a number in [0 n)
int nrand(int n)
{
if(n <= RAND_MAX)
{
const int bucket_size = RAND_MAX / n;
int r;
do r = rand() / bucket_size;
while (r >= n);
return r;
}

const int buckets = n / RAND_MAX;
const int rem = n % RAND_MAX;
// n has been divided into several buckets of RAND_MAX and also a smaller bucket.
// We simulate the condition that the random trial landed in the smaller bucket.
// By recursion we can assume nrand is defined for all smaller n.
// nrand(buckets + 1) == buckets indicates falling off the end.
// Once we've fallen off the end, we hit the small bucket if nrand is small enough.

const int positionWithinBucket = nrand(RAND_MAX); // Bucket can be either normal bucket or smaller bucket.
const int finalBucket = nrand(buckets + 1);
const bool smallerBucket = finalBucket == buckets && positionWithinBucket < rem;

// If not a small bucket, the process is straightforward. Randomly select the large bucket and use the position within the bucket.
const int bucketIndex = smallerBucket ? buckets : nrand(buckets);
return bucketIndex * RAND_MAX + positionWithinBucket;

}

// Index for such that left-of-index members are smaller than right-of-index members
// Call by pointer to preserve sort.
// bool random indicates whether partitioning is random
int QuickSortPartition(std::vector<int>* vec, bool random = false)
{
if(vec->empty())
throw std::runtime_error("Should not be called on an empty vector");

const int j = vec->size() - 1;

if(random)
Swap((*vec)[j], (*vec)[nrand(j)]);

int& key = (*vec)[j];
int lowIndex = 0;

for(int i = 0; i < j; ++i)
if((*vec)[i] < key)
Swap((*vec)[lowIndex++], (*vec)[i]);

Swap(key, (*vec)[lowIndex]);
return lowIndex;

}

std::vector<int> QuickSort(std::vector<int> vec, bool random = false)
{
if(vec.size() <= 1)
return vec;

int index = QuickSortPartition(&vec, random);
std::vector<int> left;
std::vector<int> right;
std::vector<int> results;

for(int i = 0; i < index; ++i)
left.push_back(vec[i]);

for(int i = index + 1; i < vec.size(); ++i)
right.push_back(vec[i]);

left = QuickSort(left, random);
left.push_back(vec[index]);

right = QuickSort(right, random);
results = left;
for(auto i : right)
results.push_back(i);

return results;
}

// Use bind concept to distinguish the two types of Quicksort without repeating code.
/*****************************************************************************************************
Below is meant to declare the variant of QuickSort that uses bool random = false but I can't find the syntax.
************************************************************************************************************
*************************************************************************************************************
Below line gives compile error! */
std::vector<int>(*QuickSortBasic)(std::vector<int>) = std::bind(QuickSort, std::placeholders::_2, false);

// N is the length of each vector
void CombinedTest(int N)
{
std::vector<std::vector<int>(*) (std::vector<int>) > sortTypes;
sortTypes.push_back(InsertionSort);
sortTypes.push_back(BubbleSort);
sortTypes.push_back(SelectionSort);
sortTypes.push_back(QuickSortBasic);
TestSortCollection(sortTypes, N);
}

int main()
{
const int vecLength = 50 * 1000;
CombinedTest(vecLength);
return 0;
}

[Alf P. Steinbach]

On 30-Jun-15 7:18 PM, Paul wrote:
> I am trying to write two versions of Quicksort, one that uses randomised partition, and one that doesn't randomise the partition. However, I want them to have signatures std::vector<int> f(std::vector<int> vec) and so I want to bind the quicksorts to Boolean parameters.
>
> I can't find the syntax to do this though. Just so that I haven't left out any context, I will copy-paste my entire code. However, I will mark out the offending line with asterisks.
> Many thanks for your help.

Instead of std::bind I'd just use lambdas. They're good at binding and
work as expected. In contrast, std::bind only works as expected by chance.

Cheers & hth.,

- Alf

--
Using Thunderbird as Usenet client, Eternal September as NNTP server.

[JiiPee]

niin se Scottkin sanoi... etta "hyva jos et ole oppinut bindia" :)...
minahan en ole sita opetetllut, eli kaytan suoraan lambdoja

[guinne...@gmail.com]

On Tuesday, 30 June 2015 18:19:11 UTC+1, Paul wrote:
> I am trying to write two versions of Quicksort, one that uses randomised partition, and one that doesn't randomise the partition. However, I want them to have signatures std::vector<int> f(std::vector<int> vec) and so I want to bind the quicksorts to Boolean parameters.
>
> I can't find the syntax to do this though. Just so that I haven't left out any context, I will copy-paste my entire code. However, I will mark out the offending line with asterisks.
> Many thanks for your help.

<snip>

std::vector<int> QuickSort(std::vector<int> vec, bool random = false)
> {

<snip>

> }
>
> // Use bind concept to distinguish the two types of Quicksort without repeating code.
> /*****************************************************************************************************
> Below is meant to declare the variant of QuickSort that uses bool random = false but I can't find the syntax.
> ************************************************************************************************************
> *************************************************************************************************************
> Below line gives compile error! */
> std::vector<int>(*QuickSortBasic)(std::vector<int>) = std::bind(QuickSort, std::placeholders::_2, false);

<snip>

std::bind() returns an object encapsulating enough information
to call your QuickSort function with the correct set of parameters
when it is "called" (i.e. it passes the parameter passed in the
call and the parameter given to std::bind()).

As such, it is a functional object (a "functor") and definitely
not a function pointer. Furthermore, the Standard tells us that
the type of that object is unspecified, so you cannot write its
type out in your declaration of QuickSortBasic. So just use

auto QuickSortBasic = std::bind(QuickSort, std::placeholders::_2, false);

instead, which is so much neater anyway.

If you *really* want to avoid using 'auto' and spell out the type
of the binder object, you'll need to resort to using the deprecated
bind2nd() binder, thus:

std::binder2nd<
std::pointer_to_binary_function<
std::vector<int>, bool, std::vector<int> > >
QuickSortBasic = std::bind2nd(std::ptr_fun(QuickSort), false);

However, apart from the issue of these binders being deprecated,
I'm sure you'll agree that this is a particularly ugly solution.

Like the rest of us, be thankful for 'auto' and std::bind().

[Mr Flibble]

Nonsense, just store the result of std::bind in a std::function object.

[snip]

/Flibble

[guinne...@gmail.com]

Well, yes - there are conversions from the unspecified return type
from std::bind to an appropriate specialisation of std::function.

Whilst trying to get that specialisation right, I noticed that the
OP also passes the wrong placeholder into the std::bind() argument
list.

So, for the OP, you /could/ spell out a type to hold *a conversion
from* the result of std::bind():

std::function<std::vector<int>(std::vector<int>)> BasicQuickSort =
std::bind(QuickSort, std::placeholders::_1, false);

But I would still use 'auto'.

[Juha Nieminen]

Paul <peps...@gmail.com> wrote:
> // Testing our sorts by checking that every vector is sorted.
> // True if sorted.
> bool TestSort(const std::vector<int>& vec)
> {
> if(vec.empty())
> return true;
>
> for(int i = 0; i < vec.size() - 1; ++i)
> if(vec[i] > vec[i + 1] )
> return false;
>
> return true;
> }

That doesn't actually test it correctly. It's a typical beginner mistake.
Try to figure out why.


--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---

[Paul]

On Wednesday, July 1, 2015 at 9:10:36 AM UTC+1, Juha Nieminen wrote:
> Paul <peps...@gmail.com> wrote:
> > // Testing our sorts by checking that every vector is sorted.
> > // True if sorted.
> > bool TestSort(const std::vector<int>& vec)
> > {
> > if(vec.empty())
> > return true;
> >
> > for(int i = 0; i < vec.size() - 1; ++i)
> > if(vec[i] > vec[i + 1] )
> > return false;
> >
> > return true;
> > }
>
> That doesn't actually test it correctly. It's a typical beginner mistake.
> Try to figure out why.
>

In practice, the test worked. I made faulty attempts at quicksort etc. And the unsorted nature of the result was picked up, until I fixed the code. My guess is that you're referring to the signed/unsigned comparison. However, this isn't technically perfect but it isn't really a problem either. Note that the unsigned value can never be negative because we cover the case vec.empty() above.

A more thorough test would also check that the vector has the size that it's supposed to have. Is that what you mean? In that case, the test would not be "incorrect", just arguably incomplete.

I would also add that I did check the code against both large (1 million entries) and very small (0, 1 or 2 entries) and I didn't see any problems. If you erase if(vec.empty()) return true; then the code crashes for an empty vector. But so what? (In other words, so what if you can make the code crash by changing it? Anything can be ruined by changing it.)

I'm a bit puzzled by your comment.

Please could others give feedback about whether they agree that the test is flawed? If it is flawed in an interesting way, then I agree that it would be a good learning experience to fix it.

Thank You,

Paul

[Ralf Goertz]

Am Wed, 1 Jul 2015 01:58:01 -0700 (PDT)
schrieb Paul <peps...@gmail.com>:

> On Wednesday, July 1, 2015 at 9:10:36 AM UTC+1, Juha Nieminen wrote:
> > Paul <peps...@gmail.com> wrote:
> > > // Testing our sorts by checking that every vector is sorted.
> > > // True if sorted.
> > > bool TestSort(const std::vector<int>& vec)
> > > {
> > > if(vec.empty())
> > > return true;
> > >
> > > for(int i = 0; i < vec.size() - 1; ++i)
> > > if(vec[i] > vec[i + 1] )
> > > return false;
> > >
> > > return true;
> > > }
> >
> > That doesn't actually test it correctly. It's a typical beginner
> > mistake. Try to figure out why.
> >
>

> I'm a bit puzzled by your comment.
>
> Please could others give feedback about whether they agree that the
> test is flawed? If it is flawed in an interesting way, then I agree
> that it would be a good learning experience to fix it.

What about equal elements in vec?

[Ralf Goertz]

Am Wed, 1 Jul 2015 12:15:25 +0200
schrieb Ralf Goertz <m...@myprovider.invalid>:

Sorry, I misread the code for something like

bool ret=true
for (…)
ret&=(vec[i] < vec[i + 1] )
return ret;

So I also don't see the problem.

[Alf P. Steinbach]

On 01-Jul-15 10:58 AM, Paul wrote:
> On Wednesday, July 1, 2015 at 9:10:36 AM UTC+1, Juha Nieminen wrote:
>> Paul <peps...@gmail.com> wrote:
>>> // Testing our sorts by checking that every vector is sorted.
>>> // True if sorted.
>>> bool TestSort(const std::vector<int>& vec)
>>> {
>>> if(vec.empty())
>>> return true;
>>>
>>> for(int i = 0; i < vec.size() - 1; ++i)
>>> if(vec[i] > vec[i + 1] )
>>> return false;
>>>
>>> return true;
>>> }
>>
>

> Please could others give feedback about whether they agree that the test is
> flawed? If it is flawed in an interesting way, then I agree that it would
> be a good learning experience to fix it.

I see no problem with other than that it may produce spurious warnings
about signed/unsigned comparison (which however is safe).

Cheers & hth.,

- Alf

[Paul]

On Wednesday, July 1, 2015 at 11:45:18 AM UTC+1, Alf P. Steinbach wrote:
> On 01-Jul-15 10:58 AM, Paul wrote:
> > On Wednesday, July 1, 2015 at 9:10:36 AM UTC+1, Juha Nieminen wrote:
> >> Paul <peps...@gmail.com> wrote:
> >>> // Testing our sorts by checking that every vector is sorted.
> >>> // True if sorted.
> >>> bool TestSort(const std::vector<int>& vec)
> >>> {
> >>> if(vec.empty())
> >>> return true;
> >>>
> >>> for(int i = 0; i < vec.size() - 1; ++i)
> >>> if(vec[i] > vec[i + 1] )
> >>> return false;
> >>>
> >>> return true;
> >>> }
> >>
> >
> > Please could others give feedback about whether they agree that the test is
> > flawed? If it is flawed in an interesting way, then I agree that it would
> > be a good learning experience to fix it.
>
> I see no problem with other than that it may produce spurious warnings
> about signed/unsigned comparison (which however is safe).
>

Great that others agree with me. Yes, the code does produce spurious warnings on my compiler with its current setting. Ignoring the possibility of an unsigned value becoming negative (and therefore overflowing) is indeed a common "beginner's error" so this seems a good guess about what Juha meant. However, Juha seems to have overlooked the if(vec.empty()) code which protects against that error.

Paul

[Paul]

On Wednesday, July 1, 2015 at 1:00:46 PM UTC+1, Stefan Ram wrote:
> Juha Nieminen <nos...@thanks.invalid> writes:

> >Paul <peps...@gmail.com> wrote:
> >>for(int i = 0; i < vec.size() - 1; ++i)

> >That doesn't actually test it correctly. It's a typical beginner mistake.
> >Try to figure out why.
>

> He uses »int i«, but »vec.max_size()« could
> be larger than numeric_limits< int >::max().

Yes, but this is too small a quibble for the assertion that the code "doesn't test it correctly." The code works for vector sizes that are less than both vec.max_size() and maxint and that should be good enough. I doubt whether Juha meant this.

Paul

Paul

[Juha Nieminen]

Paul <peps...@gmail.com> wrote:
> I'm a bit puzzled by your comment.

The problem with the function is that it tests that the parameter is
sorted, but it doesn't verify that your sorting algorithm actually
works correctly. To understand why, consider that this "sorting
function" passes with flying colors your test:

std::vector<int> FalseSort1(std::vector<int> v)
{
return std::vector<int>();
}

Likewise this does as well:

std::vector<int> FalseSort2(std::vector<int> v)
{
return std::vector<int>(v.size(), 0);
}

This is not just nitpicking. You can't test the validity of a custom
sorting function by simply checking that the result is sorted. You also
have to test that the result actually has all the same values as the
input had. Else you won't be catching bugs where elements are accidentally
dropped off, duplicated or corrupted in some other way.

(It's an interesting question *how* you would test that. Of course the
simplest way of doing it is to sort the original with std::sort(),
which is known to be reliable, and then compare the two vectors.
If there were no reliable readymade sorting function available, then
the checking becomes more interesting.)

[Öö Tiib]

On Wednesday, 1 July 2015 11:58:14 UTC+3, Paul wrote:
> On Wednesday, July 1, 2015 at 9:10:36 AM UTC+1, Juha Nieminen wrote:
> > Paul <peps...@gmail.com> wrote:
> > > // Testing our sorts by checking that every vector is sorted.
> > > // True if sorted.
> > > bool TestSort(const std::vector<int>& vec)
> > > {
> > > if(vec.empty())
> > > return true;
> > >
> > > for(int i = 0; i < vec.size() - 1; ++i)
> > > if(vec[i] > vec[i + 1] )
> > > return false;
> > >
> > > return true;
> > > }
> >
> > That doesn't actually test it correctly. It's a typical beginner mistake.
> > Try to figure out why.
> >
>
>

> Please could others give feedback about whether they agree that the test is flawed? If it is flawed in an interesting way, then I agree that it would be a good learning experience to fix it.

I would suggest to remove such self-made cycle and to learn to use the
<algorithm> from standard library. Reinventing own versions of standard
algorithms isn't defect itself but the self-made cycles are longer to read
so waste time of potential reader, are often less efficient than the ones
written by standard library implementer and also contain defects more
often than standard library does.

Therefore good companies value specialists who can avoid reinventing
standard algorithms.

To find out if your custom sorting algorithm did a good job or not I
would suggest to check that sorting result's length is same with
original AND then if it is sorted original. Two examples ...
A) check that sorting result 'std::is_sorted' and that it
'std::is_permutation' of original ... OR
B) check that 'std::sort'ing of original causes sequence that is
'std::equal' with result of custom sorting.

If it matters then B) is likely faster since 'std::is_permutation' has up
to quadratic complexity.

[Mr Flibble]

On 01/07/2015 11:45, Alf P. Steinbach wrote:
> On 01-Jul-15 10:58 AM, Paul wrote:
>> On Wednesday, July 1, 2015 at 9:10:36 AM UTC+1, Juha Nieminen wrote:
>>> Paul <peps...@gmail.com> wrote:
>>>> // Testing our sorts by checking that every vector is sorted.
>>>> // True if sorted.
>>>> bool TestSort(const std::vector<int>& vec)
>>>> {
>>>> if(vec.empty())
>>>> return true;
>>>>
>>>> for(int i = 0; i < vec.size() - 1; ++i)
>>>> if(vec[i] > vec[i + 1] )
>>>> return false;
>>>>
>>>> return true;
>>>> }
>>>
>>
>> Please could others give feedback about whether they agree that the
>> test is
>> flawed? If it is flawed in an interesting way, then I agree that it
>> would
>> be a good learning experience to fix it.
>
> I see no problem with other than that it may produce spurious warnings
> about signed/unsigned comparison (which however is safe).

The problem is you are using the wrong type for the job: the correct
type to use here is either 'std::size_t' or
'std::vector<int>::size_type' and not 'int'. Lazy fuckers who infect
all of their code with 'int' need to be using Java and not C++.

/Flibble

[Paul]

Thanks a lot. I heeded this advice and wrote the below which appears to work. However, now I have another concern. Why is the below not an error? Why is it ok to write is_sorted instead of std::is_sorted ? I didn't put a using namespace declaration anywhere. I don't like it that the below compiles because it means that if I write my own algorithms, I introduce ambiguities if the name clashes with a name from <algorithm>

Thanks,

Paul

bool TestSort(const std::vector<int>& vec , int N)
{
return vec.size() == N && is_sorted(vec.begin(), vec.end());
}

[Alf P. Steinbach]

On 04-Jul-15 12:47 PM, Paul wrote:
> Why is the below not an error? Why is it ok to write is_sorted instead of std::is_sorted ?
> I didn't put a using namespace declaration anywhere. I don't like it that the below compiles
> because it means that if I write my own algorithms, I introduce ambiguities if the name
> clashes with a name from <algorithm>
>
> Thanks,
>
> Paul
>
> bool TestSort(const std::vector<int>& vec , int N)
> {
> return vec.size() == N && is_sorted(vec.begin(), vec.end());
> }
>

When this compiles it is because the `std::vector` implementation uses a
custom iterator type for its iterators, instead of raw pointers. And
then you get Argument Dependent Lookup (ADL), also known as Koenig
lookup (after Andrew Koenig, the secretary for C++98). With ADL the
compiler searches for the function in the namespaces where the argument
types are defined. It was mostly intended for operators, which can't be
qualified. But it works also with ordinary named functions.

I'm not quite sure if the current standard permits standard collection
iterators to be raw pointers. But if it does, then the above code is not
guaranteed to compile. However, the last time I encountered a standard
library iterator type that was a raw pointer, was in the 1990s.

One practical way to avoid warnings about signed/unsigned mismatch, as
in the comparison to .size() above, is to define and use

using Size = ptrdiff_t;

template< class Type >
auto n_items( Type const& o )
-> Size
{
using std::begin; using std::end;
return end( o ) - begin( o );
}

The trick here with `using` is a common one to allow ADL lookup, here
for `begin` and `end`. Writing `std::begin`, for example, would force
use of the standard library's `begin`, which might not be able to handle
the type. But with the `using` there is ADL lookup, and if the type
doesn't have an associated `begin` then `std::begin` is used.

[Juha Nieminen]

Paul <peps...@gmail.com> wrote:
> bool TestSort(const std::vector<int>& vec , int N)
> {
> return vec.size() == N && is_sorted(vec.begin(), vec.end());
> }

That still doesn't test it properly. See my other post about why.

[Alf P. Steinbach]

One way to practically ensure the same numbers, without using a known
good sort implementation, could be to use a simple order-independent
checksum such as XOR (should not change from raw data to sorted), plus a
few confidence boosters of known data and results.