2

I'm writing a parallel implementation of some data structures. I'd like to find out if someone know about difference in performance between pure pointers and std::vector. If you know trustful docs about it, please write URL/book name/whatever. Any hints are welcome!

Adam
  • 21
  • 1
  • 1
    What is the commonality between pointers and `std::vector`? – pmr Nov 25 '10 at 21:14
  • Unfortunately I know nothing about this, but +1 for a very good, probably very common question :-) – Bojangles Nov 25 '10 at 21:15
  • Both can store any kind of data. I ask cause I don't know which one is faster. – Adam Nov 25 '10 at 21:15
  • I assume that by "pure pointers" you mean hand-crafted dynamically allocated arrays? – André Caron Nov 25 '10 at 21:17
  • @Adam: no, they can't hold "any kind of data". The can hold `n>=0` objects of the *same* type. What do you mean exactly? – André Caron Nov 25 '10 at 21:18
  • Then see Klaim's answer. Use `std::vector<>`. – André Caron Nov 25 '10 at 21:20
  • @Andre: I meant that can store an instance of any class/primitive, either pointer to function and so on... My question is which one is faster, cause I don't know how std::vector have been written in standard lib. – Adam Nov 25 '10 at 21:20
  • @Adam: you can almost certainly look at the source code for vector for any particular implementation you're interested in. In my installation of GCC, it's in `/usr/lib/gcc/i686-pc-cygwin/4.3.4/include/c++/bits/stl_vector.h`, but for closed-source compilers it's still (normally) in headers somewhere. If you want an answer that's applicable to *any* C++ implementation then you're out of luck because the standard doesn't guarantee precise performance, only algorithmic complexity. If you want an answer that's applicable to any *sensible* implementation then DeadMG is about right. – Steve Jessop Nov 26 '10 at 02:00

4 Answers4

5

The difference is usage and implementation relative.

Klaim
  • 67,274
  • 36
  • 133
  • 188
3

You can make std::vector as fast as normal pointers by using the unchecked operator[] and resizing appropriately. The reality is that vector is a compile-time abstraction over a pointer- not a runtime one, unless you choose to use extras. What's much more important is the vastly increased safety vector offers- debugging iterators, automatic and safe resource management, etc. There is no reason to use a raw pointer.

Edit: My reference is that profiling run you did before you even considered losing the safety of vector.

Puppy
  • 144,682
  • 38
  • 256
  • 465
0

According to this answer in a similar question, accessing an element in a dynamically-allocated array versus a std::vector will be roughly the same. There's some good analysis in that question and in this one as well.

Community
  • 1
  • 1
Wyatt Anderson
  • 9,612
  • 1
  • 22
  • 25
0

If you mean to compare a std::vector with some hand-written dynamic array here are some points of reference:

  • The resizing factor on insertion is important. This factor isn't specified by the standard but is usually between 1.5 or 2 and it must guarantee amortized constant time on insertion operations.
  • The allocator: A lot of the performance depends on the allocation mechanism that is used, same goes for your pointers.
  • Boundary checking can occur in std::vector if you call vector::at which cannot happen with raw pointers.
pmr
  • 58,701
  • 10
  • 113
  • 156
  • the resizing factor isn't relevant if you're making an apples to apples comparison. A raw array has to be sized up front, so presumably you'd do the same with `vector`. – jalf Nov 25 '10 at 23:12
  • @jalf: it's not really clear what "pure pointers" means, so it's more of an apples to some-unspecified-fruit-in-a-locked-box comparison. – Steve Jessop Nov 26 '10 at 01:51
  • @jalf: I thought if he compared something with `vector` dynamic resizing is a must. If he doesn't need dynamic resizing he should use `std::array` anyway. – pmr Nov 27 '10 at 14:00