STL List - Datatype as a pointer object

Question

I'm having a problem using inheritance and the STL list library...

Say, I have an abstract base class with two derived classes (where all comparison operators are defined). The list is declared as

list<StoreItem*> items;

I'm inserting a derived class (of the abstract base class, StoreItem) called either Food or Clothing. I make a new StoreItem pointer that's about to be inserted:

StoreItem* item = new Food(arguments here);

Now, I'm wanting to insert this new item (in order) to the list, and my attempt is this:

list<StoreItem*>::iterator iter;
for (iter = inventory.begin(); iter != inventory.end(); iter++)
{
    if (*item < **iter)
        break; // break out to insert
}

inventory.insert(iter, item);

Is there anything I'm doing wrong? Also, how would I pull the information from the inventory? (ex: Food tempFruit(**iter) using the copy constructor).

Thank you in advance! Have a good day.

Answer 1

You are assuming that the item you are pulling from the list is a Food instance; however, the compiler doesn't know that. When you construct a new instance of Food from an item in the list (an item with apparent type StoreItem), you are trying to call Food::Food(const StoreItem) or something compatible. Why? Because the iterator points to a StoreItem* that could be an instance of a StoreItem object, or an instance of any class derived from StoreItem, such as Food.

As other posters have commented, polymorphism is a key to success. Do you really need to know that the item is a Food? If not, then access the interface shared by all store items (like price, serial-number, etc.). If you need to know something specific about the item, then you can try to infer its type:

Food *food = dynamic_cast<Food*>(*iter);
if (food != NULL) {
   // perform food related logic
   std::cout << "Ingredients: " << food->ingredients() << std::endl;
}
else {
   std::cout << "I can't eat that!" << std::endl;
}

Answer 2

With a comparison function defined for pointers to StoreItem you can shorten your insertion code like so:

bool less_ptr( const StoreItem*& lhs, const StoreItem*& rhs )
{
    return *lhs < *rhs;
}

Insertion:

StoreItem* item = new Food(arguments here);
inventory.insert( std::upper_bound( inventory.begin(), inventory.end(), item, less_ptr ), item);

std::upper_bound (#include <algorithm>) assumes your list is sorted, so this applies if you keep your list sorted at all times.

As to pulling the data back out, there are two things to consider:

1. If you re-create the objects using a copy constructor, you're creating new objects and changing them won't change the objects in the list, so it's better to use pointers
2. You have to split your code path depending on the type of the object stored

You can do this:

Food* foodObj = NULL;
Clothing* clothesObj = NULL;

list<StoreItem *>::iterator it = inventory.find( /* something */ );
StoreItem* item = *it;

item->DoSomethingWithAnyStoreItem(); // It's best to only use such methods

// But if you need something only a derived class has...
foodObj = dynamic_cast<Food*>(item);
clothesObj = dynamic_cast<Clothes*>(item);

if( foodObj != NULL )
{
    foodObj->DoSomethingWithFood();
    Food newFood( *foodObj );
    newFood.DoSomethingWithCopyOfFood();
}
else if( clothesObj != NULL )
{
    clothesObj->DoSomethingWithClothes();
}
else
{
    // It's neither Food, nor Clothes
}

Answer 3

Instead of homebrewing any solution you could resort to boost::ptr_list. It makes life a lot easier if you intend to store pointers in STL like containers. Then all you need is to define operator< for whatever item you are trying to insert. Remember that ptr_list is not intended to be used with shared ownership. To achieve this use std::shared_ptrS in a std::list and specialize std::less for your shared_ptr type.

Answer 4

This will work, provided you've defined StoreItem::operator<, but there's another way that might be a little better. The STL has sorting down cold. You could define < for StoreItem*, then use list<...>::sort().

(And you've probably already thought of defining your own SortedItemList class that handles the sorting internally.)

And yes, tempMovie(**iter) would work, among other ways.

EDIT:

I think I spoke too soon about pulling something out of the inventory. This works:

list<StoreItem *>::iterator citr = items.begin();

Food *fp = dynamic_cast<Food *>(*citr);

Food ff(*fp);

Note that you have to know that this StoreItem* actually points to a Food-- if it points to a Clothing you'll get a segmentation fault or worse. To find out, you could implement your own StoreItem::whatTypeAmI(), or use C++'s run-time type identification:

#include <typeinfo>
...
Food a;
StoreItem *sp = *citr;
if(typeid(*sp)==typeid(a))
{
  // it's a Food
}

(Be aware that you can do a lot with a StoreItem* or StoreItem& without knowing it's type-- polymorphism is your friend.)

Answer 5

If you can define a comparison operator between two pointers to your base class, you can get an ordered collection without writing any other code. Depending on your application you might want a set or a heap, maybe even a map. Here's the idiom to do it... (base is publicly derived from string).

template<>
struct std::less<base*>
{
   bool operator()(const base* lhs, const base* rhs) const
   {
      return *lhs < *rhs;
   }
};

typedef set<base*> S;

int _tmain(int argc, _TCHAR* argv[])
{
    base able(std::string("able"));
    base baker(std::string("baker"));
    base charlie(std::string("charlie"));

    S inventory;
    inventory.insert(&charlie);
    inventory.insert(&able);
    inventory.insert(&baker);

    for (S::iterator i = inventory.begin(); i != inventory.end(); ++i)
        std::cout << **i << endl;
    return 0;
}

output:
able
baker
charlie

It's possible to mill around for a while before discovering this idiom. What's going on is that you're specializing the library template std::less for T=base*; this then slots as if by magic into the default comparator argument for std::set (or other ordered containers).