ArrayList für drei verschiedene Typen

[uwerothfeld]

Hallo zusammen,

ich habe mal eine Frage. Ich brauche für drei verschiedene Datentypen eine ArrayList. Nach Möglichkeit noch verschiedene Länge. Großes Problem zusätzlich: malloc darf/kann nicht verwendet werden. Ich will nun eigentlich nicht drei mal das selbe schreiben, vielleicht habt ihr ja einen Typ?

mfg
uwe

[_matze]

Was ist denn ArrayList? Ist das nicht .NET?

[simon.gysi]

_matze schrieb:

Was ist denn ArrayList? Ist das nicht .NET?

Gibts bei Java und .NET...
Also völlig falsches Unterforum...
Simon

[uwerothfeld]

hallo,

na einfach ein Array[], für das ich add(), get(), remove(), ... definiere.
Damit ich nicht tausendmal zählen muß und immer schauen muß, wo ich bin.

Also ich brauch quasi ne Lösung wie ich eine Art typedef DataType für drei Typen anlege, welche ich dann ala DataType1 list1[size1], DataType2 list2[size2], ... verwenden kann. Die Funktionen will ich aber nur einmal implementieren, da ich Codesize sparen muß

mfg

edit: Ich will halt sowas machen wie in http://alpha.uhasselt.be/~gjb/MIT-C/oef/ --> array-list, aber für drei verschiedene Datentypen

[Gast]

Vielleicht was mit ner Union basteln?

[uwerothfeld]

hi,

union? da bekomme ich doch ne structur, welche die größe der größten teilkomponente annimmt, oder? das ist aber doch doof, wenn ich in der liste folgende dinge speichern möchte:

- uint8_t
- (uint8_t,uint8_t)
- (uint8_t,uint32_t)

noch andere tips? oder sehe ich bloß gerade die lösung nicht?

uwe

[-fricky-]

uwerothfeld schrieb:

union? da bekomme ich doch ne structur, welche die größe der größten teilkomponente annimmt, oder?

du könntest 'ne struct nehmen, die einen eintrag für den typ enthält

struct variant
{
  int type;   // <-- hier hinein kommt, welcher typ das gerade ist
  union alltypes
  {
     int8_t int8;
     int32_t int32;
     ...
  } alltypes; 
};

das hat vorteile, weil die struct immer gleich gross ist. mit verschieden grossen structs wäre das einfügen und löschen viel komplizierter. sowas lohnt sich nur, wenn man echt wenig RAM hat.

[Xantus]

uwerothfeld schrieb:

oder sehe ich bloß gerade die lösung nicht?

Du scheinst dir unter union zwar das richtige vorzustellen...aber Tims Vorschlag ist wohl gerade das sinnvollste. Er meint eher so etwas:

/* note: ohne jegliche fehlerbehandlung auf null-pointer */

#include <stdio.h>

/* aufzaehlung um zu wissen,
   welcher typ gerade verwendet wird */
typedef enum {
    INT_TYPE,
    CHAR_TYPE,
    DOUBLE_TYPE
} Type;

typedef struct {
    /* die union ... */
    union {
        int int_val;
        char char_val;
        double double_val;
    };

    /* speichert den gerade verwendeteten typ */
    Type what;
} DataType;

/* hilfsfunktionen, die das setzten des wertes und 
 * der typ-variable automatisieren */
void set_int(DataType* dt, int i)
{
    dt->int_val = i;
    dt->what = INT_TYPE;
}

void set_char(DataType* dt, char c)
{
    dt->char_val = c;
    dt->what = CHAR_TYPE;
}

void set_double(DataType* dt, double d)
{
    dt->double_val = d;
    dt->what = DOUBLE_TYPE;
}

/* zum test => ausgabe */
void print_value(DataType* dt)
{
    switch(dt->what) {
    case INT_TYPE:
        printf("%d\n", dt->int_val);
        break;
    case CHAR_TYPE:
        printf("%c\n", dt->char_val);
        break;
    case DOUBLE_TYPE:
        printf("%f\n", dt->double_val);
        break;
    }
}

int main(void)
{
    DataType dt;

    set_int(&dt, 42);
    print_value(&dt);

    set_char(&dt, 'c');
    print_value(&dt);

    set_double(&dt, 123.4567);
    print_value(&dt);

    return 0;
}

jetzt hast du schonmal einen "polymorphen" Datentyp DataType in C gebaut, um den du jetzt eine Liste bauen kannst bzw. womit du jetzt Arrays bilden kannst.

[besserwisser]

wie wäre es damit, nur pointer zu speichern? void* ist dein freund. willst du an der größe des source codes sparen oder an der größe des binären codes?
die für c sauberste und wohl leserlichste version wäre, es per void* zu machen.
noch ein kommentar zu arraylist: arrays und listen sind zwei verschiedene datentypen, die nur wenig miteinander zu tun haben. was du brauchst, ist ein baum.

[supertux]

besserwisser schrieb:

wie wäre es damit, nur pointer zu speichern? void* ist dein freund. willst du an der größe des source codes sparen oder an der größe des binären codes?
die für c sauberste und wohl leserlichste version wäre, es per void* zu machen.
noch ein kommentar zu arraylist: arrays und listen sind zwei verschiedene datentypen, die nur wenig miteinander zu tun haben. was du brauchst, ist ein baum.

sicherlich ist der Aufwand mit void-Pointern geringer, aber ich sehe in der Handhabung mehr Nachteile: es ist alles nicht type-safe, wenn du aus einer Funktion eine Liste (oder Array meinetwegen) bekommst, musst du von Anfang an kennen, welches Datentype hinter dem void* an der 0. Stelle, an der 1. Stellen, usw. steckt. Was ist, wenn diese Festlegung erst zur Laufzeit festgestellt werden kann? Dann müsstest du separt eine weitere Liste führen, wo du nachschauen muss, um welches Datentyp es sich handelt. Das finde ich gefährlicher, weil man selbst als erfahrener Pointer-Jonglier viele Fehler machen kann.

Deswegen ist eine Lösung wie die von Xantus eher die bessere, weil du zur jedem Zeitpunkt immer das genaue Datentyp kennst. Ein bisschen aufwändiger aber im Grunde deutlich sicherer als nur mit void-Pointern zu arbeiten.

[-fricky-]

besserwisser schrieb:

was du brauchst, ist ein baum.

um sich aufzuhängen? oder wie?

[besserwisser]

@supertux
type-safe ist es mit der lösung von xantos ebenso wenig. er hat nämlich klugerweise auf die get methoden verzichtet. wieso wohl? wenn du nicht weißt, welchen typs ein element der liste ist, weißt du auch nicht, welche get-funktion du aufrufen musst. get_int, get_char, get_double? dsa ist vergleichbar mit dem casten eines void* pointers.

jetzt kommt möglicherweise das argument: "aber das speicher ich ja dazu...". stimmt. das kann ich bei einem void* pointer auch machen.

die void* methode spart außerdem code, da ich keine drei verschiedenen funktionen für alle drei datentypen brauche (get, set, print, ...).

hier, wie so oft in diesem forum, idt das problem, dass der threadersteller nicht angibt, für was er das braucht, was er will. damit kann ich schwer etwas über die sinnhaftigkeit einer solchen liste aussagen. die thread ersteller sollten immer den kontext ihrer fragen mit angeben.

[supertux]

besserwisser schrieb:

@supertux
type-safe ist es mit der lösung von xantos ebenso wenig. er hat nämlich klugerweise auf die get methoden verzichtet. wieso wohl? wenn du nicht weißt, welchen typs ein element der liste ist, weißt du auch nicht, welche get-funktion du aufrufen musst. get_int, get_char, get_double? dsa ist vergleichbar mit dem casten eines void* pointers.

ich hab in meinem Post geschrieben, dass xantos Lösung nicht 100% type-safe wäre sondern, dass sie sicherer als die reine void*-Lösung ist. Das ist eine Stärke und gleichzeitig eine Schwäche in C. Ich hab in meiner Arbeit sowohl mit void*-Listen als auch mit xantos-ähnlichen Listen zu tun und ich weiß, wann welche einen Vorteil hat.

Mit xantos Listen ist es generell auch nicht gewährleistet, dass man die richtige Funktion nimmt, aber du kannst wenigsten mit der Abfrage von DataTyp->what aufs Datentyp kommen, wie willst du das nur mit einem void-Zeiger machen? In beiden Fällen ist ein 'what' Member am sinvollsten.

Der Ansatz ist auch nicht der falsche, es gibt mehrere Bibliotheken, die sowas implementieren. GTK+ macht viel davon Gebrauch (sogar eine sehr ähnliche Implementierung) und dort funktioniert es auch zuverlässig.

Wenn du nur mit void-Zeigern arbeitest, musst du meisten immer vorher Speicher reservieren (und später ans Freigeben denken). Bei dem union ist das nicht der Fall; vor allem wenn du nur mit numerischen Listen (int, double, floats, usw) arbeitet, fände ich lästig für jeden Wert erstmal Speicher anfordern zu müssen anstatt set_int(liste, value), set_float usw. zu benutzen.

[Xantus]

1. mit u - Xantus!
2. habe ich denn soviel Zeit, getter- und setter- Funktionen zu schreiben? Denkanstöße sind nicht mit vollständigen Lösungen bzw. Implementationen gleichzusetzen, dafür reicht wieder die Zeit noch ist es schön, so langen Code zu pasten, nur um nochmals 3 get-Funktionen zu haben, deren Funktionsweise man sich sowieso denken kann.

[uwerothfeld]

Hallo Zusammen,

also ich will dann mal wieder bissl Licht in das Dunkel bringen ;). Worum geht es? Also Kontext mäßig geht es um Sensorknoten. Dabei befinde ich mich in einer Umgebung in der wir folgende Bedingungen zu berücksichtigen haben:

1. der RAM ist extrem schmal bemessen
2. der ROM ist extrem schmal bemessen
3. soetwas wie malloc existiert nicht
4. der Prozessor ist klein und langsam (8bit bei 20Mhz oder so)
5. Energie ist knapp auf dem Knoten, sprich viel rechnen ist auch doof

benötigt werden die Listen jeweils nur zum temporären Zwischenspeichern von Werten. Also die Liste wird gefüllt, dann der erste Wert der List genommen und bearbeitet, irgendwann erhält man ein Ergebnis, dies wird sich gemerkt und das Ergebnis für den zweiten Wert auf der Liste gebildet. Und so weiter. Soviel zum Kontext. Nun will man also eine kleine, feine Lösung, mit der man dennoch wenigstens bissl arbeiten kann. Ich habe mich daher für die union Variante entschieden, da ich nicht so richtig weiß, wie ich bei void* meine Elemente dauerhaft auf den Stack bekomme. So, wie ich es jetzt habe, ist die Liste einfach global, thats it. Nun meine Frage, könnt ihr euch mal meine Lösung anschauen und sagen ob dies so ok ist, bzw. was sich verbessern lässt, bzgl. der oben genannten Punkte? Hier mein Code:

Datei data_type.h:

#ifndef _DATA_TYPE_H
#define	_DATA_TYPE_H

#ifdef	__cplusplus
extern "C" {
#endif

    typedef enum {
        SEL_VAR,
        AGG_FUNC,
        SET_PAIR
    } DATA_TYPE;

    typedef uint8_t sel_var;

    typedef struct {
        uint8_t func_nr;
        uint8_t var_nr;
    } agg_fun;

    typedef struct {
        uint8_t var_nr;
        uint32_t value;
    } set_pair;

    typedef struct {
        DATA_TYPE type;

        union {
            sel_var select;
            agg_fun agg;
            set_pair set;
        };
    } elem;

#ifdef	__cplusplus
}
#endif

#endif	/* _DATA_TYPE_H */

Datei array_list.h

#ifndef _ARRAYLIST_H
#define	_ARRAYLIST_H

#ifdef	__cplusplus
extern "C" {
#endif

    /**
     * This file defines a simple array list.
     * Its offers methods to add, remove and read elements from the 
     * list.
     */

#include "data_type.h"
#include <stdlib.h>

#define MAXLENGTH 5 
#define FIRSTPOS 0 
#define OVERFLOW 0xFF

    /**
     * Defines the list struct.
     */
    typedef struct {
        elem content[MAXLENGTH];
        int last;
    } List;

    /**
     * clears the list
     */
    void clearList(List *l);

    /**
     * adds elem e to the end of the list
     */
    void addElem(List *l, elem e);

    /**
     * returns the element at index i from list
     */
    elem* getElem(List *l, uint8_t i);

    /**
     * removes the element at the given index from the list
     */
    void removeElem(List *l, uint8_t index);

    /**
     * returns the size of the list
     */
    uint8_t listSize(List* l);

#ifdef	__cplusplus
}
#endif

#endif	/* _ARRAYLIST_H */

Datei array_list.c:

#include "array_list.h" 

/* 
 * File:   array_list.c
 *
 * Created on 20. August 2008, 13:08
 */

/**
 * clears the list
 */
void clearList(List *l) {
    l->last = FIRSTPOS;
}//End clear

/**
 * adds elem e to the end of the list
 */
void addElem(List *l, elem e) {

    if (l->last < MAXLENGTH) {
        l->content[l->last] = e;
        l->last++;
    }//End if
}//End add

/**
 * returns the element at index i from list
 */
elem* getElem(List *l, uint8_t i) {

    if (i < l->last) {
        return &l->content[i];
    }//End if

    return NULL;

}//End get

/**
 * removes the element at the given index from the list
 */
void removeElem(List *l, uint8_t index) {

    uint8_t i;

    for (i = index; i < l->last && i < MAXLENGTH; i++) {
        l->content[i] = l->content[i + 1];
    }//End for

    l->last--;
    if (l->last == OVERFLOW)
        l->last = FIRSTPOS;

    if (l->last >= MAXLENGTH)
        l->last = MAXLENGTH - 1;
}//End remove

/**
 * returns the size of the list
 */
uint8_t listSize(List* l) {
    return l->last;
}//End size

Also mich interessiert dazu eure Meinung. Ist dies ok so oder sollte man was ändern, etc. Nun noch ne weitere Frage, wie kann ich nun die MAXLENGTH variabel machen? Weil ich wie in meinen ersten Post schon sagte, die Liste insgesamt dreimal habe. Nun wäre es toll wenn ich für Liste 1 eine MAXLENGTH_1 definieren könnte und so weiter. List benutze ich als Bezeichnung für diese Struktur, da es sich um eine Datenstruktur mit einer endlichen Anzahl von Elementen handelt. Die Definition über Pointer halte ich nicht für zwingend, auch wenn sicherlich einige da anderer Meinung sind. Typsicherheit ist hingegen eine von mir persönlich als sehr angenehm empfundenen Eigenschaft, welche aber in meiner Lösung nicht gegeben ist. Da lag der Fokus mehr auf Handharbarkeit. Das mit dem Baum verstehe ich nicht, da eine Liste im Gegensatz zu einem Baum immer eine Totalordnung ist, ein Baum jedoch "nur" eine Halbordung, auch wenn er zu einer Liste degenerieren kann. Ha. Nun ist aber gut. Berichtigt mich, wenn ich mich irre.

Gruß und schon mal dank,
Uwe

[besserwisser]

@supertux
jeder, wie er s haben will.

@uwerothfeld
mal eine ganz blöde frage: wieso machst du das alles so ultra kompliziert? was du brauchst ist keine liste sondern ein simples array.

wenn man mal annimmt, dass deine zahlen messwerte sind, bekommst du von einem interrupt handler oder durch polling bei jedem durchlauf einen wert.

du allokierst zur compilierzeit derzeit einfach die maximale menge an werten. das ist schon mal ok, wenn du kein malloc hast. die frage ist nur, wieso du das über so einen komischen wrapper machen willst? es wär doch viel einfacher, das mit einem simplen pointer zu machen. das is schneller und braucht so gut wie gar keinen code.

du nimmst einen pointer auf elem, den du mit "content" initialisierst. jeden neuen messwert schreibst du an die stelle, auf die der pointer zeigt und inkrementierst diesen pointer danach.

zum berechnen der nicht-temporären werte machst du genau das gleiche und gehst somit deine "liste", die einfach nur ein array ist, durch.

es ist löblich, dass du dir viele gedanken machst, aber hier denkst du eindeutig viel zu kompliziert.

[uwerothfeld]

Morgen :),

also

besserwisser schrieb:

@uwerothfeld
mal eine ganz blöde frage: wieso machst du das alles so ultra kompliziert? was du brauchst ist keine liste sondern ein simples array.

Echt? Findest du es kompliziert? Finde ich eigentlich nicht, aber ok. Vielleicht liegt es daran, dass ich eigentlich eher aus der OO Ecke komme. Zugriffe direkt auf Datenstrukturen sind daher für mich etwas böses ;).

besserwisser schrieb:

wenn man mal annimmt, dass deine zahlen messwerte sind, bekommst du von einem interrupt handler oder durch polling bei jedem durchlauf einen wert.
du allokierst zur compilierzeit derzeit einfach die maximale menge an werten. das ist schon mal ok, wenn du kein malloc hast. die frage ist nur, wieso du das über so einen komischen wrapper machen willst?

Diese Annahme ist nicht ganz richtig. Es sind zwar quasi Messwerte, diese werden allerdings in einem Rutsch in die Liste geschrieben. Die Abarbeitung dieser Liste erfolgt dann allerdings durch verschiedene Funktionen und unterschiedliche Zeiten. Daher der Wrapper, da ich mir keine Gedanken machen wollte, wann wie und wo ich Zuzugreifen habe und ob eigentlich noch was da ist. Also Funktion A füllt die Liste und anschließend werden (hier nicht weiter wichtig) die Funktionen B und C aufgerufen, z.B. C-B-C-C-B-B-C. Nun will ich in B und C halt relativ einfach auf die Liste zugreifen können, ohne derren interna zu kennen. Daher soll mir die Liste sagen: Ich bin leer.

besserwisser schrieb:

du nimmst einen pointer auf elem, den du mit "content" initialisierst. jeden neuen messwert schreibst du an die stelle, auf die der pointer zeigt und inkrementierst diesen pointer danach.

Wie meinst das genau? Ich glaub dafür ist es noch zu früh für mich.

Im Moment ist die "Liste" in der Tat nur ein Array, richtig. Ich hätte gerne eher etwas in Richtung echter verketteter Liste gehabt, weiß aber nicht wie und ob überhaupt so etwas statisch geht, ohne Speicher zu verschwenden beim Elemente entfernen.

Gruß

[supertux]

uwerothfeld schrieb:

besserwisser schrieb:

du nimmst einen pointer auf elem, den du mit "content" initialisierst. jeden neuen messwert schreibst du an die stelle, auf die der pointer zeigt und inkrementierst diesen pointer danach.

Wie meinst das genau? Ich glaub dafür ist es noch zu früh für mich.

Im Moment ist die "Liste" in der Tat nur ein Array, richtig. Ich hätte gerne eher etwas in Richtung echter verketteter Liste gehabt, weiß aber nicht wie und ob überhaupt so etwas statisch geht, ohne Speicher zu verschwenden beim Elemente entfernen.

da du kein malloc hast (und wahrscheinlich keine sonstige Speicherverwaltungsfunktion hast, ist es schwer Speicher zur Laufzeit zu reservieren, deswegen reservierst zu zur Compilezeit den Speicher und benutzt diesen. Am einfachsten ist es dann mit einem Array. Das Problem mit dem obigen Ansatz ist es, wenn du Daten löscht, hinzufügst, wieder löscht, usw, dann fragmentiert sich der Speicher und müsstest defrgmentieren, damit du keinen Buffer Ovreflow erzeugst.

Ich hatte dieses Problem mit einem selbst geschriebenen Mikrokernel, da habe ich es so gelöst:

ich hab mir schnell eine Double-Linked-List Struktur (struct DLList) geschrieben und global ein Array vom Typ struct DLList angelegt. Dann habe ich so initialisiert, dass für 1 <= i <= max-2 gilt

array[i].next = &array[i+1];

und sonst

array[0].prev = &array[max - 1];
array[max - 1].next = NULL;

Dann hab ich 2 Zeiger deklariert, free_space = &array[0]; und list = NULL . Ich denke, jetzt siehst du, wie das funktioniert. Mit einer geeigneter Funktion kannst du immer das erste freie Feld über mem = &free_space[0] bekommen und dann mit list[curr_num_elemnts-1].next = mem; in die aktuelle List bekommen. Dann weißt du, das nächste freie Element ist mem.next und kannst somit free_space wieder anpassen:

free_space = mem.next;
mem.next = NULL; /* weil das letzte Element der 'list'-Liste,
  die Information auf das nächste freie Feld nicht mehr gebraucht,
  weil free_space auf das richtige Feld hat */

Indem du die next und prev Elemete geschickt setzt, kannst du mit 2 Pointern sowohl die freien Felder als auch die verwendeten Felder verwalten, ohne den Speicher defragmentieren zu müssen. Wenn du mal ein Bsp willst oder so, dann schick mir ne PM (persönliche Nachricht) oder Mail übers Board.

[TheTester]

Die Erklärung von Supertux erinnert mich an eine "Freispeicherliste" für homogene Elemente. Eine knappe und einleuchtende Erklärung findet sich in einer Praktikumsaufgabe unter folgendem Link http://www.cs.hm.edu/~koehler/alg_dat/alg_dat_prakt_2008/p1_ss08.pdf

Weitere Quellen welche die Idee demonstrieren wären "Introduction do Algorithms (Cormen et. al)" dort findet sich etwas unter "free list". Und Knuth spricht in seinem ersten Buch (Fundamental Algorithms) von einer "available space list" um die grundlegende Idee zu verdeutlichen.

[Tippgeber]

Wollte gerade vorschlagen, dass eine ArrayList wie man sie zumindest derzeit im Sprachgebrauch nutzt kein normales Array ist, das einfach nur wächst, sondern tatsächlich einige Listen-Eigenschaften besitzt.
Bzw. diese Sichtweise ist schlecht, es lässt sich besser formulieren als eine Liste mit einigen Array-Eigenschaften.

Denn das meiste was eine Liste kann, kann man mit einem Array auch und das Löschen und Einfügen in der Mitte geht bei einem Array halt nicht in konstanter Zeit.
Daher ist es besser wenn man von einer Liste mit Array-Eigenschaften spricht. Man bekommt dadurch nämlich eine Liste mit O(1) Zugriff auf jedes Element. Dafür wird das Löschen/Einfügen in der Mitte allerdings nicht mehr in O(1) möglich.
Über die genauen Aufwände kann man i.A. nichts genaues sagen, das kommt auf die Implementierung drauf an. Die Java-Leute haben sich da recht viel Mühe gegeben.