Tablica nieprostokątna

pytanie zadane 19 lutego 2018 w C i C++ przez Kabuuz Bywalec (2,820 p.)

Cześć. Da się w jakiś prosty sposób utworzyć tablice która nie jest prostokątna? Widziałem jakiś sposób ze wskaźnikami (wskaźnik na wskaźnik? ** takie coś było) i zastanawiam się czy nie ma prostszej metody.

2 odpowiedzi

odpowiedź 19 lutego 2018 przez mokrowski Mędrzec (155,460 p.)
edycja 19 lutego 2018 przez mokrowski

Można oczywiście wskaźnikami. Będziesz jednak zajmował się szczegółami które spowodują wprowadzanie wielu ilości błędów (brak dealokacji, zła arytmetyka wskaźników, błędne dostępy). Lepiej zacząć od std::vector zawierające inne std::vector :-) Jeśli będziesz wiedział jakie mają być prawdziwe ograniczenia tej struktury, zmienisz typ danych. Naprawdę na początku programowania 95% zastosowań kontenerów to... std::vector :-)

#include <iostream>
#include <vector>

using container_t = std::vector<std::vector<int>>;
using row_t = typename container_t::value_type;

void makeTriangle(container_t& data) {
    for(auto i = 0U; i < data.size(); ++i) {
        data[i] = row_t(i + 1);
    }
}

void showData(const container_t& data) {
    for(const auto& row: data) {
        for(const auto& field: row) {
            std::cout << field << ' ';
        }
        std::cout << '\n';
    }
}

int main() {
    constexpr static size_t DATA_SIZE = 20;
    // 20 wierszowy wektor...
    container_t data(DATA_SIZE);
    makeTriangle(data);
    showData(data);
}

Jeśli upierasz się przy wskaźnikach i tablicach dynamicznych, otrzymasz jakiś taki kod:

#include <iostream>
#include <vector>

constexpr static size_t DATA_SIZE = 20;

void makeTriangle(int *** data) {
    *data = new int *[DATA_SIZE];
    for(auto i = 0U; i < DATA_SIZE; ++i) {
        (*data)[i] = new int[i + 1]();
    }
}

void showData(int *** data) {
    for(auto row = 0U; row < DATA_SIZE; ++row) {
        for(auto col = 0U; col < row + 1; ++col) {
            std::cout << (*data)[row][col] << ' ';
        } 
        std::cout  << '\n';
    }
}

void disposeData(int *** data) {
    for(auto row = 0U; row < DATA_SIZE; ++row) {
        delete [] (*data)[row];
    }
    delete [] (*data);
}

int main() {
    int ** data;
    makeTriangle(&data);
    showData(&data);
    disposeData(&data);
}

Sam oceń czy to jest czytelne i nie popełnisz błędu :-/ Dane do funkcji przekazywane są przez wartość, stąd konieczność przekazania 3-krotnego wskaźnika. Dane są 2-krotnym wskaźnikiem.

Dla maksymalnej wydajności i przy tablicach o regularnej strukturze (np. takiej jak w przykładach), alokuje się ciągłe miejsce w pamięci czyli tablicę 1-wymiarową. Wymaga to później w trakcie dostępów obliczania adresu docelowego. Taka implementacja będzie wydajniejsza ze względu na trafianie w cache procesora.

komentarz 19 lutego 2018 przez Knayder Nałogowiec (37,640 p.)

Ale ty wiesz że kod który ma coś komuś wytłumaczyć, ma być możliwie najbardziej prosty?
Gościu który nie rozumie jeszcze dokładnie tablic, ma ci coś takiego analizować?

komentarz 19 lutego 2018 przez Hiskiel Pasjonat (22,830 p.)

@mokrowski, to co tu widzę... Co oznacza constexpr i o co cm z typename? To nie jest szablon..

komentarz 19 lutego 2018 przez Knayder Nałogowiec (37,640 p.)

http://en.cppreference.com/w/cpp/language/constexpr

komentarz 19 lutego 2018 przez Hiskiel Pasjonat (22,830 p.)

A po co się stosuje ten prefiks? Nie widzę sensu w stosowaniu go.

komentarz 19 lutego 2018 przez mokrowski Mędrzec (155,460 p.)

W programowaniu obowiązuje zasada DRY (Don't Repeat Yourself) czyli "nie powtarzaj się". Stąd za każdym razem gdy wklepywany jest taki sam kod, można popełnić pomyłkę i należy go zdefiniować wcześniej.

Zaps:

using container_t = std::vector<std::vector<int>>;
using row_t = typename container_t::value_type;

Oznacza tworzenie 2 nazw typów gdzie 1 (container_t) to wektor wektorów przetrzymujący int. Drugi to typ wiersza. Tak się składa że każdy kontener przetrzymuje w swojej definicji typ danych wewnętrznych o nazwie value_type. To typ zależny (bo zależy od samego kontenera), więc wymaga podania typename by poinformować kompilator że to typ a nie pole statyczne.

Bez definicji tych typów, można oczywiście "powklejać'" w każde wystąpienie container_t, std::vector<std::vector<int>> a w wystąpienie row_t, std::vector<int>.

Dzięki tym 2 liniom, nie będę pracowicie klepał skomplikowanych nazw w kodzie.

Wyrażenie z constexpr, to definiowanie stałej. W ten sposób robi się to od 2011. Dzięki takiej definicji, można użyć tych wyrażeń także w funkcjach constexpr (czyli wykonywanych w trakcie kompilacji). Stałe zawsze należy definiować do przyszłego ich użycia. Inaczej będą miały charakter "wartości magicznej" co utrudni utrzymanie i analizę programu.

To co prezentuje, jest mocno zbliżone do standardów kodowania w projektach w których uczestniczę. Pokazałem porównanie podejścia z kontenerem do podejścia "poprzez wskaźnik". To drugie na poziomie logiki aplikacji ma w zasadzie same wady. Zgadzam się że w embedded, blisko sprzętu, nie ma wyjścia. Na tym poziomie to jednak katowanie się i bardzo zła praktyka programistyczna. Do tego stopnia zła że IMHO nie usprawiedliwia traktowania jej jako prostszej (3 x wskaźnik... to ma być proste? ).

Radzę zwrócić uwagę na pierwotne pytanie. Chodziło o prostą metodę. Metoda z kontenerem std::vector w zasadzie sama się broni przez semantykę wywołań i brak problemów z dealokacją zasobu którą trzeba robić ręcznie w rozwiązaniu "przez wskaźnik".

komentarz 19 lutego 2018 przez Treners Początkujący (310 p.)

@Knayder, a skąd Ty to wiesz? Może niech zapyta to się czegoś dowie? ;-)

komentarz 19 lutego 2018 przez Knayder Nałogowiec (37,640 p.)

By przeprowadzać operacje compile-time.
Czyli w czasie kompilacji, kompilator sobie wszystko liczy, a potem tylko używa obliczonego wyniku.
Nie używa się tego raczej tak, jak pokazał to @mokrowski.

#include <iostream>

template<size_t N, typename T>
struct Fibb {
	constexpr static T value = Fibb<N - 1u, T>::value + Fibb<N - 2u, T>::value;
};

template<typename T>
struct Fibb<0u, T> {
	constexpr static T value = static_cast<T>(0);
};

template<typename T>
struct Fibb<1u, T> {
	constexpr static T value = static_cast<T>(1);
};

int main() {
	std::cout << Fibb<80, unsigned long long>::value << '\n';
	std::cin.get();
}

Tutaj masz meta funkcje do liczenia N-tej liczby fibbonaciego w czasie kompilacji.

komentarz 19 lutego 2018 przez mokrowski Mędrzec (155,460 p.)
edycja 19 lutego 2018 przez mokrowski

No popatrz...

http://en.cppreference.com/w/cpp/language/constant_expression

https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#con5-use-constexpr-for-values-that-can-be-computed-at-compile-time

https://google.github.io/styleguide/cppguide.html#Use_of_constexpr

Po co szablonem jak można od 3 lat najprościej...

#include <iostream>
 
template<typename T>
constexpr T fibo(size_t n) {
    T x0 = 0;
    T x1 = 1;
    for(T i{}; i < n; ++i) {
        auto temp = x0;
        x0 = x1;
        x1 += temp;
    }
    return x0;
}
 
int main() {
    std::cout << fibo<unsigned long long>(80) << '\n';
}

I nie ryzykujesz ograniczeń co do zagnieżdżenia szablonu... (na poziomie ~ 1000).

W C++11 także się dla constexpr ale nie da się uniknąć rekurencji.

odpowiedź 19 lutego 2018 przez Knayder Nałogowiec (37,640 p.)
edycja 19 lutego 2018 przez Knayder

std::vector<std::vector<int>>;

W wektorze masz wektory. Każy z nich może być różnej długości. np.

XXXXXX

XXXX

XXXXXXXXXXXX

Oczywiście możesz też użyć dynamicznej alokacji:

int **tab = new int*[5];
for(int i = 0; i<5;i++)
 tab[i] = new int[i+1];
/*
X
XX
XXX
XXXX
XXXXX
*/
for(int i = 0; i<5;i++)
 delete[] tab[i];
delete[] tab;