Storing Items In an Array of Custom Lists

[ElusiveTau]

I'm working with code that implements its own templated CusList data structure (a variant of linked list) that is dynamically allocated. CusList contains additional members like find(T item, int *loc) which finds the item in the list and returns its position, a 0-based index value. It also has members you'd expect: addToHead(T item), addToTail(T item).

#include <vector> 

// Base type
struct Foo { 
   string id; // Any string
   int type; // 0 .. 3
   Foo(string id = "", int type = 0) : id(id), type(type) {}
};

// Derived type
struct Fooz : Foo { // Some additional members }

...
// Need to populate this map 
CusList<Foo> fooMap[3]; // Index: 0 maps to all Foos with Foo.type = 0, etc. 

// Code snippet under question
for (int i = 0; i < BigBox.size(); i++)
{
   Fooz fz; 
   Foo *pFoo = &fz;
   // BigBox.getFoo returns a varying number of initialized Fooz object. 
   bool success = BigBox.getFoo(pFoo); 
   ... 
   // I want to do something like this but fz is local. 
   fooMap[fz.type].addToTail(fz); 
}

Outside the for-loop, will fooMap contain garbage since fz were local values?
If so, how should I declare fz?

Edited:

I drew up an example (substituting CusList for vector since they're analogous) and it seems to work. But is it working because the Foo values are static?

#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using std::vector;
using std::string;
using std::stringstream;
using std::cout;

struct Foo
{
    string id;
    int type; // 0 ... 2
    Foo(string id = "", int type = 0) : id(id), type(type) {}

    // Returns string representation of Foo
    string ToString()
    {
        stringstream ss;
        ss << "Foo(" << id << "," << type << ", " << std::hex << this << ")";
        return ss.str();
    }
};

struct Fooz : Foo {};

// Mock of the possible return values for BigBox.getFoo()
struct BigBox
{
    bool getFoo(Foo *fillMe) { *fillMe = items[idx++]; return true; }
    static int size() { return items.size(); }
    static void PrintStaticFooAddresses()
    {
        cout << "Addresses\n";
        for (int i = 0; i < items.size(); i++)
        {
            cout << "\tFoo(" << items[i].id << "," << items[i].type << ") @ Address: " << std::hex << &items[i] << "\n";
        }
    }
private:
    static int idx; 
    static vector<Foo> items;
};

vector<Foo> BigBox::items{
    Foo("Zero", 0), Foo("ZEro", 0), Foo("ZERo",0), Foo("ZERO",0), 
    Foo("One", 1), 
    Foo("Two", 2), Foo("TWo", 2)
};
int BigBox::idx = 0;
BigBox theBigBox; // Singleton

int main()
{
    // Show us where Foo objects are allocated
    BigBox::PrintStaticFooAddresses();

    // Map to fill 
    vector<Foo> fooMap[3];

    // Code snippet in question
    for (int i = 0; i < BigBox::size(); i++)
    {
        Fooz fz;
        Foo *pFoo = &fz;
        bool success = theBigBox.getFoo(pFoo);

        fooMap[pFoo->type].push_back(fz); // analogous to .addToTail()
    }

    // Did it work?
    for (int type = 0; type < 3; type++)
    {
        cout << "Type[" << type << "]: \n";
        for (int i = 0; i < fooMap[type].size(); i++)
        {
            cout << "\t" << fooMap[type][i].ToString() << "\n";
        }
    }
}

Output

Addresses
	Foo(Zero,0) @ Address: 0x2604340
	Foo(ZEro,0) @ Address: 0x2604350
	Foo(ZERo,0) @ Address: 0x2604360
	Foo(ZERO,0) @ Address: 0x2604370
	Foo(One,1) @ Address: 0x2604380
	Foo(Two,2) @ Address: 0x2604390
	Foo(TWo,2) @ Address: 0x26043a0
Type[0]: 
	Foo(Zero,0, 0x2604410)
	Foo(ZEro,0, 0x2604420)
	Foo(ZERo,0, 0x2604430)
	Foo(ZERO,0, 0x2604440)
Type[1]: 
	Foo(One,1, 0x26043c0)
Type[2]: 
	Foo(Two,2, 0x26043e0)
	Foo(TWo,2, 0x26043f0)

[Peter87]

Outside the for-loop, will fooMap contain garbage since fz were local values?

It depends on how it is implemented. Does the CusList store copies or pointers of the the objects that are passed to addToHead and addToTail? If it stores copies, like std::vector does, then it doesn't matter how fz was created.

If CusList store pointers then you would have to change the function signatures so that the objects are passed by reference (or pointer)

addToHead(T& item)
addToTail(T& item)

otherwise you would run into problems, because the parameter would be a copy of the object that was passed as argument, and you don't want to store a pointer to such a local copy because it would not exist after the function has ended.

Even if you store copies it might be a good idea to pass by reference to avoid unnecessary copies being created when passing the arguments.

[Peter87]

I drew up an example (substituting CusList for vector since they're analogous) and it seems to work. But is it working because the Foo values are static?

The code seems valid, but is it doing what you want? I don't know ...

Note that on line 70 fz, BigBox::items[BigBox::idx - 1] and fooMap[pFoo->type].back() all refer to different objects.

Also note that there is no need to create a pointer variable here

Fooz fz;
Foo *pFoo = &fz;
bool success = theBigBox.getFoo(pFoo);

Instead you could pass the address of fz directly as argument to the function

Fooz fz;
bool success = theBigBox.getFoo(&fz);

And later use fz. instead of pFoo->.

fooMap[fz.type].push_back(fz);

[ElusiveTau]

Peter87 wrote:

It depends on how it is implemented. Does the CusList store copies or pointers of the the objects that are passed to addToHead and addToTail?

So CustList<T> stores pointers to the template class ListItem<T> like so:

template <typename T> class ListItem
{
   T item; // Stores the underlying value
   ListItem<T> *prevItem;
   ListItem<T> *nextItem;
   ListItem(T storeMe) : item(storeMe), prevItem(0), nextItem(0) {}
}

template <typename T> class CustList 
{
   ListItem<T> *listHead; 
   ListItem<T> *listTail; 
   ...
   bool addToHead(T item) {...} // Returns if add was successful
   bool addToTail(T item) {...} 
   bool getHead(T &itemAtHead) { return itemAtHead = listHead->item; }
}

So because addToHead takes a T item. The underlying value that is stored in a ListItem has to be a copy right?

So regarding my original question:

   Fooz fz; 
   ...
   fooMap[fz.type].addToTail(fz);

Should be safe, and the safeness of the copies depend on how Fooz's copy constructor is implemented, I would imagine.

Regarding your advice:

Peter87 wrote:

Even if you store copies it might be a good idea to pass by reference to avoid unnecessary copies being created when passing the arguments.

I agree but for what I'm doing, asking to modify this datastructure is not possible. I either use it or have find something else.

[mbozzi]

But is it working because the Foo values are static?

There aren't any objects with type Foo that have static storage duration. (The contents of a static vector still have dynamic storage duration.)

This line
bool success = theBigBox.getFoo(pFoo);
Slices *pFoo. This is because its dynamic type is Fooz but BigBox::getFoo treats it as a Foo.

Here's a rough example of how this object slicing could cause problems:

#include <cassert>

class A 
{
  int x;  
public:
  explicit A(int x): x{x} {}
  
  int get_x() const noexcept { return x; }
  void set_x(int new_x) { x = new_x; }
}; 

class B: public A 
{ // B maintains a class invariant: x + y should always sum to 10.  
  // TODO: avoid integer overflow.
  int y;  
public:
  explicit B(int x): A(x) { set_y(); }
  
  void set_x(int new_x) 
  { 
    A::set_x(new_x); 
    B::set_y();
  }
  
  int get_y() const noexcept { return y; }

private:  
  void set_y() { y = 10 - get_x(); }
};

void get_a(A* pa) { static A my_a(5); *pa = my_a; } 

int main()
{ 
  B b{4};
  assert(b.get_x() + b.get_y() == 10);
  get_a(&b); 
  assert(b.get_x() + b.get_y() != 10); // invariant is violated, b is invalid
}

Also [code line=20] is supposed to be [code firstline=20].

[Peter87]

ElusiveTau wrote:

So because addToHead takes a T item. The underlying value that is stored in a ListItem has to be a copy right?

Yes, that's right.

ElusiveTa wrote:

... Should be safe, and the safeness of the copies depend on how Fooz's copy constructor is implemented, I would imagine.

Yes, except for the slicing problem that mbozzi mentioned.

[markyrocks]

I think that you're over complicating some things. I understand where you're going with all this. When you get into creating a container you're going to have to start creating some pointers. It's hard for me to explain it so I'll just post a link to a piece of code I wrote that is working halfway decently to kinda show what I needed to do. You're basically making connected nodes and this example shows how to grow a string of nodes from the rear and traverse them in order. It's far from complete but dips your toe in the water. https://pastebin.com/Gn5EVE80

The only other thing I can add to this is checkout type_info and type_index headers. I really like this problem and getting variant data in is the easy part, getting it back out to a usable state is the hard part. I was playing around with generating a type_index::hash with limited success. They don't really want you digging in there too much bc it is not user-friendly at all.

[mbozzi]

I really like this problem and getting variant data in is the easy part, getting it back out to a usable state is the hard part.

Isn't it a simple problem though?

There must be a value (a discriminator) that says how to interpret the data. This value can be located anywhere as long as the code that does the interpretation can find it. For union-like stuff the discriminator is typically just an integer. For stuff involving virtual functions, the discriminator is the pointer to the virtual table.

[markyrocks]

@mbozzi I've given this type of problem alot of thought and I may have even had this discussion b4. The OP's ultimate conclusion to this is probably different than mine. The point of why I play with this problem is to make a variant container that is able to store mixed types and have the in and out flow of the data to be seamless without having to declare a template type with every transaction. This is kinda simple to do for a handful of types bc you can have a class that creates an element that orchestrates a template "object" class that just saves information about the data but you have to know what type the data is to do this so you end up with a switch statement or a constructor for every type you're dealing with or the element class has to be templated but then everything shifts up a layer in the inception and your left with the same problem. A similar process is required to get the data out. Needless to say it gets messy quickly. This is why I find this problem fascinating bc it gets me stuck in an infinite loop with no elegant way to resolve it. Idk I'm probably just a weirdo. I'm going to keep playing with it until it falls off tho.

[ElusiveTau]

mbozzi wrote:

void get_a(A* pa) { static A my_a(5); *pa = my_a; }

I'd never thought about assigning a base type to a derived type. This is probably outside the scope of the question in my OP, which I will mark as complete.

I'm a little confused because others seem to think it's the other way around (i.e., copy-assigning a derived type to a variable of a base type). For example, [1]. Is this still an example of object slicing?

[1] https://stackoverflow.com/a/49148511/5972766

[mbozzi]

ElusiveTau wrote:

I'm a little confused because others seem to think it's the other way around (i.e., copy-assigning a derived type to a variable of a base type). For example, [1]. Is this still an example of object slicing?

Maybe not, but I wouldn't know what else to call it. It's similar at least.

(FWIW the words "object slicing" don't seem to appear in the standard document.)

markyrocks wrote:

it gets me stuck in an infinite loop with no elegant way to resolve it

Right, there is no way to resolve it.

Given a memory blob, the program can either
a.) assume what the memory blob represents; or
b.) look it up somehow.
We're just talking about case b.

If you just want to get the switch statements out of your code you can make the compiler write an equivalent for you using virtual functions. See the various examples of type erasure in the standard library, std::function for example.