Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Diskuze: Pole více datových typů

Aktivity
Avatar
švrčajs
Člen
Avatar
švrčajs:11.12.2016 11:19

Zdravím, potřeboval bych menší radu, mám vyřešit v c++ jeden problém. Jedná se o napsání jedné šablony, která mi připomíná HashMap(java), Dictionary(c#)... V zadání je, že se mají ukládat Key i Value do jednoho pole (mají se zároveň i zatřídit)... S tím by problém nebyl, ale nemůžu přijít na to, jak vytvořit vícerozměrné pole, tak aby do něj na první pozici šel uložet Key a na druhou Value, protože můžou být rozdílných datových typů... První možnost, kterou jsem chtěl použít :D byl list, ale ten použít nemůžu, díky zadání... Ne

Šablona má vypadat takto

template<class T, class S>
class AsociativniPole { };
  • metody, ale ty mám už promyšlené

Neporadil by prosím někdo ?

 
Odpovědět
11.12.2016 11:19
Avatar
Jan Vargovský
Tvůrce
Avatar
Odpovídá na švrčajs
Jan Vargovský:11.12.2016 11:55

Co něco takového?

template<class T, class S>
class AsociativniPole {
private:
        struct Item {
                T Key;
                S Value;
        };

        Item * arr;
};
 
Nahoru Odpovědět
11.12.2016 11:55
Avatar
Jakub Šilhavý:11.12.2016 11:59

Já jsem řešil něco podobného u robotické ruky, kde jsem měl n krokových motorů a různé parametry k nim (masky, piny, název,.. což je víc datových typů). Udělal jsem si strukturu s těmito datovými typy a pak jsem si jen jednoduše udělal pole této struktury :) Koukni se na http://www.itnetwork.cz/…-c-struktury třeba by se to dalo použít v tvém případě... :P.

Nahoru Odpovědět
11.12.2016 11:59
Život je pes, a proto žít je psina.
Avatar
švrčajs
Člen
Avatar
Odpovídá na Jan Vargovský
švrčajs:11.12.2016 12:03

Díky moc, teď to zkouším pomocí pole párů :D Případně použiju strukturu ;)

 
Nahoru Odpovědět
11.12.2016 12:03
Avatar
švrčajs
Člen
Avatar
švrčajs:11.12.2016 16:09

Trošku jsem pokročil, ale mám tam teď problém, když chci získat prvek z pole.. Hází mi to chybu: Unhandled exception at 0x74CAA6F2 in cplusbonus.exe: Microsoft C++ exception: std::bad_alloc at memory location 0x0019E790.

jinak kod mam zatim takový:

// cplusbonus.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <utility>

using namespace std;

template<class T, class S>
class AsociativniPole {
private:
        int vrchol;
        int iterator;
        int velikost;

        pair<T, S> * pole;


public:
        AsociativniPole(unsigned n) { pole = new pair<T, S>[n]; vrchol = -1; iterator = -1; velikost = n; }

        //nastaví iterátor na první prvek
        bool prvni()
        {
                if (vrchol == -1)
                        return false;
                iterator = 0;
                return true;
        }
        //vrátí počet prvků v poli
        int operator + ()
        {
                return vrchol + 1;
        }

        //vrátí aktuální prvek
        const S& aktualni()
        {
                pair<T,S> p = pole[iterator];
                return p.second;
        }

        //vrátí další prvek
        bool dalsi()
        {
                if (iterator == vrchol)
                        return false;
                iterator++;
                return true;
        }

        //vkládání prvků se zatříděním podle velikosti klíče
        int vlozit(const T & first, const S & second)
        {
                vrchol++;
                if (vrchol == velikost)
                        return -1;
                pair<T, S> p = make_pair(first, second);

                //nalezení indexu, kam umístit prvek
                int i = 0;
                if (vrchol == 0) pole[vrchol] = p;
                else {
                        while (pole[i].first <= p.first) {
                                //když se v poli nachází tento klíč => nepřidá se a vrátí nulu
                                if (pole[i].first == p.first) return 0;
                                i++;
                        }

                        //přeskupení pole, aby bylo zatříděné
                        for (i; i < vrchol; i++) {
                                //uložení prvku, který bude nahrazen
                                pair<T, S> temp = pole[i + 1];
                                pole[i] = p;
                                p = temp;
                        }
                }
                //přidání bylo úspěšné
                return 1;
        }
};





int main()
{
        int x = 1;
        string y = "ahoj";
        int x1 = 2;
        string y1 = "2ahoj";


        AsociativniPole<int, string> pole = AsociativniPole<int, string>::AsociativniPole(10);
        pole.vlozit(x1, y1);
        pole.vlozit(x, y);
        string s = pole.aktualni();
        cout << pole.aktualni().c_str() << endl;

        getchar();
        return 0;
}

Přijde mi, jako bych blbě alokoval pole :D ale čumím na to jak puk a nevím, co s tím :/ :D

 
Nahoru Odpovědět
11.12.2016 16:09
Avatar
Odpovídá na švrčajs
Drahomír Hanák:11.12.2016 17:28

Jednak v metodě aktualni() bude iterator == -1, protože ho v metodě vlozit neměníš. Dál tam vracíš referenci na lokální proměnnou (ten pár si nejdřív zkopíruješ do proměnné p a pak na ni vracíš referenci, jenže ona zanikne hned po skončení funkce).

Navíc neuvolňuješ alokovanou paměť. Zvážil jsi použít třeba std::vector místo ručně alokované paměti? Proměnné té třídy by asi bylo lepší inicializovat přímo při vzniku toho objektu (http://en.cppreference.com/…ializer_list) Část toho rozhraní mi přijde dost neintuitivní. Operátor + vrací velikost? Úplně nejlepší by bylo, kdyby to mělo podobné rozhraní jako mají ostatní kontejnery ve standardní knihovně, ale s tím je dost práce, když to chceš udělat pořádně. Ve standardní knihovně (konkrtně algorithms: http://en.cppreference.com/w/cpp/algorithm) je taky docela dost užitečných funkcí, které by se ti mohly hodit.

 
Nahoru Odpovědět
11.12.2016 17:28
Avatar
švrčajs
Člen
Avatar
Odpovídá na Drahomír Hanák
švrčajs:11.12.2016 17:40

Ehm, to bude jen v případě, že bude prázdné pole, jinak se iterátor mění s přidáváním prvků... Co se týče operátoru + :D za to já nemůžu, jedu podle zadání... Ale díky, projedu ty linky a uvidím, jestli s tím hnu...

 
Nahoru Odpovědět
11.12.2016 17:40
Avatar
švrčajs
Člen
Avatar
Odpovídá na Drahomír Hanák
švrčajs:11.12.2016 17:51

A k tomu vektoru :D to místo pole použít nemůžu, protože v zadání je použijte pole...

 
Nahoru Odpovědět
11.12.2016 17:51
Avatar
Odpovídá na švrčajs
Drahomír Hanák:11.12.2016 18:11

Tak by to nejspíš mělo být. Ve funkci vlozit ji ale neměníš a ani nevoláš žádnou funkci, která by ji měnila, takže její hodnota bude pořád -1 (navíc výraz pole[-1] je validní, jenom se odkazuješ na paměť, která ti nepatří). Každopádně ta chyba, která vyvolá výjimku, je způsobená tím, že vracíš referenci na lokální proměnnou. Teď jsem to zkoušel ve Visual Studiu a to tě na to dokonce upozorní (warning C4172: returning address of local variable or temporary: p)

 
Nahoru Odpovědět
11.12.2016 18:11
Avatar
švrčajs
Člen
Avatar
Odpovídá na Drahomír Hanák
švrčajs:11.12.2016 22:01

Kód jsem upravil a furt mi to nefugovalo, tak jsem zkusil naalokovat pole "natvrdo"

pair<T, S> pole[10];

a funguje to, jenže ho protřebuju naalokovat dynamicky, což dělám dle mého úsudku správně

pair<T, S> *pole;
pole = new pair<T, S>[n];

a po tomto naalokování mi to nejde :D tak nevím, co dělám blbě, asi musím být za exota, ale lámu si s tím hlavu už 3 hodiny a nic...

Komplet kod:

// cplusbonus.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <utility>

using namespace std;

template<class T, class S>
class AsociativniPole {
private:
        int vrchol;
        int iterator;
        int velikost;

        pair<T, S> pole[10];

public:
        AsociativniPole(unsigned n) {vrchol = -1; iterator = -1; velikost = n; }

        //nastaví iterátor na první prvek
        bool prvni()
        {
                if (vrchol == -1)
                        return false;
                iterator = 0;
                return true;
        }
        //vrátí počet prvků v poli
        int operator + ()
        {
                return vrchol + 1;
        }

        //vrátí aktuální prvek
        const S& aktualni()
        {
                return pole[iterator].second;
        }

        //vrátí další prvek
        bool dalsi()
        {
                if (iterator == vrchol)
                        return false;
                iterator++;
                return true;
        }

        //vkládání prvků se zatříděním podle velikosti klíče
        int vlozit(const T & first, const S & second)
        {
                vrchol++;
                if (vrchol == velikost)
                        return -1;
                pair<T, S> p = make_pair(first, second);
                iterator++;
                //nalezení indexu, kam umístit prvek
                int i = 0;
                if (vrchol == 0) {
                        pole[vrchol] = p;
                }
                else {
                        while (pole[i].first <= p.first) {
                                //když se v poli nachází tento klíč => nepřidá se a vrátí nulu
                                if (pole[i].first == p.first) return 0;
                                i++;
                        }

                        //přeskupení pole, aby bylo zatříděné
                        for (i; i < vrchol+1; i++) {
                                //uložení prvku, který bude nahrazen
                                pair<T, S> temp = pole[i];
                                pole[i] = p;
                                p = temp;
                        }
                }
                //přidání bylo úspěšné
                return 1;
        }
};





int main()
{
        int x = 1;
        string y = "ahoj";
        int x1 = 2;
        string y1 = "2ahoj";


        AsociativniPole<int, string> pole = AsociativniPole<int, string>::AsociativniPole(10);
        pole.vlozit(x1, y1);
        pole.vlozit(x, y);
        string s = pole.aktualni();
        cout << pole.aktualni().c_str() << endl;

        getchar();
        return 0;
}
 
Nahoru Odpovědět
11.12.2016 22:01
Avatar
Odpovídá na švrčajs
Drahomír Hanák:11.12.2016 22:47

Mně to už žádnou chybu nevyhazuje ani když tam použiju dynamickou alokaci. Správně to ale nefunguje. Např. když vložím hodnotu s klíčem, který už tam je, tak se zvýší vrchol i iterator, ale žádná nová položka se do toho pole nepřidá. Taky to přeuspořádání pole nefunguje správně (prohazuješ tam prvek pole s lokální proměnnou). Když přidáš klíč, který je větší než všechny klíče, co jsou zatím s poli, tak ten while cyklus poleze mimo pole (protože ta podmínka bude splněna pro všechny prvky, takže i se může zvětšovat až za hranice pole).

Navrhuju tu else větev udělat takhle (N je počet prvků v tom poli, předpokládám, že máš alokované dostatečně velké pole):

  1. Najdeš nejmenší klíč v tom poli, který je >= nově přidávaný klíč. To by mohlo být něco jako:
int i = 0;
while (i < N && pole[i].first < p.first) i++;
  1. pokud i není konec pole, a klíč nalezeného prvku = klíč nově přidávaného prvku, pak upravíš jeho hodnotu a vrátíš 0
  2. jinak posuneš všechny prvky od i doprava o 1. Tedy něco takového:
for (int j = N; j > i; j--) pole[j] = pole[j - 1];
  1. na pozici i vložíš nový prvek
 
Nahoru Odpovědět
11.12.2016 22:47
Avatar
švrčajs
Člen
Avatar
Odpovídá na Drahomír Hanák
švrčajs:13.12.2016 20:40

Díky moc, už to funguje... A chtěl jsem se ještě zeptat, tady beru jako key int :D ale co když tam hodím třeba string ? To musím přetížit v tom Asoc. poli operátor < ? Něco ve stylu, jako že zjistím, jaký je datový typ class T a podle toho to porovnám ?

 
Nahoru Odpovědět
13.12.2016 20:40
Avatar
Odpovídá na švrčajs
Drahomír Hanák:13.12.2016 20:56

Operátor < je pro std::string definovaný už ve standardní knihovně. Jinak se to většinou dělá tak, že ta třída bude mít konstruktor, ve kterém jí předáš porovnávací funkci (ona to ve skutečnosti nemusí být funkce, může to být klidně i objekt, který definuje operator(), a tak se chová jako funkce). Typ téhle porovnávací funkce je většinou další parametr šablony. Může mít výchozí hodnotu třeba std::less<T> (to je pak stejné, jako kdybys ty klíče porovnával operátorem <)

 
Nahoru Odpovědět
13.12.2016 20:56
Avatar
švrčajs
Člen
Avatar
Odpovídá na Drahomír Hanák
švrčajs:13.12.2016 21:01

Ahá, díky moc za vysvětlení ;) a za rady

 
Nahoru Odpovědět
13.12.2016 21:01
Avatar
švrčajs
Člen
Avatar
Odpovídá na Drahomír Hanák
švrčajs:13.12.2016 21:16

A ještě jedna otázka, snad už poslední :D Mám dopsat ještě tuto funkci:
const S * operator [const T &]; Binárním vyhledáváním vyhledá v poli prvek dle zadaného klíče (hodnota klíče je argument operátoru indexu). Byl-li prvek s daným klíčem nalezen, je výsledek operace ukazatel na tento prvek. Pokud nebyl nalezen, operace vrátí nulový ukazatel.

Co se týče bin. vyhledávání, vím o co jde, ale problém mám s deklarací této funkce. Když si hodím za const T& key, abych mohl s předaný argumentem pracovat, tak mi to vyhodí errory, typu: chybí středník atd... S takovýmto zápisem funkce(přetížení operátoru), jsem se ještě nesetkal. Mohl bych se zeptat, jak k tomu přistupovat ? :D

 
Nahoru Odpovědět
13.12.2016 21:16
Avatar
Odpovídá na švrčajs
Drahomír Hanák:13.12.2016 21:27

Operátory se definují podobně jako ostatní metody. Jenom před ně napíšeš slovo operator:

const S* operator[](const T& key) const { ... }
 
Nahoru Odpovědět
13.12.2016 21:27
Avatar
švrčajs
Člen
Avatar
Odpovídá na Drahomír Hanák
švrčajs:13.12.2016 21:56

trošku jsem pokročil, ale zase tam mám něco špatně :D
const S * operator[](const T& key) {
find(key, 0, vrchol);
}

dodefinoval jsem si pomocnou funkci find

S& find(T key, int l, int r) {
if (l > r) return NULL;
int i = (r + l) / 2;
if (pole[i].first == key) return pole[i].second;
if (pole[i].first < key) find(key, l, i - 1);
if (pole[i].first > key) find(key, i + 1, r);
}

ale když pak dám string s = pole.operator[](2);
tak mi to píše error, v c++ jsem naprostý zelenáč, takže mohl bych poprosit o radu ještě ? :D

 
Nahoru Odpovědět
13.12.2016 21:56
Avatar
švrčajs
Člen
Avatar
švrčajs:13.12.2016 22:57

pár errorů jsem se zbavil pomocí přepsání funkce do jedné... Ale teď mi to píše, že nemůžu konvertovat z basic string do const string (chyba C2440)

const S * operator[](const T& key) const{
                int left = 0, right = vrchol;
                int center;
                while (left <= right) {
                        center = (left + right) / 2;
                        if (key == pole[center].first) return pole[center].second;
                        else
                                if (key < pole[center].first) right = center - 1;
                                else left = center + 1;
                }
                return nullptr;
        }
 
Nahoru Odpovědět
13.12.2016 22:57
Avatar
Odpovídá na švrčajs
Drahomír Hanák:14.12.2016 15:04

Ten první return nevrací pointer, ale hodnotu.

 
Nahoru Odpovědět
14.12.2016 15:04
Avatar
švrčajs
Člen
Avatar
Odpovídá na Drahomír Hanák
švrčajs:14.12.2016 15:24

To právě vím, ale když jsem zkusil třeba vrátit

*pole[center].second;

tak to hodí chybu, jediné co nehodilo chybu byla reference, ale to mi vrátí adresu...

&pole[center].second;

nevím, jak to vrátit jako ukazatel, je to pro mě španělská vesnice...

 
Nahoru Odpovědět
14.12.2016 15:24
Avatar
Odpovídá na švrčajs
Drahomír Hanák:14.12.2016 17:07

Operátor & vrátí adresu (pointer) na danou proměnnou. Operátor * naopak vrátí hodnotu, na kterou ukazuje daný pointer. Doporučuju si o pointerech a referencích něco přečíst. Ujisti se, že tomu opravdu rozumíš. Bez toho to totiž půjde hodně těžko.

 
Nahoru Odpovědět
14.12.2016 17:07
Avatar
švrčajs
Člen
Avatar
Odpovídá na Drahomír Hanák
švrčajs:15.12.2016 8:40

Už jsem to pročetl a přišel jsem na to, tak snad bude mé řešení v pořádku. Ještě jednou díky za pomoc ;)

 
Nahoru Odpovědět
15.12.2016 8:40
Avatar
švrčajs
Člen
Avatar
švrčajs:19.12.2016 12:59

Kompletní řešení:

#include "stdafx.h"
#include <iostream>
#include <utility>

using namespace std;

template<class T, class S>
class AsociativniPole {
private:
        int vrchol;
        int iterator;
        int velikost;

        pair<T, S> * pole;

public:
        AsociativniPole(unsigned n) { pole = new pair<T, S>[n]; vrchol = -1; iterator = -1; velikost = n; }

        //nastaví iterátor na první prvek
        bool prvni()
        {
                if (vrchol == -1)
                        return false;
                iterator = 0;
                return true;
        }
        //vrátí počet prvků v poli
        int operator + ()
        {
                return vrchol + 1;
        }

        //vrátí aktuální prvek
        const S& aktualni()
        {
                return pole[iterator].second;
        }

        //vrátí další prvek
        bool dalsi()
        {
                if (iterator == vrchol)
                        return false;
                iterator++;
                return true;
        }

        //vkládání prvků se zatříděním podle velikosti klíče
        int vlozit(const T & first, const S & second)
        {
                vrchol++;
                if (vrchol == velikost) {
                        vrchol--;
                        return -1;
                }
                pair<T, S> p = make_pair(first, second);
                iterator++;
                //nalezení indexu, kam umístit prvek
                int i = 0;
                while (i < vrchol && pole[i].first < p.first) i++;
                if (i != vrchol && !(p.first < pole[i].first || pole[i].first <p.first)) {
                        vrchol--;
                        return 0;
                }

                for (int j = vrchol; j > i; j--) pole[j] = pole[j - 1];
                pole[i] = p;
                return 1;

        }

        //binární vyhledávání
        const S * operator[](const T& key) const {
                int left = 0, right = vrchol;
                int center;
                while (left <= right) {
                        center = (left + right) / 2;
                        if (!(key < pole[center].first || pole[center].first < key)) {
                                return &pole[center].second;
                        }
                        else
                                if (key < pole[center].first) right = center - 1;
                                else left = center + 1;
                }
                return nullptr;
        }
};





int main()
{
        int x = 1;
        string y = "prvek1";
        int x1 = 2;
        string y1 = "prvek2";
        int x3 = -1;
        string y3 = "prvek3";
        int x4 = -1;
        string y4 = "prvek4";


        AsociativniPole<int, string> pole = AsociativniPole<int, string>::AsociativniPole(10);
        int ret;
        ret = pole.vlozit(x1, y1);
        cout << "vlozeni prvku [2, prvek2]: " << ret << endl;
        ret = pole.vlozit(x, y);
        cout << "vlozeni prvku [1, prvek1]: " << ret << endl;
        ret = pole.vlozit(x3, y3);
        cout << "vlozeni prvku [-1, prvek3]: " << ret << endl;
        ret = pole.vlozit(x4, y4);
        cout << "vlozeni prvku [-1, prvek4]: " << ret << endl;

        cout << "pocet prvku v poli: " << +pole << endl;


        bool a = pole.prvni();
        string s = pole.aktualni();

        cout << "prvni prvek: " << pole.aktualni().c_str() << endl;

        bool b = pole.dalsi();
        s = pole.aktualni();
        cout << "druhy prvek: " << pole.aktualni().c_str() << endl;

        bool c = pole.dalsi();
        s = pole.aktualni();
        cout << "treti prvek: " << pole.aktualni().c_str() << endl;

        s = *(pole[-1]);
        cout << "vyhledani prvku s klicem = -1 : " << s.c_str() << endl;
        cout << "stisknutim enter ukoncite aplikaci" << endl;
        getchar();
        return 0;
}
Akceptované řešení
+5 Zkušeností
Řešení problému
 
Nahoru Odpovědět
19.12.2016 12:59
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 23 zpráv z 23.