Tablica asocjacyjna

[zizou666]

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.

[[Ekspert] Mormegil]

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).