Thread: How to declare high order vectors vector<vector<vector<.....<vector<double>>>>>...>

  1. #1
    Registered User FortranLevelC++'s Avatar
    Join Date
    May 2013
    Location
    United States
    Posts
    81

    How to declare high order vectors vector<vector<vector<.....<vector<double>>>>>...>

    Hello,

    I suspect that C++11 would make it possible to declare high rank vectors such as
    Code:
    int N = 15; // chosen arbitrary rank 
    vector<vector<vector<...<vector<double>>>>..> vec; // N layers of nested vectors
    Is there a way to declare such a vector of rank N (given a fixed integer rank N)?

    Heuristically I would like to write the declaration like this:
    Code:
    vector<double> A;
    vector<A> vec[0];
    for(int i=1; i<N; i++)
    {
       vector<vec[i-1]> vec[i];
    }
    Is there a way to use the new variadic templates to make this work?




    Many thanks.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > int N = 15; // chosen arbitrary rank
    > vector<vector<vector<...<vector<double>>>>..> vec; // N layers of nested vectors
    And how many elements do you plan to store in each dimension?

    With just the equivalent of
    double vec[4][4][4][4][4][4][4][4][4][4][4][4][4][4][4];
    you're looking at 8GB just to store the data, and who knows how overhead of storing all the vector information.

    Replace 4 with 5, and it jumps to 256GB!

    Declaring it seems much less of a problem than finding a machine with enough memory to deal with the result.

    Perhaps you should describe the problem you're trying to solve, rather than how to implement your current approach.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User FortranLevelC++'s Avatar
    Join Date
    May 2013
    Location
    United States
    Posts
    81
    Quote Originally Posted by Salem View Post
    > int N = 15; // chosen arbitrary rank
    > vector<vector<vector<...<vector<double>>>>..> vec; // N layers of nested vectors
    And how many elements do you plan to store in each dimension?

    With just the equivalent of
    double vec[4][4][4][4][4][4][4][4][4][4][4][4][4][4][4];
    you're looking at 8GB just to store the data, and who knows how overhead of storing all the vector information.

    Replace 4 with 5, and it jumps to 256GB!

    Declaring it seems much less of a problem than finding a machine with enough memory to deal with the result.

    Perhaps you should describe the problem you're trying to solve, rather than how to implement your current approach.
    Thanks a lot for the comments.

    The above choice N=15 was only for illustration purposes. So far I have not yet used more than 4 layers of vectors, and probably the N will never exceed 7.

    But I would like to make this rank N variable, to add flexibility.

  4. #4
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Code:
    template <typename T, int N>
    class NestedVectorType
    {
    public:
    	typedef std::vector<typename NestedVectorType<T, N-1>::type> type;
    };
    
    template <typename T>
    class NestedVectorType<T, 1>
    {
    public:
    	typedef std::vector<T> type;
    };
    
    // Declare a 15-dimensional vector of integers
    NestedVectorType<int, 15>::type vec;
    EDIT: More would be required than just this basic level to be useful. For instance, functions to set the size of the vector's various dimensions.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  5. #5
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    You can do it in any standard version of C++

    Code:
    #include <vector>
    
    template<std::size_t n> struct Vec
    {
         typedef std::vector<typename Vec<n-1>::type>  type;
    };
    
    template<> struct Vec<0>
    {
         typedef double type;
    };
    
    int main()
    {
          Vec<15>::type   a_vector;
    }
    You'll get an unpleasant surprise with how long it takes to compile though.

    The technique is recursive at compile time, and most modern compilers enforce a limit on the depth of that recursion.

    Note also that, as shown, the vectors are not sized. All you get from this is a multidimensional array .... with each dimension being of zero length. I'll leave sorting that out as an exercise (not least of which because I haven't thought through how to do that).


    The real world need for more than 5 dimensions in a matrix is pretty rare (except in cases of poor design).
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

  6. #6
    Registered User FortranLevelC++'s Avatar
    Join Date
    May 2013
    Location
    United States
    Posts
    81
    Thanks a lot!

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    It's worth noting that although Salem mentioned a 15-dimensional array with each dimension of length 4 would be 8 GB, that with vectors it would be even worse. A vector typically consists of 3 pointers, likely 4 or 8 bytes each depending on platform, plus the rest on the heap. These pointers themselves exceed the size of the data by my estimates, and that's not including the fact that heap allocations are typically rounded up to the nearest 8 bytes in size or so either.
    Every item in a 15-dimensional matrix requires traversing 14 levels of vectors to get to it too. That's following 15 pointers to get there!
    Performance would be, in a word... "laughable".

    It probably doesn't make sense to use vectors in this case. Unless any of the dimensions must be adjustable or it must be a ragged matrix (e.g. rows with different length), then the better option is to use a nested std::array.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    If you need such a high rank, sparse matrix is the way to go. However, this requires you to write your own variadic class template which must consider the rank. As a really simple, reference implementation, std::unordered_map of tuples as keys can do the job. I've written a simplified implementation with operator() which takes a variable number of parameters and forwards them as tuple to the map (operator() acts here the same way as operator[], but can take a variable number of operands and hides implementation detail which is using a tuple).

    Code:
    #include <iostream>
    #include <string>
    #include <tuple>
    #include <unordered_map>
    
    // http://stackoverflow.com/questions/7110301/generic-hash-for-tuples-in-unordered-map-unordered-set
    
    size_t hash_combiner(size_t left, size_t right) //replacable
    { return left^right;}
    
    template<int index, class...types>
    struct hash_impl {
        size_t operator()(size_t a, const std::tuple<types...>& t) const {
            typedef typename std::tuple_element<index, std::tuple<types...>>::type nexttype;
            hash_impl<index-1, types...> next;
            size_t b = std::hash<nexttype>()(std::get<index>(t));
            return next(hash_combiner(a, b), t);
        }
    };
    template<class...types>
    struct hash_impl<0, types...> {
        size_t operator()(size_t a, const std::tuple<types...>& t) const {
            typedef typename std::tuple_element<0, std::tuple<types...>>::type nexttype;
            size_t b = std::hash<nexttype>()(std::get<0>(t));
            return hash_combiner(a, b);
        }
    };
    
    namespace std {
        template<class...types>
        struct hash<std::tuple<types...>> {
            size_t operator()(const std::tuple<types...>& t) const {
                const size_t begin = std::tuple_size<std::tuple<types...>>::value-1;
                return hash_impl<begin, types...>()(1, t); //1 should be some largervalue
            }
        };
    }
    
    // END of stack overflow code
    
    template <typename TupleT, typename T>
    struct AppendTupleElement;
    
    template <typename... Types, typename T>
    struct AppendTupleElement<std::tuple<Types...>, T>
    {
        typedef std::tuple<Types..., T> type;
    };
    
    template <unsigned int N>
    struct GenerateSparseMatrixKey
    {
        typedef typename AppendTupleElement
            <
                typename GenerateSparseMatrixKey<N - 1>::type,
                unsigned int
            >::type type;
    };
    
    template <>
    struct GenerateSparseMatrixKey<0>
    {
        typedef std::tuple<> type;
    };
    
    template <typename T, unsigned int N>
    class SparseMatrix
    {
    public:
    
        typedef T MappedType;
    
        static constexpr unsigned int Rank = N;
    
        // This is the actual indexing operator.
        // Passing arguments of wrong types, or passing their wrong number,
        // will result in compile-time error.
        template <typename... Dimensions>
        MappedType& operator()(Dimensions... dimensions)
        {
            return map[std::forward_as_tuple(dimensions...)];
        }
    
    private:
    
        typedef typename GenerateSparseMatrixKey<N>::type KeyType;
    
        // std::unordered_map has tuple as its key. I took tuple hashing
        // from stack overflow which specializes std::hash, but I would
        // personally do it by defining a separate hashing class which then
        // I would explicitly pass as a third template argument.
        std::unordered_map<KeyType, MappedType> map;
    };
    
    int main()
    {
        SparseMatrix<std::string, 4> matrix;
        matrix(0, 0, 1, 2) = "AA";
        matrix(0, 0, 1, 3) = "BB";
        matrix(0, 0, 4, 4) = "CC";
    
        std::cout << matrix(0, 0, 1, 2) << std::endl;
        std::cout << matrix(0, 0, 1, 3) << std::endl;
        std::cout << matrix(0, 0, 1, 4) << std::endl; // doesn't exist
        std::cout << matrix(0, 0, 4, 4) << std::endl;
    }
    Compiles with GCC 4.8.1.
    Last edited by kmdv; 09-22-2013 at 04:41 AM.

  9. #9
    Registered User FortranLevelC++'s Avatar
    Join Date
    May 2013
    Location
    United States
    Posts
    81
    Many thanks for the Sparse Matrix formulation. This is very interesting. And the code compiles without any problems.

  10. #10
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    From your username, I infer you know a bit of Fortran. If that's the case, I'm surprised you haven't come across sparse matrices before. It is a rare Fortran programmer who tries to build high-dimensional arrays without knowing about sparse matrices.
    Right 98% of the time, and don't care about the other 3%.

    If I seem grumpy or unhelpful in reply to you, or tell you you need to demonstrate more effort before you can expect help, it is likely you deserve it. Suck it up, Buttercup, and read this, this, and this before posting again.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. vector<vector<const char*>> behaving strangely
    By unixmania in forum C++ Programming
    Replies: 6
    Last Post: 07-26-2013, 02:50 PM
  2. Replies: 4
    Last Post: 07-05-2013, 02:30 AM
  3. Replies: 16
    Last Post: 06-13-2013, 06:15 PM
  4. Converting string vector to integer vector
    By CPlus in forum C++ Programming
    Replies: 4
    Last Post: 05-08-2010, 05:43 AM
  5. Simple Question memset(vector<int>, 0, sizeof(vector<int>))
    By HyperShadow in forum C++ Programming
    Replies: 6
    Last Post: 12-10-2007, 04:56 PM