std::vector initialization problem

[GeoRanger]

Hello:

I have some code which needs to allocate a pointer to a list of arrays. The code which uses that pointer can throw exceptions. To prevent leaking the array, I would like to wrap the pointer with std::vector.

#include <vector>
void main(void)
{
  int static const nUnits = 2;
 
  // I want to use vector for it's RAII abilities.
  std::vector<int[nUnits]> aUnits;
  aUnits.resize(300);
 
  int (* const pUnits)[nUnits] = &aUnits[0];
 
  // Of course the below works fine, but then I have to wrap all the code
  // which follows with an exception handler to prevent a memory leak.
  // int (* const pUnits)[nUnits] = new int[300][nUnits];
 
  // In the real program, the code which appears here and which uses
  // pUnits has lots of places which might throw exceptions.
}

The problem is, I keep getting

Error 1 error C2440: '<function-style-cast>' : cannot convert from 'int' to 'int [2]' c:\program files (x86)\microsoft visual studio 10.0\vc\include\memory 631

in STL code. That comes from a routine with the title

// TEMPLATE FUNCTION _Uninitialized_default_fill_n WITH ALLOCATOR

. I think the problem is that vector is trying to initialize the array with default values. In the real code, I don't need it initialized at all because I memcpy something else into it.

I looked around on the web to see if I could solve the problem by doing something with the second template argument to vector and found reference to a malloc_alloc object, but VS2010 doesn't seem to have that.

Nor do I see a way to allocate the array manually and then force vector to take ownership of it.

I'm about to give up and simply just wrap my routine with an exception handler so I can delete [] the array. Does anybody know how I can get vector or some other STL container to own the array?

[Paul McKenzie]

Hello:

I have some code which needs to allocate a pointer to a list of arrays. The code which uses that pointer can throw exceptions. To prevent leaking the array, I would like to wrap the pointer with std::vector.

You can't do that. The std::vector is not designed to point to your own array after it's been initialized.

. I think the problem is that vector is trying to initialize the array with default values.

That is what vector does, and that is to default initialize any T objects created within it.

I'm about to give up and simply just wrap my routine with an exception handler so I can delete [] the array.

So why not just create your own RAII class?

class MyPointerClass
{
     public:
       MyPointerClass() { /* stuff */ }
       ~MyPointerClass() { /* stuff to do when this object goes out of scope */ }
};

There is nothing complicated at all. Or you can use what boost has:

http://www.boost.org/doc/libs/1_48_0...tml/index.html

Regards,

Paul McKenzie

[Lindley]

I don't think a vector is allowed to have an array as its type, since a vector's type must be copyable.

[GeoRanger]

Thanks for the responses. :-)

Apparently vector is safely converted to a raw array, as long as the type is not bool. According to these pages new versions the ISO standard require it:

http://stackoverflow.com/questions/8...-be-contiguous

http://stackoverflow.com/questions/2...ays-contiguous

Asside from that, it looks like I'll have to do as you're suggesting anway. I was initially trying to use vector just to get in the habit of using the STL, but when I wrote the initial post I had forgotten that some of the code which follows uses the vector's iterators for a call to the STL sort function.

I tried using a workaround structure as the template argument to vector (where the structure is the same size as the argument I really want) but that wrought insurmountable havoc in the sort function. (Surpisingly, the body of the lambda passed to sort is unaware of the template types in the outer function, so I was unable to reinterpret_cast the lambda arguments from the workaround structure to the "template-type (*)[nUnits]" I need.)

The bottom line, unfortunately, is that I need to both do as your suggesting and rewrite my sort function to use the old C-style qsort (bye-bye type safety).

Thanks for the help!

[Lindley]

some of the code which follows uses the vector's iterators for a call to the STL sort function.

The sort algorithm can be run on a simple array if desired. All it requires are random-access iterators, which includes pointers by definition. This includes an "array view" of the memory inside a vector.

I tried using a workaround structure as the template argument to vector (where the structure is the same size as the argument I really want) but that wrought insurmountable havoc in the sort function. (Surpisingly, the body of the lambda passed to sort is unaware of the template types in the outer function, so I was unable to reinterpret_cast the lambda arguments from the workaround structure to the "template-type (*)[nUnits]" I need.)

You should be able to get template type information into a lambda. Regardless of how that can be done, though, it's definitely possible to get it into std::sort if you define the functor manually instead of using a lambda---just make the type a template argument of the functor.

The bottom line, unfortunately, is that I need to both do as your suggesting and rewrite my sort function to use the old C-style qsort (bye-bye type safety).

Thanks for the help!

Technically you've already lost type safety if you're using reinterpret_cast.

[Paul McKenzie]

The bottom line, unfortunately, is that I need to both do as your suggesting and rewrite my sort function to use the old C-style qsort (bye-bye type safety).

#include <algorithm>

int main()
{
   int SomeArray[] = {1, 9, 3, 78, -9, 0};
   std::sort(SomeArray, SomeArray + 6);
}

This sorts an int array in ascending order. You do not need vector to sort.

Regards,

Paul McKenzie

[GeoRanger]

Thanks you two! I really would like to use std::sort, but I can't get it to compile. This sample I think recreates what I'm running into:

#include <vector>
#include <algorithm>
 
template <int N, class T> struct A {};
 
template <class T> struct A<1, T>
{
 int static const nUnits = 2;
 
 typedef typename std::vector<int>::size_type size_type;
 
 size_type MyRoutine(int const nFields, size_type const (* const pFields)[nUnits]);
};
 
template <class T>
typename A<1, T>::size_type A<1, T>::MyRoutine(int const nFields, size_type const (* const pFields)[nUnits])
{
 size_type (* const pLocalFields)[nUnits] = new size_type [nFields][nUnits];
 
 memcpy(pLocalFields, pFields, sizeof(pFields[0]) * nFields);
 
 std::sort(pLocalFields, pLocalFields + nFields,
           [](size_type const (& r1)[nUnits], size_type const (& r2)[nUnits])->bool
 {
     size_type const (* pTestCompile1)[nUnits] = NULL;
     return true;
 });
 delete [] pLocalFields;
 return 0;
}
 
void main(void)
{
 A<1, int> a;
 a.MyRoutine(0, NULL);
}

That gives me

Error 1 error C2065: 'nUnits' : undeclared identifier c:\users\GeoRanger\documents\myprojects\test\test.cpp 243

This seems really odd since it did know what nUnits was in the lambda declaration. In my real code, I think I was seeing the same behavior with size_type, though I haven't been able to recreate that in my test example.

If I comment out the declaration of pTestCompile1 in the lambda body, instead I get

Error 1 error C2075: '_Val' : array initialization needs curly braces c:\program files (x86)\microsoft visual studio 10.0\vc\include\algorithm 2663

which seems to be once again some kind of inability to default-initialize a size_type (*)[nUnits].

I've got a version with a homemade RAII container and qsort compiling, but I'm sure I'm off by at least one level of indirection in the body of the comparator in qsort. (To be debugged later when I finish the code which calls this beast.)

Am I missing an easy way to fix std::sort? I'd much rather use it.

[Paul McKenzie]

Thanks you two! I really would like to use std::sort, but I can't get it to compile. This sample I think recreates what I'm running into:

Instead of posting the sample, on a high-level, describe what you're sorting.

For example:

size_type (* const pLocalFields)[nUnits] = new size_type [nFields][nUnits];

What is your goal here? Is it to create a 2-d array?

Now for the sort -- what is the criteria for your sort? Is it to take each row from this 2-d array and do what exactly? There is no need to post code, just describe.

Regards,

Paul McKenzie

[GeoRanger]

Instead of posting the sample, on a high-level, describe what you're sorting.

The array I'm sorting contains indices into a table of statistical data. The indices describe regions within the table which should be ignored by the analysis performed by "MyRoutine". They have to be sorted to improve the run-time of the analysis.

The alternative approach in which the caller zeroes out parts of the table to be ignored (rather than passing in indices to those parts) won't work because the analysis is looking for clusters that can overlap. If the caller zeroed out a cluster, it would negatively impact the statistical summary of any overlapping clusters.

What is your goal here? Is it to create a 2-d array?

That's right. I wan't to duplicate the fields described by the caller so I can sort them without stomping the caller's version of the fields. The 2-D array can be thought of as yet another table in which each row contains the indices which describe a single exclusion in the statistical table. Then the array has a row for however many exclusions exist.

Now for the sort -- what is the criteria for your sort? Is it to take each row from this 2-d array and do what exactly? There is no need to post code, just describe.

The rows have to be ordered so the walking analysis will encounter the exclusion closest to the start of the table first, then second, and so forth. Any rows which have the same start position have to be secondarily sorted by their ending position.

I'm sure I can get it working with qsort; it's just that it's ugly and unsatisfying that way. Plus if it were type-safe the compiler would practically debug the pointer indirection for me. Even more so, I'm curious about the bigger picture (the generality). It seems like the STL code in principal should be able to work with arrays like this. I should mention that in the previous code post I don't actually need the pTestCompile1 declaration if the lambda function can be made to compile. I only put that there for the purpose of asking why the lambda body doesn't seem to know about nUnits. I ran into that problem when I was trying to reinterpret_cast the workaround structure/hack I briefly tried.

Thanks,

[Lindley]

The syntax new T[X][Y] might work, but I've never seen it used. There are two basic types of 2D arrays: those in which the first dimension is an array of pointers to rows, and those in which the rows are contiguous in memory. The syntax for accessing both types is the same but the handling during sorts, etc must be different.

If you are attempting to move 'rows' around as a single unit, the first-dimension-is-pointers approach is probably going to be more efficient. If you're concerned with the memory overhead of allocating each row separately, it's possible to allocate two arrays, one with contiguous rows and the second with pointers into the first array.

The rows have to be ordered so the walking analysis will encounter the exclusion closest to the start of the table first, then second, and so forth. Any rows which have the same start position have to be secondarily sorted by their ending position.

This is, of course, a trivial functor to write. Why don't you start there?

[Philip Nicoletti]

I am still having problems at what you mean by "indices". If I understand what you
want, you would need at least 3 fields for each exclusion : the row , the start column,
and the end column.

Could you give a small concrete example of what you want ?

[Paul McKenzie]

That's right. I wan't to duplicate the fields described by the caller so I can sort them without stomping the caller's version of the fields.

Well, that way to allocate a 2D array, even though it looks simple, seems to be a pain-in-the-neck to deal with. Needless to say, I've never used that form of new[] in any programs that I've written to allocate a 2d array. Either it's a vector<vector<T>> or it's a T** with dynamically allocated data.

If you want to use T**, then the way to do this is to start off with a T** and dynamically allocate each row, then allocate space for the data. Then you point the rows within the table. For example, this works:

#include <algorithm>
#include <cstdlib>

unsigned Randomize()
{
    return rand()&#37;1000;
}

template <typename T>
T** Create2DArray(unsigned rows, unsigned cols)
{
    T** ptrptrT;
    T* ptrT;

    // allocate row pointers to point to memory pool
    ptrptrT = new T*[rows];

    // Here is the memory pool
    ptrT = new T[rows*cols];

    // fill with random numbers (remove the line below for generic usage -- it's only there for demo purposes)
    std::generate(ptrT, ptrT + rows*cols, Randomize);  

    // Now point the rows to the data within the memory pool
    for (unsigned i = 0; i < rows; ++i, ptrT += cols )
        ptrptrT[i] = ptrT;
    return ptrptrT;
}

template <typename T>
void Destroy2DArray(T** ptr)
{
    delete [] ptr[0];  // delete pool
    delete [] ptr;      // delete row pointers
}

struct SortRows
{
    unsigned int m_cols;
    SortRows( unsigned cols ) : m_cols( cols ) { }
    void operator()(int *pSortedRow) const
    {
        std::sort(pSortedRow, pSortedRow + m_cols);
    }
};

int main()
{
    int ** My2DInt = Create2DArray<int>(10, 100);
    // sort each row
    std::for_each(My2DInt, My2DInt + 10, SortRows(100));
    Destroy2DArray<int>(My2DInt);   
}

This creates a 2d table and calls sort() for each row. I don't know if this was your goal, but this works properly.

Regards,

Paul McKenzie

[superbonzo]

That gives me Error 1 error C2065: 'nUnits' : undeclared identifier c:\users\GeoRanger\documents\myprojects\test\test.cpp 243
This seems really odd since it did know what nUnits was in the lambda declaration.

I don't have the standard at my disposal right now, but I'm quite sure that the lambda cannot see *this static members, unless "this" is included in the lambda capture clause ( or if those members are captured explicitly, of course ).

as far as the other error is concerned, I don't think you can sort multidimensional arrays in that way, because pointers to arrays are not mutable iterators ( in other words, a "size_type (* const)[nUnits]" does not point to anything in memory, it just produces an rvalue pointer when dereferenced, using usual array arithmetic ).
Therefore, you should sort a real array of pointers instead ... EDIT: as shown in Paul's post

[GeoRanger]

From Lindley:

If you are attempting to move 'rows' around as a single unit, the first-dimension-is-pointers approach is probably going to be more efficient.

From Paul McKenzie:

Then you point the rows within the table.

I hadn't thought of simply just sorting an array of pointers to each row, rather than the rows themselves. For the size of the table of exclusions, I don't think shuffling rows around will be too big of a performance hit in the context where it will be used, but the pointers-approach seems superior regardless.

Before I saw the latest advice from you all, I revisited the workaround structure idea and was able to get it working with something like the following, which I post here for interest's sake and to demonstrate the inconsistent compiler access to *this members within the lambda:

#include <vector>
#include <algorithm>
 
template <int N, class T> struct A {};
 
template <class T> struct A<1, T>
{
    int static const iFirst  = 0;
    int static const iSecond = 1;
    int static const nUnits  = 2;
 
    typedef typename std::vector<int>::size_type size_type;
 
    size_type MyRoutine(int const nFields, size_type const (* const pFields)[nUnits]);
};
 
template <class T>
typename A<1, T>::size_type A<1, T>::MyRoutine(int const nFields, size_type const (* const pFields)[nUnits])
{
    struct LWorkaround
    {
        LWorkaround(void) {}

        // I've included { copy, move } X { constructors, assignment operators }
        // in case the size_type template argument is ever something non-trivial.

        size_type const & operator [] (size_t i) const { return m_i[i]; }

        size_type m_i[nUnits];

    };

    static_assert(sizeof(LWorkaround) == sizeof(size_type const [nUnits]),
                  "Structure size is incompatible with field exclusion row.");
    static_assert(sizeof(LWorkaround[100]) == sizeof(size_type const [100][nUnits]),
                  "Structure packing is incompatible with array packing.");

    // Now I get to use vector again for the RAII effect (rather than writing a manual RAII class).
    std::vector<LWorkaround> aFields;
    aFields.resize(nFields);

    // This is safe because the ISO standard requires vector to be compatible with
    // a raw array.
    LWorkaround * const pLocalFields = &aFields[0];
 
    memcpy(pLocalFields, pFields, sizeof(pFields[0]) * nFields);

    std::sort(pLocalFields, pLocalFields + nFields,
              [](LWorkaround const & r1, LWorkaround const & r2)->bool
    {
        // Odd, if uncommented, the following declaration compiles just fine...
        // size_type test[nUnits];
        // ... but in contrast, if uncommented, the following declaration does not.
        // size_type const (* const pFields)[nUnits] = NULL;

        // Also the uses of the static members of A work here...
        bool const b = r1[iFirst] == r2[iSecond];
        return true;
    });

    return 0;
}
 
void main(void)
{
    A<1, int> a;
    a.MyRoutine(0, NULL);
}

From superbonzo:

...I'm quite sure that the lambda cannot see *this static members, unless "this" is included in the lambda capture clause ( or if those members are captured explicitly, of course ).

I guess the issue is obsolete, but I'm getting the inconsistent compiler behavior described by the comments in the lambda body. It's as if the compiler is aware of them in some instances but not others. Perhaps by the C++ standard it wouldn't have access to them at all (as superbonzo states) but the compiler implementation sometimes does have that access in a non-standard way? (That is, perhaps the code wouldn't be portable?)

Anyway, if I hybridize my preferred way of allocating the array with the great suggestion you all have made to sort an array of pointers, I end up with:

template <class T>
typename A<1, T>::size_type A<1, T>::MyRoutine(int const nFields, size_type const (* const pFields)[nUnits])
{
    int i;

    std::vector<size_type const (*)[nUnits]> aFields;
    aFields.resize(nFields);

    size_type const (** const pLocalFields)[nUnits] = &aFields[0];

    for (i = 0; i < nFields; ++i)
    {
        pLocalFields[i] = &pFields[i];
    }

    std::sort(pLocalFields, pLocalFields + nFields,
              [](size_type const (* & r1)[nUnits], size_type const (* & r2)[nUnits])->bool
    {
        bool const b = (*r1)[iFirst] == (*r2)[iSecond];
        return true;
    });

    return 0;
}

Unfortunately, that causes the STL to have an ambiguous template specialization in the vector declaration and in the sort function. I might dig into it a little more tomorrow, but I'm about ready to settle for the workaround structure, perhaps even exposing it to the caller so the caller would pass in an array of these structures. I'm relunctant to do that because the contents of the structure are just indices with no intrinsic meaning apart from this function, and I don't want to pollute the caller's scope with excess baggage.

Regarding the atypical new [] and pointer syntax, new T[X][Y1][Y2][...][Yn] works as long as Y1 to Yn are all known at compile time. So for a horrific example, this

    int nElements = 100;
    int volatile (* const pThing)[4][8][2][24][43][72] = new int [nElements][4][8][2][24][43][72];

is a perfectly legitimate pointer, compiling just fine and useable in code as expected because the compiler knows both how much memory needs to be allocated for each "element" and how to compute the address of each volatile int by the (constant) size of the array dimensions. Also, it helps to remember that pointer declarations are most easily understood if you read them backwards and group by parenthesis, so in this case it would be read "pThing is a const pointer to an array of 4 by 8 by 2 by 24 by 43 by 72 volatile ints".

Thanks all!