This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?


On Nov 24, 2005, at 4:32 AM, Gabriel Dos Reis wrote:

| My position isn't that a doubly-linked list should have an O(1) size.
| It is that if a container, any container, has a size(), then that
| member should be O(1) (same for operator[], at, swap, max_size,
| capacity, begin, end, front, back, push/pop_front, push/pop_back,
| empty, default ctor, -- perhaps amortized O(1) on some of those).


so the next battle is to make map<>::operator[] O(1)?
That one might be more useful to me than making list<>::size O(1) ;-p

Sarcasm aside, when I first started implementing that function years ago, I renamed the underlying implementation "find_or_insert" just so that I could remember what the thing did. Over the years I've gotten use to the name of map::operator[]. But I clearly remember being confused by it (but then I'm easily confused! :-)).


-Howard


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]