Filling a container with objects using pointers / iterators

Question

I have a series of nested objects that I need to serialize into a byte (unsigned char) array to send out to another computer over UDP.

Right now I each object create a std::list, and pass that list to the next object up the 'tree' and then it merges the lists to create the final packet.

class Item {
 unsigned char value;
}
class Sublist {
 std::vector<Items*> items;
 std::list<unsigned char> subpacket;
 std::list<unsigned char> Sublist::serialize() {
 subpacket.clear();
 for(auto item : items) {
 subpacket.push_back(item->value);
 }
 return subpacket;
 }
}
class Superlist {
 std::queue<Sublist> sublists;
 std::list<unsigned char> serializedSublist;
 std::list<unsigned char> packet;
 std::list<unsigned char> Superlist::serialize() {
 packet.clear();
 for(auto sublist : sublists) {
 serializedSublist = sublist.serialize();
 packet.insert(packet.end(), serializedSublist.begin(), serializedSublist.end());
 }
 return packet;
 }
}

However, this feels really inefficient with unnecessary clear() and insert() calls, and in generally feels a bit sloppy.

I feel like a more efficient approach would be for the Superlist to have a unsigned char container (vector, list, deque?), and then give each Sublist a pointer to where it should write data to.

I feel like perhaps something like:

class Sublist {
 std::vector<Items*> items;
 void Sublist::serialize(std::vector::iterator begin) {
 for(auto item : items) {
 begin->push_back(item->value);
 ++begin;
 }
 }
}
class Superlist {
 std::queue<Sublist> sublists;
 std::vector<unsigned char> packet;
 std::list<unsigned char> Superlist::serialize() {
 packet.clear();
 for(auto sublist : sublists) {
 sublist.serialize(packet.end());
 }
 return packet;
 }
}

Problems with this exact code include:

• I don't think I can call push_back on a iterator

• It'd be nice if I could create the final packet of a final size first, and then send pointers off to the correct location in the packet for each sublist to begin writing.

Would an approach like this work? Is there an even more concise and clever way to place all of the objects in a buffer?

Answer 1

std::list is usually implemented as a doubly-linked list which is very inefficient for your purpose. You should definitely use std::vector for this (or similar dynamic array structure, possibly some stream).

Your second approach is the idea I got while reading your question. You don't need an iterator (and I don't think you can call push_back on it), but a reference to the vector - vector<byte>& buffer as the argument.

The same applies to serizalize() on the main list with possible default argument creating the vector. If you want to have the final packet somewhere, you can track some dirty flag (if you can modify the structure) to re-serialize it as needed.

---

You could do that last approach in two phases:

1. Track the sizes to compute the total size needed
2. Allocate the buffer (you could use byte* or vector)
3. Do the same again, but passing index together with the vector (buf[i++] = data)

...it is a bit more low-level solution, but possibly fastest. I would personally not worry that much and use the direct approach with vector (it should be fast enought).

---

Some notes about errors in the code:

class Sublist {
 std::vector<Items*> items;
 std::list<unsigned char> subpacket;
 std::list<unsigned char> Sublist::serialize() {

You do use Sublist:: prefix when you define the methoud outside of the class, not here (remove it).

class Sublist { ...
 std::vector<unsigned char>& serialize(std::vector<unsigned char>& buffer) const { ...

This should be the final signature (taking reference, returning the reference and with const modifier on the method because you are not modifying the class).

• nathan lachenmyer: So I should be able to just pass a reference of the target vector, and then push_back using that reference? Huh. I never thought of that! (references are black magic to me)
• user52292: Yes, references are just like pointers. There are few differences, but you can think about them the same (like there was * infront of it).
• nwp: @nathanlachenmyer Think about references as a new name for a variable. int n; int &rn = n; means rn is a new name for n. It comes in handy when the original name is not available anymore like in functions: void swap(int &n1, int &n2); int i1, i2; swap(i1, i2);. Now n1 is another name for i1 which is useful because inside swap you have no access to i1. References are practically always implemented with pointers, but you really should not think of them as pointers. Think of them as alternative names.
• nathan lachenmyer: @nwp -- that was a super lucid and clear explanation! thanks :)