Qualified's blog

Data structure that keeps elements in chronological order, allows erases in O(log(n)) or less, and allows insertions.
By Qualified, history, 4 years ago, In English

I want a data structure that keeps elements in the way that you inserted them and allows erases in $$$O(log(n))$$$ or less. For example, if the initial array is empty and you insert 5, 2, 4, then the array would be [5, 2, 4]. Erase 4 and it is [5, 2]. Insert a 3 and it is [5, 2, 3]. I know that set allows erases in $$$O(log(n))$$$ and insertions but it keeps the elements in sorted order, not in the way that I inserted them.

  • Vote: I like it
  • -20
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Qualified (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it
Self understandable code
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    You can get rid of the log factor to achieve O(1) for Insert and Delete operations by using std::list and std::unordered_map.

    Code
    → Reply