Pointer Triad Storage: Yes or No?

Alright, I was thingking about somthing...

Pointers point to an address in memory. What if I used 3 pointers: 2 to mark the first/last nodes, and the third to mark the current node being referenced?

I would wrap it in a class (to make the memory management automatic, of course), but is this practical??

mabey some pseudo code will get the juices flowing:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<class type>
class supercondensed_list{

public:
    supercondensed_list();
    ~supercondensed_list();

/* push_back, push_front, pop_back, pop_front,
find, insert, remove, operator[], operator=,
operator<, operator>, operator>=, operator<=,
operator+, operator+=, operator==*/

private:

    type *beg = new type(), *end = NULL, *ref = NULL; //end and ref will be initialiized by the constructors 


Any things I should take into consideration? I'm not exactly the most experienced with pointers, and manually managing memory, but I think it's worth trying. If this works, then my programs should, in theory, be 100% memory efficient.
Last edited on
Congratulations you invented a linked list. Yes they are practical, see std::list.

Edit:
Wise ass comment aside, what you are describing is very similar to an assignment I had in comp sci 2 a double ended linked list with custom accessors/mutators and no support for iterators. std::list is a double ended list except it uses iterators instead of using a current pointer. It is definitely a good learning excercise but I would use std::list in any application.

Any things I should take into consideration? I'm not exactly the most experienced with pointers, and manually managing memory, but I think it's worth trying. If this works, then my programs should, in theory, be 100% memory efficient.
Linked lists are efficient when inserting or removing nodes at any location, but they do not offer random access (no access using operator[]) so they can be slow finding specific elements. If you need random access lists are a bad choice. If you need to insert or remove any where but the end (or front with deque) then a list is a good choice.
Last edited on
> and the third to mark the current node being referenced
so you can't traverse a constant list.

> then my programs should, in theory, be 100% memory efficient.
maybe I'm missing something (I know, the nodes). ┬┐how did you manage to implement a list without a `next' pointer?

> I'm not exactly the most experienced with pointers, and manually managing memory
then you may want to consider a simpler approach, circular list with an "empty" header cell. You don't have to worry about invalid pointers in that case
http://www.cplusplus.com/forum/beginner/90716/#msg487820
@naraku:

What if I sorted it and emplemented a binary search?

Also, what if I indexed it?

Also, I just realized I wouldn't need the third pointer, I would just need to add a nimber tothe address of the first (takin the necessary precautions, first, of course).

So, for example:

Access the third element:
Would this work?
1
2
3
4
5
6
7
8
type& object::operator[](const unsigned int& x)
{
    if(!this->in_bounds(x))
    {
         return type();
    }
    reurn *(begin + x);
}
What if I sorted it and emplemented implemented a binary search?
You could, but then you might as well write a binary search tree.

Also, what if I indexed it?
...
Would this work?


No it wont work. The list nodes wont be in contiguous memory, so no pointer arithmetic.
but, they would have to be...

Alright, what if I used an array instead? Aren't arrays just 1 solid block in memory?

My goal here is to create an object to store objects in a condensed and memory-efficient manner...
Last edited on
There exists a concept known as a smart pointer. It seems you are trying to reinvent it. Look it up and see what are the existing options, because you may want to have shared/non-shared access to a resource. You simply can't have a "100% memory efficient" model for every situation, because it depends on many factors. Also, do note the recommendations so far, about reusing a data structure from the standard library agains rolling up your own (although, again, it depends on your exact requirements and constraints).
but, they would have to be...
They could be placed in sequential memory locations by pure luck, but it extremely unlikely.

Alright, what if I used an array instead? Aren't arrays just 1 solid block in memory?
Yes arrays are stored in contiguous memory.

My goal here is to create an object to store objects in a condensed and memory-efficient manner...
I'm not sure what you mean by "condensed" here. Lists are reasonably memory efficient (no blocks of memory pre-allocated) but they don't fit all situations. The container you choose should depend on how you intend to use it.

Edit:
There is nothing wrong with being memory efficient, but I wouldn't get too extreme about it unless you are working with low memory systems (embedded and mobile come to mind).
Last edited on
Topic archived. No new replies allowed.