STL deque accessing by index is O(1)?

by

I found this deque implementation from Wikipedia:

Storing contents in multiple smaller arrays, allocating additional
arrays at the beginning or end as needed. Indexing is implemented by
keeping a dynamic array containing pointers to each of the smaller
arrays.

I guess it answers my question.

More Related Contents:

  1. What really is a deque in STL?
  2. Why would I prefer using vector to deque
  3. What is the easiest way to initialize a std::vector with hardcoded elements?
  4. C++ std::set update is tedious: I can’t change an element in place
  5. Initializing a static std::map in C++
  6. Alternative to vector
  7. Best way to extract a subvector from a vector?
  8. how to provide a swap function for my class?
  9. How can I create my own comparator for a map?
  10. GCC STL bound checking
  11. Does vector::erase() on a vector of object pointers destroy the object itself?
  12. How to reuse an ostringstream?
  13. Inspecting standard container (std::map) contents with gdb
  14. Extending the C++ Standard Library by inheritance?
  15. How to implode a vector of strings into a string (the elegant way)
  16. How to update an existing element of std::set?
  17. Search a vector of objects by object attribute
  18. std::strings’s capacity(), reserve() & resize() functions
  19. What is an iterator’s default value?
  20. all combinations of k elements out of n
  21. array vs vector vs list
  22. Is std::string size() a O(1) operation?
  23. std::string in a multi-threaded program
  24. How can I sort an STL map by value?
  25. What happens if you increment an iterator that is equal to the end iterator of an STL container
  26. Standard Library Containers with additional optional template parameters?
  27. Embedded C++ : to use STL or not?
  28. General use cases for C++ containers
  29. Syntax for using std::greater when calling std::sort in C++
  30. list of polymorphic objects

Leave a Comment