0

It is said that the std::deque swap function takes constant time,not linear. http://www.cplusplus.com/reference/deque/deque/swap-free/. How is that function implemented then?

  • How do you suppose `std::vector` is swapped? – Passer By Sep 29 '17 at 07:26
  • 2
    If you had two `int` variables that you wanted to swap, how would you do that? Now what if the variables were *pointers* instead? Now think about how a `std::deque` could be implemented, perhaps using a *pointer*? So how would then a swap between two `std::deque` objects be done? – Some programmer dude Sep 29 '17 at 07:29

2 Answers2

2

All resizable standard library containers (that is, all except std::array) have to store their contents in dynamically allocated memory. That is because they can grow arbitrarily large and there's no way to store arbitrarily many objects in the fixed space occupied by the container object itself. In other words, it must be possible that container.size() > sizeof(container).

This means that the container object only stores a pointer to its contents, not the contents itself. Swapping two containers therefore means simply swapping these pointers. In extremely simplified form:

template <class T>
class Container
{
  T *_begin, *_end;

  friend void swap(Container &a, Container &b)
  {
    std::swap(a._begin, b._begin);
    std::swap(a._end, b._end);
  }
};

Of course, in practice, this is complicated by the presence of allocators etc., but the principle is the same.

Angew is no longer proud of SO
  • 167,307
  • 17
  • 350
  • 455
0

The implementation of deque is typically hidden by using pimpl idiom (each deque holds a pointer to implementation). The pointers are then swapped. It might (also) be that the deque at least holds a pointer to its buffer, which is then swapped (with related members like size).

This post (copy and swap idiom) is related to how the swap might be implemented.

Werner Erasmus
  • 3,988
  • 17
  • 31