Блог пользователя mohmahkho

Автор mohmahkho, 4 года назад, По-английски

Hi! I hope you are doing well.

If you are in love(!) with vectors and you use them a lot, you probably know that defining a multidimensional vector is just a pain in the neck! For example if you are trying to define a 3 dimensional vector with (n, m, k) as dimensions you have to write it like this :

vector<vector<vector<int>>> a(n, vector<vector<int>>(m, vector<int>(k)));

Then you change your mind and realize that your data will not fit in an int. You decide to change it to long long.

vector<vector<vector<long long>>> a(n, vector<vector<int>>(m, vector<int>(k)));

[HITS COMPILE BUTTON] Oops! won't compile (G++ really get's mad at you). Go on and change inner vectors as well.

vector<vector<vector<long long>>> a(n, vector<vector<long long>>(m, vector<long long>(k)));

So if you want a 100 dimensional vector of long longs, you literally have to say it 100 times to the compiler that you want your data to be long long.
Well what's the solution?

N dimensional vector using template meta programming

So yes, there is this thing called template meta programming which I'm not going to discuss here. But you can do cool things with it! One of the cool things is just N dimensional vector (basically D dimensional!). Here's the code:

template<int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
  static_assert(D >= 1, "Vector dimension must be greater than zero!");
  template<typename... Args>
  Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {
  }
};
template<typename T>
struct Vec<1, T> : public vector<T> {
  Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {
  }
};

This is essentially publicly inheriting from vector<vector<vector< ... vector<T> ... >>> in which vector appears D times!
It has a constructor which takes dimensions in order and if you want to initialize your multidimensional vector with some value you can pass that value to the constructor as the last argument otherwise it will be initialized with zero (or if it's a class it will be initialized using default constructor). If you provide less than D numbers to the constructor, following dimensions will have length equal to zero.
A few examples :

Vec<2, int> a(10, 50); // int a[10][50] initialized with zero
Vec<3, double> b(n, m, k, 3.14); // double b[n][m][k] initialized with 3.14
Vec<3, long long> c(5, 5); // the third dimension has no value yet
c[0][0].push_back(100); // now c[0][0][0] has a value (100) but others don't
Vec<4, int> d(10, 10);
d[2][3].push_back(Vec<1, int>(100, 12345)); // now d[2][3][0] is a vector with 100 values of 12345
Vec<1, string> e; // just blank vector of strings

Based on C++11 (or above) standard this code will compile.
Template arguments must be compile time constants, for example Vec<n, int> in which n is the user input, won't compile, which makes a lot of sense.

  • Проголосовать: нравится
  • +417
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

I loved your effort. It is awesome.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

Nice use of templates, added to my library. Keep doing such experiments

»
4 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Salute you,brother. You saved my time.

»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Awesome, you just discovered arrays!

Just kidding, well done!

»
4 года назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

Fuck array. All my homies use vector.

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Bookmarked!!

»
4 года назад, # |
  Проголосовать: нравится -33 Проголосовать: не нравится

مهبل كس مهبل مهبل ديك لول موظر مص الحمار الحمار لعق الشرج

»
4 года назад, # |
  Проголосовать: нравится +58 Проголосовать: не нравится

I think I've got it more elegant:

template<class... Args>
auto create(size_t n, Args&&... args) {
	if constexpr(sizeof...(args) == 1)
		return vector(n, args...);
	else
		return vector(n, create(args...));
}

It requires C++17. Usage:

int n, m;
cin >> n >> m;
auto dp = create(n, m, 0LL);

That creates a vector<vector<long long>> of size n by m filled with value 0. As you see, the code is shorter and it doesn't need constant sizes.

Thanks kwazar for showing this neat trick. Working example: https://codeforces.com/contest/1336/submission/77118622

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    That's interesting and the good part I think is that you don't inherit from std::vector.
    However I like to be explicit about type of the container. When I write Vec<3, int> I know it's a 3 dimensional vector of ints, and if I don't care about the third dimensions size, I just don't write it there (Vec<3, int> a(n, m) and the third dimension is yet to be decided).
    Also I think there is a misunderstanding about what I said in the last line. I just said the number of dimensions must be compile time constant not the dimension size and something like Vec<2, long long> v(n, m, 0) is completely legit in my code.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      The last argument explicitly tells the compiler what type it should be. auto dp = create(n, m, int(42)) is even more specific. If that isn't explicit enough, you can look at this:

      template<class T, class... Args>
      auto create(size_t n, Args&&... args) {
      	if constexpr(sizeof...(args) == 1)
      		return vector<T>(n, args...);
      	else
      		return vector(n, create<T>(args...));
      }
      auto dp = create<double>(n, m, 42.69);
      
      

      I find create(n, m, 0, 0) more readable and less error-prone than Vec<3, int>(n, m), though that might be my personal preference.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    tnowak How to pass this to function?

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

That kind of template is really useful. I have been experimenting in-contest with a similar one.

One feature I added to my template that I liked, is to override the operator() so you can query and assign using syntax:

dp(i, j, k) instead of the usual dp[i][j][k],

for example this 76759577

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Yeah, I was once thinking about it, it's probably easier to write, however you may confuse it with normal function call. It would have been way better to be able to write it like dp[i, j, k] but operator[] has to take only one parameter.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

This can also be done using the template argument deduction feature of C++17. This produces a 100x200x300 3D array.

vector arr3D(100, vector(200, vector(300, 123)));
  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Two issues:
    1- C++17 (some OJs don't support it even though they should IMO)
    2- You still have to write "vector" for each dimension.
    BTW it's a matter of taste I guess.

»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Thanks for sharing this trick! Unfortunately, clang doesn't accept this code, which is problematic for those who use clang-powered auto-completion like me :(

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Btw, if you're after something sufficiently practical and easy to remember rather than fancy template metaprogramming, defining your own derived classes vec1D<T>, vec2D<T> etc also works. It's not like you're ever going to use a 5 times nested vector, it will have some tiny dimensions and the memory access overhead will be crazy.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I want to initialize Vec<1, T> with initializer list like vector{}. Does anyone have a method to do this?

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

    The easiest way to tweak the code to support what you wanted (that came to my mind) :

    template<int D, typename T>
    struct Vec : public vector<Vec<D - 1, T>> {
      static_assert(D >= 1, "Vector dimension must be greater than zero!");
      template<typename U, typename... Args>
      Vec(U n = U(), Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {
      }
    };
    template<typename T>
    struct Vec<1, T> : public vector<T> {
      template<typename... Args>
      Vec(Args... args) : vector<T>(args...) {
      }
    };
    

    then you will be able to initialize it with another vector like this:

    vector<int> a {2, 7, 1, 8};
    Vec<1, int> b(a);
    Vec<1, int> c(a.begin() + 1, a.end());
    Vec<1, int> d(initializer_list<int> {3, 1, 4, 1, 5, 9});
    

    Note that it is still possible to use it the old way.