0

I'm trying to implement a generic class for lists for an embedded device using C++. Such a class will provide methods to update the list, sort the list, filter the list based on some user specified criteria, group the list based on some user specified criteria etc. But there are quite a few varieties of lists I want this generic class to support and each of these varieties can have different display aspects. Example: One variety of list can have strings and floating point numbers in each of its elements. Other variety could have a bitmap, string and special character in each of it's elements. etc.

I wrote down a class with the methods of interest (sort, group, etc). This class has an object of another class (say DisplayAspect) as its member. But the number of member variables and the type of each member variable of class DisplayAspect is unknown. What would be a better way to implement this?

JasonMArcher
  • 14,195
  • 22
  • 56
  • 52
Spottsworth
  • 395
  • 5
  • 12

3 Answers3

4

Why not use the std::list, C++ provides that and it provides all the functionality you mentioned(It is templated class, So it supports all data types you can think of).

Also, there is no point reinventing the wheel as the code you write will almost will never be as efficient as std::list.

In case you still want to reinvent this wheel, You should write a template list class.

Alok Save
  • 202,538
  • 53
  • 430
  • 533
  • On embedded devices STL may not fit in memory (ROM), for instance Atmel AVR microcontrollers have only 4k-128k ROM and up to 8k RAM. – Alexander Verbitsky Aug 16 '11 at 15:15
  • @Roland Taverner: I would even have suggested creating a generic link list in c, with `void*` as the data pointer but the OP specifically demands the list to be `Object Oriented` and `C++`. – Alok Save Aug 16 '11 at 15:17
  • @Roland: That's probably true. But a home-grown generic list that offers the same features is probably not going to be smaller! – Oliver Charlesworth Aug 16 '11 at 15:23
  • @Oli Charlesworth: home-made list class may be implemented without allocators and iterators. – Alexander Verbitsky Aug 16 '11 at 15:37
  • @Roland: True. But if you're not using particular methods, I would hope that the compiler wouldn't generate code for them. – Oliver Charlesworth Aug 16 '11 at 15:41
  • @Oli Charlesworth: you're right but in any case allocator would be instantiated for every list<> instantiation. – Alexander Verbitsky Aug 16 '11 at 16:02
  • @Roland: Allocator objects are zero size. To be specific, every object is at least one byte big, even if it has no data members. But if you use such a class as a base class, then the compiler can optimize it down to zero bytes. Any decent STL will be written to take advantage of this. – john Aug 16 '11 at 17:07
  • @Roland: You said instantiated, which made me think of data. I've never checked but I would expect the default allocater to inline calls to new and delete. I can think of parts of the standard library that would use a great deal of precious memory, but std::list doesn't seem like one of them. – john Aug 16 '11 at 17:14
  • @john: I meant class template instantiation. Sorry if it was unclear. I checked std::allocator implementation in MS VC++ - you're right, it consists only of a few calls. Maybe using STL not as bad idea as I thought. – Alexander Verbitsky Aug 16 '11 at 17:33
0

First, you should probably use std::list as your list, as others have stated. It seems to me that you are having problems more with what to put in the list, however, so I'm focusing on that part of the question.

Since you want to also store multiple bits of information in each element of the list, you will need to create multiple classes, one to store each combination. You don't describe why you are storing mutiple bits of information, but you'd want to use a logical name for each class. So if, for example, you were storing a name and a price (string and a double), you could give the class some name like Product.

You mention creating a class called DisplayAspect.

  • If this is because you want to have one piece of code print all of these lists, then you should use inheritance and polymorphism to accomplish this goal. One way to accomplish that is to make your DisplayAspect class an abstract class with the needed functions (printItem() for example) pure virtual and have each of the classes you created for the combinations of data be subclasses of this DisplayAspect class.
  • If, on the other hand, you created the DisplayAspect class so that you could reuse your list code, you should look into template classes. std::list is an example of a template class and it will hold any type you'd like to put into it and in that case, you could drop your DisplayAspect class.
101100
  • 2,666
  • 23
  • 28
0

Others (e.g., @Als) have already given the obvious, direct, answer to the question you asked. If you really want a linked list, they're undoubtedly correct: std::list is the obvious first choice.

I, however, am going to suggest that you probably don't want a linked list at all. A linked list is only rarely a useful data structure. Given what you've said you want (sorting, grouping), and especially your target (embedded system, so you probably don't have a lot of memory to waste) a linked list probably isn't a very good choice for what you're trying to do. At least right off, it sounds like something closer to an array probably makes a lot more sense.

If you end up (mistakenly) deciding that a linked list really is the right choice, there's a fair chance you only need a singly linked list though. For that, you might want to look at Boost Slist. While it's a little extra work to use (it's intrusive), this will generally have lower overhead, so it's at least not quite a poor of a choice as many generic linked lists.

Community
  • 1
  • 1
Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111