0

I know that a std::vector supplies an O(1) random access function but only has an O(N) insertion/removal function due to having to shift elements to make new space or fill up old space.

On the other hand, a linked list data structure has an O(1) insertion/removal function due to its use of pointers, but an O(N) random access function because we have to traverse from the first element to access any other.

Is there any data structure that can combine the two benefits given by each of the above data structures, to produce a structure with constant lookup, insertion, and deletion times?

Telescope
  • 2,068
  • 1
  • 5
  • 22
  • Use `std::map` or `std::unordered_map` – 김선달 Jun 05 '20 at 01:46
  • 1
    You might want to clarify that "insertion" and "deletion" refer to arbitrary elements, since a vector's insertion and deletion of the last element is O(1), and a deque's insertion and deletion of the first or last element is O(1). (It's the operations in the middle that are slow.) – JaMiT Jun 05 '20 at 01:47
  • `std::unordered_map` has these features, but it performance may be sub optimal. The way the standard defines an unordered_map, you basically have to implement it as an array of linked lists. Those lists are expensive to traverse when there are collisions. Use a hash-map, just not `unordered_map` – NathanOliver Jun 05 '20 at 01:50

0 Answers0