1
\$\begingroup\$

If I have a class called Something, what will the consequences for memory be if I include, in that class, a pointer to another object of the same class? So if the objects ThingOne and ThingTwo are both Something objects, ThingOne's contained pointer could point to ThingTwo (and vice versa, I assume)? I am trying to create a very simple alternative to both typical arrays (I need something more dynamic) and classic vectors (they keep gumming up my work. Please do not misinterpret this question as asking for help on vectors, though).

Needless to say, the pointers would be empty in the class, only to be set when an instance of the object has already been created.

\$\endgroup\$
  • 2
    \$\begingroup\$ Bear in mind that pointer chasing through a linked list (when the objects are arranged arbitrarily/randomly in memory) can introduce extra cache misses as compared to iterating over a densely-packed array or vector. Especially if your objects are small, numerous, or you iterate through the list frequently, this can cause a very substantial slowdown. If that's a concern, consider posting a new question about the issues you're experiencing with vectors "gumming up" your work, and users here may be able to help you find solutions to that root problem \$\endgroup\$ – DMGregory Jun 5 '17 at 16:23
  • 2
    \$\begingroup\$ Before rolling out your own linked list, have a look at std::forward_list, std::list, boost::intrusive::list (different kinds of linked lists), and std::deque (looks much like a vector, but does not reallocate when extending, which I suspect is the trouble std::vector is causing you). \$\endgroup\$ – Quentin Jun 5 '17 at 19:13
2
\$\begingroup\$

If I understand you correctly you are talking about creating a memory structure which is called a Linked List in CompSci.

A linked can be single-linked or double-linked and each node will hence contain pointers to the next and previous object respectively.

This memory structure is, as you mention, more or less efficient, as it does not allocate any more space than it needs. There is an overhead for the pointers, but that is negligible in most cases.


A consideration that has to be taken is the fact that you do not get random access on the elements of a linked list. Every access has to iterate from either the head or tail of the list (in case of a doubly linked one, otherwise you only have a head) up to the desired node.

This means it will perform better in cases where you only have sequential access and fast changing lists. But will be outperformed in virtually any case where you need random access.

\$\endgroup\$
  • \$\begingroup\$ It is almost entirely for sequential usage. But also, it should allow a vector-like "endless array" use, right? \$\endgroup\$ – Henry Stone Jun 5 '17 at 19:56
  • 1
    \$\begingroup\$ @HenryStone with a linked-list you basically have single blocks of memory each representing one entry in your list, each containing a block of data making up your object whatever it is and a pointer to the next entry in the list (make that two pointers in case of a doubly-linked-list). So yes, the size of your list is only limited by your memory. You will still have slower reading times because the blocks don't have to be sequential in RAM and will most likely not be, so your CPU will have to make more read-accesses to your memory. \$\endgroup\$ – dot_Sp0T Jun 5 '17 at 19:59
0
\$\begingroup\$

The "very simple alternative" is called a Linked List and it's been around for a very long time.

There is, fundamentally, nothing wrong with what you are doing. You will need to forward declare the type, or your Something field inside your Something class will not compile.

\$\endgroup\$
  • 1
    \$\begingroup\$ Yuck, you beat me - but my answer contains a beautiful link.... Call it a draw? That is cheating! \$\endgroup\$ – dot_Sp0T Jun 5 '17 at 16:09
  • \$\begingroup\$ You don't need forward declaration since there is only one class, right? \$\endgroup\$ – HolyBlackCat Jun 5 '17 at 16:33
  • 1
    \$\begingroup\$ @ArcaneEngineer Your link refers to two classes which have pointers to each other. It's quite different from a single class case. (See for yourself.) A class is considered declared after a compiler sees words class Something. (Whether they are a forward declaration or a part of a normal class declaration.) But before the closing } in the definition of this class it's considered an incomplete type. It's legal to create pointers to incomplete types, otherwise even solution at your link wont work. \$\endgroup\$ – HolyBlackCat Jun 5 '17 at 18:21
  • 1
    \$\begingroup\$ Pardon me if that sounded offensive, I didn't mean it. Of course the answer remains useful. :) I'm not insisting on any edits, just thought you (and/or future readers) may consider it interesting. Btw, GCC compiles the code even in C mode. Our compilers seem to behave differently. \$\endgroup\$ – HolyBlackCat Jun 5 '17 at 20:24
  • 1
    \$\begingroup\$ Almost feels like people are fighting over me, I am very honored! As the title states, it is in C++, so any C++ issues will likely apply. And please, remember to be excellent to each other! \$\endgroup\$ – Henry Stone Jun 5 '17 at 21:35
0
\$\begingroup\$

I'm not sure your question got answered. You can check the memory cost of a pointer by using sizeof(Type*). It will in practice be 4B in a 32-bit programme and 8B in a 64-bit programme.

\$\endgroup\$
  • \$\begingroup\$ Thanks, my question was answered, but your answer adds highly valued detail! \$\endgroup\$ – Henry Stone Jun 6 '17 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.