Your opinion on the functionality of a template dynamic list

[Joshua Flynn]

I am just in the design phase of an improved template dynamic list for use in combination with SFML classes, and I want people's opinion of what they imagine or expect (I want to make it instinctive and more user-friendly):

//What do you imagine these do, and what do you imagine they return?
TemplateList++;
TemplateList--;
--TemplateList;
++TemplateList;
TemplateList = Item;

//What do you imagine this should return?
(!TemplateList)

I have my own ideas of what the functions should do, but I want to see what others think.

Thank you for any feedback.

[Grimshaw]

//What do you imagine these do, and what do you imagine they return?
TemplateList++;
TemplateList--;
--TemplateList;
++TemplateList;

 - I could only see this as iterating the list, increasing and decreasing an internal iterator!

TemplateList = Item;

Makes no effective logic to set a list as one item, but if you make it a += its a perfectly acceptable "Append"

//What do you imagine this should return?
(!TemplateList) - makes no sense to me, if its a template, the any object won't have a common logic evaluation. Therefore, what the hell wold be a negation of a list of any kind of object? Cant think of anything

Hope it helps

[Disch]

None of those operators make any sense.

How can you increment a list?  How can you assign an entire list to one item?

The closest thing I can imagine would be that !TemplateList would check to see if the list is empty, but even that is "blech".

EDIT:
Don't get cute with operator overloading.  The reason it exists is to make code more natural, not to avoid typing function names.  If you have to ask the question "what should this operator do or return", then you shouldn't be making that operator.  It defeats the point and makes your code more confusing.
/EDIT

Any reason why you don't want to just use std::list?


EDIT 2:

if you make it a += its a perfectly acceptable "Append"

I disagree that that's perfectly acceptable  =P

[Laurent]

TemplateList++;
TemplateList--;
--TemplateList;
++TemplateList;
TemplateList = Item;
(!TemplateList)

- push back a default-constructed item
- pop back
- pop front
- push front a default-constructed item
- no idea
- test if the list is empty
?

In my opinion, it's confusing at best. Follow the rules of the language and its standard library. Don't try to over-simplify, longer but more explicit names will always be more intuitive than operators. Use operators only when they make perfect sense. And... use standard classes, don't reinvent the wheel

[Joshua Flynn]

- I could only see this as iterating the list, increasing and decreasing an internal iterator!

Makes no effective logic to set a list as one item, but if you make it a += its a perfectly acceptable "Append"

makes no sense to me, if its a template, the any object won't have a common logic evaluation. Therefore, what the hell wold be a negation of a list of any kind of object? Cant think of anything

Hope it helps

Yes it does, thank you for your feedback.

If you have to ask the question "what should this operator do or return", then you shouldn't be making that operator.  It defeats the point and makes your code more confusing.

I have in mind precisely what it would do, but generally in programming, bugs occur when the assumptions of the user (IE other than me) are different from the assumptions of the program. In this case I want to see if other people instinctively have the same concepts I do before I make it part of the design.

Any reason why you don't want to just use std::list?

Std::list requires log(n) time to get the size of the list, when it's perfectly possible to get a log(1) return, including iterator numeric position. Given how I have no idea how it operates under the covers (if it does log(n) for size returns, what else does it do inefficiently?), it makes it difficult for me to optimise it to other classes - which are supposed to automate, simplify and make safe tasks.

The size issue might not seem like a gripe at first but running log(n)*n for how many times size is required seems very poor (especially given this will be for dynamic char lists of sizes 89000+ or more from files). Custom-lists also gain the advantage of improving over iteration (IE design and improvement), fewer functions, more capability/stability.

TemplateList++;
TemplateList--;
--TemplateList;
++TemplateList;
TemplateList = Item;
(!TemplateList)

- push back a default-constructed item
- pop back
- pop front
- push front a default-constructed item
- no idea
- test if the list is empty

These are generally the ideas I had for the list. Iteration across the list was the other alternative, but it would make either pre or post-fix redundant (duplication of tasks).

In my opinion, it's confusing at best. Follow the rules of the language and its standard library. Don't try to over-simplify, longer but more explicit names will always be more intuitive than operators. Use operators only when they make perfect sense. And... use standard classes, don't reinvent the wheel

The operators would be front-ends for suitably named functions, with the named functions themselves still accessible. As for std library functions, they tend not to be my preference, generally because of how they work.

But it's good, thank you for the feedback. I will consider it when writing the classes. Any additional feedback is appreciated.

[Disch]

Std::list requires log(n) time to get the size of the list,

How do you figure that?  All it has to do is store the size of the list internally (which I'm reasonably sure it does) and it gets O(1).

I don't even see how it could get O(log(n))

Custom-lists also gain the advantage of improving over iteration(IE design and improvement)

I don't follow.  How can you improve upon linked list iteration?

fewer functions

So you basically want to make a list that does less.

Call me crazy, but that's a shortcoming, not an advantage.

more capability

What is std::list incapable of?

stability.

So you plan to write a linked list that's more stable than the one that's been around for several years and has been extensively used and tested by virtually every C++ programmer in the world.



I don't mean to sound negative.  It's just that this seems like a fool's errand to me.  Unless it's purely for academic/educational reasons, there's really no good reason to reinvent the wheel like this.  It just seems like a massive waste of time, and will confuse/annoy any people who use your code in the future.


EDIT:

These are generally the ideas I had for the list. Iteration across the list was the other alternative

Again, the mere fact that there are multiple possibilities of what the operators could be doing is a pretty clear indication to me that they should not be overloaded.

[Laurent]

Standard containers have a robust design and implementation which is the result of years and years of experts working on it. std::list::size is O(1). Basically, there are enough containers so that you can always find one that can be perfect for your needs (don't use a std::list to store thousands of characters!).

People (often beginners -- don't know about you) always tend to rewrite standard classes, I don't know why; maybe they don't have enough experience with the language and find it simpler to write their own classes rather than adapt their code to the language and its SL. A lot of people have to start like this, experiment and write their own low-level stuff, until they feel comfortable enough with the language.

It's not bad to reinvent the wheel from a learning point of view, but for "real" code just forget about that, and use what the language provides.

[omeg]

Sometimes if you need the best performance and not much functionality, you can rewrite it... I did that once, replacing std::list with a dynamic array implementation which was much faster. But that was a specific case, I was number crunching some genetic algorithms and needed the speed. But for general cases it's usually good enough.

[Haikarainen]

//What do you imagine these do, and what do you imagine they return?
TemplateList++;
TemplateList--;
--TemplateList;
++TemplateList;
TemplateList = Item;

//What do you imagine this should return?
(!TemplateList)

I have my own ideas of what the functions should do, but I want to see what others think.

Thank you for any feedback.

TemplateList++;  - Add new item with default constructor(push_back(Item()))
TemplateList--; - Remove last item(pop_back())

--TemplateList/++TemplateList - Iterations

TemplateList = Item doesnt make sense, but maybe add that item? For that you should have += instead.

!TemplateList should return if its empty.

[Hiura]

TemplateList++;  - Add new item with default constructor(push_back(Item()))
TemplateList--; - Remove last item(pop_back())

--TemplateList/++TemplateList - Iterations

It would be very confusing because you won't be able to do *tl++ = smth.

As said previously,

Use operators only when they make perfect sense.

I would say even more : Use operators only when they make perfect sense.

[Haikarainen]

TemplateList++;  - Add new item with default constructor(push_back(Item()))
TemplateList--; - Remove last item(pop_back())

--TemplateList/++TemplateList - Iterations

It would be very confusing because you won't be able to do *tl++ = smth.

As said previously,

Use operators only when they make perfect sense.

I would say even more : Use operators only when they make perfect sense.

Hehe you are right sir Im not really that interested in a new container, since there are so many standards that do a good job already, just wanted to give my thoughts on an alternative tho

[Silvah]

All it has to do is store the size of the list internally (which I'm reasonably sure it does) and it gets O(1).

std::list::size is O(1).

Not necessarily, in libstdc++ it's O(n). Legal in "old" C++, IIRC not legal anymore in C++0x.

[Disch]

Even if that's the case, you can just store the size of the list separately.  To redo the entire class from scratch for such a minor detail is excessive.

[Fred_FS]

I have in mind precisely what it would do, but generally in programming, bugs occur when the assumptions of the user (IE other than me) are different from the assumptions of the program. In this case I want to see if other people instinctively have the same concepts I do before I make it part of the design.

I hope you realized that there are many different opinions and so I recommend you not to implement those operators.

Std::list requires log(n) time to get the size of the list, when it's perfectly possible to get a log(1) return, including iterator numeric position. Given how I have no idea how it operates under the covers (if it does log(n) for size returns, what else does it do inefficiently?)

I don't think that implementing size in O(n) is just for fun. Mostly it is by the way implemented in O(1). If it is not, it is mostly O(n) because of other performance issues. For example would std::list::splice be in O(n), if size is in O(1), because the new size of the list has to be computated. If size is O(n), splice would be O(1).
I'd prefer size in O(1) and splice in O(n), but there are obviously different opinions about this topic.

But there are many other different STL container.
std::deque for example can be used similar to std::list, provieds size in O(1) and individual element access in O(1).

Just have a look at all STL containers and think about using them.
http://www.cplusplus.com/reference/stl/

I think the STL containers are rather performant and I don't think that you would easily create a new one which is better than the others .

[Disch]

That's interesting.  I hadn't even thought about splice.

I would think the best way to handle that would be to invalidate the size after a splice, and only recalculate it if needed.  That way you can get O(1) for both, except the first time you call size() after a splice operation, which is the only time it would take O(n):

Code: [Select]


class list
{
//...
private:
  mutable size_t listsize;
  mutable bool sizevalid;

//...
void splice(...)
{
  //...
  sizevalid = false;
}

//...
size_t size() const
{
  if(!sizevalid)
  {
    recalcsize();
    sizevalid = true;
  }
  return listsize;
}
//...
};


I wonder if any implementations do it like that.