Jump to content

Archived

This topic is now archived and is closed to further replies.

zizou666

Tablica asocjacyjna

Recommended Posts

Witajcie, dzisiaj mialem kolokwium z C++ no i zrobilem prawie wszystko. Nie sprostalem zadaniu polegajacym na napisaniu tablicy asocjacyjnej przy pomocy klasy. Wogole wczesniej nie wiedzialem co to jest ta tablica asocjacyjna, i choc prowadzacy jako tako to wyjasnil, to chyba nie do konca zrozumialem. Wiem ze ma to byc cos na ksztalt tablicy do ktorej odwolujemy sie poprzez unikalne klucze i zawierajacej jakies wartosci. Zadanie trzeba bylo wykonac tak, zeby zarowno klucz jak i wartosc byly typu "string". O ile dla mnie logicznym by bylo uzywanie dla kluczy zmiennej typu int a dla wartosci stringow, to to rozwiazanie bylo jakas abstrakcja. Do tego nie wiedzialem jak to ubrac w klase. Prowadzacy powiedzial, ze mozna to zrealizowac w formie stosu lub tez listy. Mysle ze kolokwium bez tego zalicze, niemniej jednak chcialbym sie dowiedziec jak cos takiego mozna zrealizowac ;)

Wikipedia nie rozwiala niestety moich watpliwosci, dowiedzialem sie tylko, ze w bibliotece standardowej jest rozwiazanie takiej tablicy zawarte.

Link to comment
Share on other sites

Asocjacja czyli powiązanie, w przypadku kontenerów klucza z obiektem. Tego typu pojemniki ułatwiają wyszukiwanie obiektów na podstawie klucza.

Jak zrobić? Potrzebujesz struktury wiążącej klucz z obiektem, czyli klasę pary. Można użyć tej z stl, lub zrobić własną:

template <typename Key, typename T> class Pair
{
   public:
     Pair(const Key & key) : key(key) {
     }

     Pair(const Key & key, const T & t) : key(key), t(t) {
     };

     Key & First() {
        return key;
     }

     T & Second() {
        return t;
     }

     const Key & First() const {
        return key;
     }

     const T & Second() const {
        return t;
     }

   private:
     Key key;
     T t;
};

Drugim elementem jest już sam kontener:

class TablicaAsjocacyjna
{
  typename std::vector<Pair<std::string, std::string > > Data;

  public:
    std::string * operator [] (const std::string & key) {

      Data::iterator it, end;

      for (it = data.begin(); end != it; ++it) {
        if (0 == it->First().compare(key)) {
          return & ( it->Second() );
        }
      }
      Pair<std::string, std::string> pair(key);
      data.push_back(pair);
      return & ( data.back() );
    }

  private:
     Data data;
};

Brakuje tu kilku elementów, ale myślę, że ideę rozwiązania przedstawiłem.

W stl masz już gotowy pojemnik asocjacyjny std::map. Jest oparty o drzewa czarno czerwone, co zapewnia mu dość wydajne wyszukiwanie (przeszukanie tablicy tak jak ja to tutaj zrobiłem jest bardzo powolnym rozwiązaniem).

Link to comment
Share on other sites



  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...