-2

From what I understand, swapping a std::vector is a constant time operation because the only pointers are being swapped, but in the case of an std::array the swapping is element-wise. Is it possible to swap the pointers of an std::array?

Apologies if this has been asked to death already. If so kindly point me in the right direction, thanks.

Enlico
  • 23,259
  • 6
  • 48
  • 102
lilweege
  • 61
  • 1
  • 2
  • 6
  • 2
    `std::array` doesn't have any pointers in the first place. It's just a wrapper around a C-style array – IWonderWhatThisAPIDoes May 30 '21 at 19:40
  • 1
    You can certainly use two `std::array` pointers pointing to two array instances, and swap those pointers. That may or may not be good enough for the algorithm you are trying to implement. – Igor Tandetnik May 30 '21 at 19:40
  • If an array holds elements that are pointers or other trivial types, they can be copied to another array in constant time, using memcpy(), an optimized std::copy(), etc. But non-trivial types can't be. If you want to swap the elements of 2 arrays, then they have to be swapped individually. – Remy Lebeau May 30 '21 at 19:41
  • @RemyLebeau: That wouldn't be constant time in terms of the number of entries in the array. – Nicol Bolas May 30 '21 at 19:41

2 Answers2

3

You can think of std::vector as something along these lines

template<typename T>
struct vector {
    T * pointer;
    int N; // well, not really int
    // the several constructors allocate memory, set N, and do other stuff if necessary
    // Other stuff
};

so there's the pointer you refer to, the one which is swapped when you swap two vectors.

But std::array is more like this

template<typename T, int N> // again, not really int
struct array {
    T elements[N];
    // other stuff
};

so there's no pointer here, just statically allocated memory.

(Learned here.)

Enlico
  • 23,259
  • 6
  • 48
  • 102
2

There are no "pointers of a std::array". The array is its contents; it doesn't point to anything any more than a class with an int member "points" to that member.

Nicol Bolas
  • 449,505
  • 63
  • 781
  • 982