Linked list, but not like that

  • I want to use a linked list structure to link structures in multiple ways.

    The structures are loaded from a(n XML) file, and simply allocated in the order they are loaded.
    Each structure may then belong to various lists as specified by tags in the XML.

    I'm imagining each structure having an array of link structures, one element for each list it is a part of.

    Is there something like this in Qt or am I in a "roll your own" situation?
    I've hunted around and not found anything so I'm guessing it's the latter, but I thought I'd ask, just in case.


  • Sounds like you want a very flexible solution if you want to define your datastructure like that in XML.
    I think you are clearly in the 'write it yourself' catagory ;)

  • Is your XML linear or a tree-like structure? You can easily build trees by deriving from QObject, which is one of the most basic building blocks of Qt.

    If it is a linear structure with objects of different type, it is still a good idea to make your classes hierarchy QObject derived, store a QList of pointers to the actual instances and use polymorphism to traverse the list. The linked list is somewhat slower, and only makes sense to use if you have a lot of inserting in the middle, which you won't have since you will be parsing an XML.

  • Thanks both.

    utcenter is right on the money. Of course (doh!) I just let it build one list and then set up lists (in the same pass) using pointers to the existing structures. I was getting all overcomplicated in my head :(

  • Keep in mind QObject has its copy constructor disabled because you shouldn't really copy a QObject, so you are pretty much forced to put pointers to QObjects in the actual list.

    But you may not need to derive from QObject, it is useful for object lifetime and memory management and for signals and slots, but you could go away with something cheaper and lighter.

  • Moderators

    QObject might also be too heavy if you do not need its special features like signals/slots, etc.

  • As a rule of thumb I'd say that a collection of a 1000 items or less, the QObject overhead is not all that relevant. That amount goes down a bit when you are in very memory restricted environment (like an embedded device).
    So, while I agree with Tobias it might be too heavy, for many usages its Ok.

  • I never really checked how big QObject actually is. The private dynamically allocated data that is, according to sizeof it is fairly compact, but it doesn't catch everything.

    Anyway it is pretty straightforward to implement a custom tree structure, only two members are really needed - the parent node and a list of children nodes. It can even be brought down further, if the hierarchy is only one way the parent node can be removed while preserving the ability to traverse the tree recursively, but having the children being unaware of the parent has its limitations.

  • Or, you just take one of the already available alternatives. I have used "this one": successfully in the past.

  • Ok, it's been a while, sorry.
    I understand, at least in principle, the different types of structures, however that's not the issue.

    They key phrase in the initial question was "in multiple ways".
    I want to build one set of data and then thread the items through multiple lists.

    It's actually for displaying a list of musical instruments.
    The list should be switchable to display different groups of instruments; for example, orchestral instruments, jazz instruments, brass band, &tc &tc.
    Each instrument may (!) be on many different lists.

    Each instrument needs quite a large structure so I really only want one instance for each instrument.

    At this point I'm thinking I will build multiple qlists of pointers to my instrument data structures.
    Any thoughts?

  • Lifetime Qt Champion


    Have you given a thought about the model/view paradigm ? Sounds like you have a set of instruments which would be your model data and over that you'll have proxy models to sort/filter your instruments (then no need to modify the model data) and the views (probably custom) to show what you want.

  • No, I hadn't thought of model/view for this.
    I'm contributing to a (largish) piece of open source s/w, and this is a very small part of it. I think I'd make a big splash in the existing code by implementing something like that... I'll have a look, though. Thanks.

Log in to reply

Looks like your connection to Qt Forum was lost, please wait while we try to reconnect.