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: Should the complexity of std::list::size() be O(n) or O(1)?

From: Gabriel Dos Reis <gdr at integrable-solutions dot net>
To: Jonathan Wakely <jwakely dot gcc at gmail dot com>
Cc: Peter Dimov <pdimov at mmltd dot net>, libstdc++ <libstdc++ at gcc dot gnu dot org>
Date: 29 Nov 2005 16:47:14 +0100
Subject: Re: Should the complexity of std::list::size() be O(n) or O(1)?
References: <801D405E-70DD-4E2D-B6FA-72D447A358F4@apple.com> <m3br08ro9l.fsf@uniton.integrable-solutions.net> <838CF22A-24B7-49DF-B884-37591DD0F561@apple.com> <m3sltg8e3g.fsf@uniton.integrable-solutions.net> <20051129002527.GA4662@noisy.compsoc.man.ac.uk> <011301c5f47f$77af5390$6501a8c0@pdimov2> <m3acfom8v2.fsf@uniton.integrable-solutions.net> <004701c5f4de$251a8820$6501a8c0@pdimov2> <438C5703.1040108@suse.de> <005501c5f4ee$1b1ac460$6701a8c0@pdimov> <4348dea50511290623w23f8fbbdk@mail.gmail.com>

Jonathan Wakely <jwakely.gcc@gmail.com> writes:

| On 11/29/05, Peter Dimov <pdimov@mmltd.net> wrote:
| 
| > If all containers that keep their elements in a contiguous block of memory
| > (std::vector, std::string, std::valarray, user-defined array, string, matrix
| 
| Sorry for going off on a tangent, but does the standard actually
| require contiguous storage for std::string?

It does not.  But, that does not matter.  Just pretend it does and if 
implementations don't agree you, decree they are not portable <g>.

More seriously, there have been discussions to require it and I
believe the general sentiment now is "yes"

But no, I don't buy the container<T>::iterator == T* argument.

-- Gaby

Follow-Ups:
- Re: Should the complexity of std::list::size() be O(n) or O(1)?
  - From: Peter Dimov
- Re: Should the complexity of std::list::size() be O(n) or O(1)?
  - From: Jonathan Wakely

References:
- Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?
  - From: Howard Hinnant
- Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?
  - From: Gabriel Dos Reis
- Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?
  - From: Howard Hinnant
- Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?
  - From: Gabriel Dos Reis
- Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?
  - From: Jonathan Wakely
- Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?
  - From: Peter Dimov
- Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?
  - From: Gabriel Dos Reis
- Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?
  - From: Peter Dimov
- Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?
  - From: Paolo Carlini
- Re: [C++] Should the complexity of std::list::size() be O(n) or O(1)?
  - From: Peter Dimov
- Re: Should the complexity of std::list::size() be O(n) or O(1)?
  - From: Jonathan Wakely

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