3 ms·
How would you implement an O(1) list without breaking encapsulation then?
by rumcajz 14y ago
How would you implement an O(1) list without breaking encapsulation then?
- tptacek 14y agoWhat do you mean, "O(1) list"?
- tg3 14y agoI assume he meant "a list from which an element can be removed in constant time."
- mpyne 14y agoPerhaps I'm being dumb, but doesn't std::list<T> already do exactly this? From SGI's STL docs: "A list is a doubly linked list. That is, it is a Sequence that supports both forward and backward traversal, and (amortized) constant time insertion and removal of elements at the beginning or the end, or in the middle"
- malkia 14y agoAs others have said - yes, as long as you keep the iterator not the object itself. e.g. from T itself you cannot find where it was stored, so with std::list<something>, and then only from something you can't find where it is (you can have to look for it in the list).
- tedunangst 14y agoThe question doesn't make much sense. Your C example totally breaks encapsulation.
- rumcajz 14y agoWell, what kind of problem is that in C? It's C. It has no public/private keywords. Nobody expect struct in C to be well-encapsulated.
- scott_s 14y agoIt's also not a problem in C++ if you don't care. Just because C++ gives you the means to enforce encapsulation doesn't mean you have to. And, as I said below, when your goal is performance and you need to break abstractions, it makes sense not to enforce encapsulation.
- ahupp 14y agohttp://www.boost.org/doc/libs/1_35_0/doc/html/intrusive/usage.html http://www.boost.org/doc/libs/1_35_0/doc/html/intrusive/usag... Not sure if this qualifies as not "breaking encapsulation" but it's as close as you're going to get.
- eklitzke 14y agoThe idiomatic way to access and manipulate STL data structures is through iterators. In this case, an iterator for a std::list is basically a pointer/reference to the person container in the article, so if you're referring to the list objects via their iterators there's no need for O(n) list traversal.