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

Автор CodingKnight, 6 лет назад, По-английски

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
  • Проголосовать: не нравится

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

Wtf why do people downvote? Its a kinda useful article, you won't meet many of them nowadays

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

An alternative approach: Map element (i, j) to element in a 1D array.

  • »
    »
    6 лет назад, # ^ |
    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.