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: Jonathan Wakely <jwakely dot gcc at gmail dot com>
To: Peter Dimov <pdimov at mmltd dot net>
Cc: libstdc++ <libstdc++ at gcc dot gnu dot org>
Date: Tue, 29 Nov 2005 14:23:16 +0000
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>

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?  I was under the
impression it used to implicitly require it, until lib DR259 was
resolved.  Can anyone set me straight?

jon

Follow-Ups:
- Re: Should the complexity of std::list::size() be O(n) or O(1)?
  - From: Gabriel Dos Reis

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

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