Sort Array of Indexes Into Primary Array

Question

I'm coding a C++ dll to sort a SAFEARRAY passed from VBA.

I'm not using any OLE libraries, but rather accessing the array descriptor and data directly.

I have no problem sorting an array of any native VBA types. For example, the following fragment sorts an array of BSTRs:

long * p = (long*)pData; 

std::sort(p, p + elems, comparestring);

...which uses this comparison function:

bool comparestring(const long& lhs, const long& rhs) {

   wchar_t * lhs_ = (wchar_t*)lhs;
   wchar_t * rhs_ = (wchar_t*)rhs;

   return _wcsicmp(lhs_, rhs_) < 0;
}

I realize I'm cheating here since wchar_t is very different from BSTR, but it's not common to have a zero char within the payload of an Excel string and so I'm OK with that. The above works well.

THE PROBLEM

I want the dll to optionally be able to sort a companion array of indexes into the primary data array. In this mode only the index array would be sorted, leaving the source data untouched.

My research suggests that a lamda functor may be the most promising path as I'd prefer not to allocate memory for additional arrays or vectors of data or pairs.

In particular, this answer seems very promising.

However, I cannot work out how to adapt it to my situation where I'm processing the raw pointers to the BSTRs that begin at pData.

I have tried the following:

long * p = (long*)pData; 

long ndx[5];

for (int i = 0; i < 5; i++) ndx[i] = i + 1;

std::sort(ndx[0], ndx[4], [&p](long i1, long i2) { comparestring((*p) + i1, (*p) + i2); })

I am using VC++ 2015 and the above results in the following error:

Error C2893 Failed to specialize function template 'iterator_traits<_Iter>::iterator_category std::_Iter_cat(const _Iter &)'

My C programming days are ancient history (predating the existence of C++) and so I'm struggling a little. Appreciate any assistance.

UPDATE

The code now looks like this.. and it compiles, but the order of ndx is incorrect after execution:

long * p = (long*)pData; 

long ndx[5];

for (int i = 0; i < 5; i++) ndx[i] = i + 1;

std::sort(ndx, ndx + 5, [&p](long i1, long i2) { return comparestring(*p + i1, *p + i2); })

The lambda needs to return a boolean value (e.g. `return comparestring.....` — M.M, Dec 02 '15 at 22:25
also you probably meant `ndx, ndx + 5` instead of `ndx[0], ndx[4]`. That should make it compile but it seems to me that your pointer cast hackery is still producing junk — M.M, Dec 02 '15 at 22:26
Thanks. I tried using place the three statements from inside `comparestring` directly into the lambda, and even though it would then return a boolean, I got the exact same error. — Excel Hero, Dec 02 '15 at 22:28
Does your compiler come with a C++ wrapper for SAFEARRAY? That would save a lot of reinventing the wheel. — M.M, Dec 02 '15 at 22:31
Yes, but this is for educational purposes. Using a wrapper obscures a lot of what is going on. The project has worked out very well so far. As mentioned, I can sort arrays of all the native types including VBA's Variant. I am surprised that extending this to sorting an array of indexes into the the SAFEARRAY is difficult. — Excel Hero, Dec 02 '15 at 22:35
Maybe drawing a memory map would help you. `(*p) + i1, (*p) + i2` is obviously wrong, as `i1` and `i2` are taking values from 1 through 5, but your `comparestring` function is expecting to get pointers to different strings to compare (when in fact it will get pointers to adjacent bytes) — M.M, Dec 02 '15 at 22:37
By the way, `ndx, ndx + 5` does not compile either... but the errors are different. It now reports: `conditional expression of type 'void' is illegal` — Excel Hero, Dec 02 '15 at 22:38
Yes, and it does compile now. But, the returned sorted order of the indexes is wrong. — Excel Hero, Dec 02 '15 at 23:02
@M.M Can you suggest a link for me to read up on what you are talking about. it's literally been decades for me... or if you could post a code example? — Excel Hero, Dec 02 '15 at 23:14
Not really, I don't know of any documentation of safearray apart from what's on the MSDN website. — M.M, Dec 02 '15 at 23:17
Just re-read you comment, but it seems to me that the pointer arithmetic should work. Yes the number coming from `i1` and `i2` will be the values 1 to 5, but the pData is sequential long pointers to the strings... — Excel Hero, Dec 02 '15 at 23:18
Have you considered using the Windows API functions for accessing the array members, instead of adding integers? — M.M, Dec 02 '15 at 23:18
Your first test will be `comparestring(1000, 1001)` or similar, those clearly cannot point to different strings — M.M, Dec 02 '15 at 23:18
Sorry for the confusion. I am good with my understanding of the the documentation of SAFEARRAY. I know it very well. C++ is my weakness. I did not get the memory map suggestion. — Excel Hero, Dec 02 '15 at 23:20
Since `*p` is a `long`, and if `p = 1000`, shouldn't `p + 1 = 1004` ? — Excel Hero, Dec 02 '15 at 23:23
Yes, but you're doing `*p`, not `p`. You're adding two integers. — M.M, Dec 02 '15 at 23:26
@M.M I fixed it with your help... so thanks. I needed ndx to be populated starting with zero instead of one (doh!) and then this did the trick in the lambda: `return comparestring(*(p + i1), *(p + i2));` Please write an answer and I'll accept it. — Excel Hero, Dec 02 '15 at 23:48

M.M · Accepted Answer · 2015-12-02T23:58:28.417

This code:

long ndx[5];
for (int i = 0; i < 5; i++) ndx[i] = i + 1;
std::sort(ndx[0], ndx[4], [&p](long i1, long i2) { comparestring((*p) + i1, (*p) + i2); })

should probably be:

long ndx[5];
for (int i = 0; i < 5; i++) ndx[i] = i;
std::sort(ndx, ndx + 5, [&](long i1, long i2) { return comparestring(*(p + i1), *(p + i2)); }

The first two arguments to std::sort are an iterator range. It'd be better style (assuming your compiler is C++11-compatible) to use std::begin(ndx) and std::end(ndx).

Also, the second line can be written std::iota( std::begin(ndx), std::end(ndx), 0 );

Sort Array of Indexes Into Primary Array

1 Answers1