### CodingKnight's blog

By CodingKnight, 4 years ago,

In matrix theory, a lower-triangle/upper-triangle matrix is a special n × n square matrix where its items above/below the main diagonal are zeros, and therefore at most of its items are non-zeros. Formally, a lower-triangle matrix A satisfies the condition ai, j = 0 if i < j, and an upper-triangle matrix A satisfies the condition ai, j = 0 if i > j, where i is the row index, j is the column index, and 1 ≤ i, j ≤ n.

The following are simple and memory-efficient C++ templates for lower-triangle and upper-triangle matrices that allocate dynamically at run-time using the vector::resize() STL member function the size of each row to store only the non-zero items. This can be useful in saving about half the memory size of the full square matrix when n is large. Individual non-zero items are updated in both templates using set() member function, and the value of an individual zero/non-zero item is read using get() member function.

#include <bits/stdc++.h>

using namespace std;

template< typename T > struct lower_triangle: vector< vector< T > >
{
lower_triangle( size_t n )
{
for( size_t row_size = 1; row_size <= n; row_size++ )
this->emplace_back(), this->back().resize( row_size );
}

void set( size_t i, size_t j, T k )
{
assert( i >= j and i >= 1 ), this->at( i - 1 ).at( j - 1 ) = k;
}

T get( size_t i, size_t j ) const
{
return ( i >= j and i >= 1 ) ? this->at( i - 1 ).at( j - 1 ) : 0;
}
};

template< typename T > struct upper_triangle: vector< vector< T > >
{
upper_triangle( size_t n )
{
while( n > 0 )
this->emplace_back(), this->back().resize( n-- );
}

void set( size_t i, size_t j, T k )
{
assert( j >= i and i >= 1 ), this->at( i - 1 ).at( j - i ) = k;
}

T get( size_t i, size_t j ) const
{
return ( j >= i and i >= 1 ) ? this->at( i - 1 ).at( j - i ) : 0;
}
};



The following is a sample program that illustrates using these C++ templates.

int main()
{
ios_base::sync_with_stdio( false ), cin.tie( nullptr ), cout.tie( nullptr );

int n; cin >> n; lower_triangle< int > L( n ); upper_triangle< int > U( n );

for( int i = 1; i <= n; i++ )
{
for( int j = 1, k = i; j <= i; j++, k++ )
L.set( i, j, k );

for( int j = i, k = 2 * i - 1; j <= n; j++, k++ )
U.set( i, j, k );
}

for( int i = 1; i <= n; i++, cout << endl )
for( int j = 1; j <= n; j++ )
cout << L.get( i, j ) << ' ';

cout << endl;

for( int i = 1; i <= n; i++, cout << endl )
for( int j = 1; j <= n; j++ )
cout << U.get( i, j ) << ' ';
}


UPDATE

The following is an alternative approach for implementing the C++ templates using one-dimensional arrays based on the constructive comment from f2lk6wf90d. Performance analysis should compare the average execution time and memory requirements of both approaches. A word of gratitude is due to tryhard for recommending this modest blog.

inline size_t C2( size_t n ) { return n * ( n - 1 ) / 2; }

template< typename T > struct lower_triangle: vector< T >
{
lower_triangle( size_t n )
{
this->resize( C2( n + 1 ) );
}

void set( size_t i, size_t j, T k )
{
assert( i >= j and i >= 1 ), this->at( C2( i ) + j - 1 ) = k;
}

T get( size_t i, size_t j ) const
{
return ( i >= j and i >= 1 ) ? this->at( C2( i ) + j - 1 ) : 0;
}
};

template< typename T > struct upper_triangle: vector< T >
{
size_t N, P;

upper_triangle( size_t n ) : N( n ), P( n + 1 )
{
this->resize( C2( P ) );
}

void set( size_t i, size_t j, T k )
{
assert( j >= i and i >= 1 );  this->at( C2( P - i ) + N - j ) = k;
}

T get( size_t i, size_t j ) const
{
return ( j >= i and i >= 1 ) ? this->at( C2( P - i ) + N - j ) : 0;
}
};


• +7

 » 4 years ago, # |   -35 Wtf why do people downvote? Its a kinda useful article, you won't meet many of them nowadays
 » 4 years ago, # |   +14 An alternative approach: Map element (i, j) to element in a 1D array.
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 Provided that the size of the 1D array is , this alternative approach should work for a lower-triangle matrix. For an upper-triangle matrix, the element (i, j) should be mapped to the element in the 1D array. Alternatively, the upper-triangle matrix mapping function can be expressed as , where u = n + 1 - i and v = n + 1 - j.