Which data structure supports efficient deleting and random access?

Question

I am looking for a data structure in which I can efficiently remove items and also supports random access.

I also need efficient insertion but as the ordering of elements is not important, I thought I can preallocate memory for maximum number of elements it may have to store and then always put the new element at the end so that no reallocation or move of other elements is necessary.

To the best of my knowledge, a linked list would be perfect for deleting but accessing its elements can take O(n) time. On the other side, a simple array (e.g vector in C++) has the random access property but deleting an element from such an structure has complexity of O(n).

Actually, the random access requirement is something stronger than what I really need. I only have to be able to pick an element of the structure uniformly at random. Clearly efficient access property implies efficiency of the operation I need but I am not sure if those two are equivalent.

Thanks in advance!

Cramp

A set may also be an alternative if the implementation allows to get a random element (I guess the same requirement goes for the hash table which doesn't always do that either) – Grandniece

Unfortunately the set implementation in C++ does not allow random access :( – Cramp

@ManiBastaniParizi You may want to tag your question with C++ then :) – Grandniece

Answer 1

I believe the solution you hint at in your question is actually what you need, except for a small detail.

You suggested:

I thought I can preallocate memory for maximum number of elements it may have to store and then always put the new element at the end so that no reallocation or move of other elements is necessary.

If indeed you can establish a reasonable maximum number of entries, then I would suggest you pre-allocate an array (e.g. using std::array if the maximum is known at compile time, or a std::vector otherwise) with that number of entries, establish an element count (to count the number of elements currently stored), and proceed as follows:

1. Initially you set the count to 0
2. When you insert an element, you add it to the end and increment the count
3. When you delete an element, you swap it with the last element and decrement the count
4. For random access (in the sense you described it, i.e. literally picking an element randomly) you determine a random number between 0 and count, and pick that element

The only detail I changed is element deletion, which I suggest you implement as switch positions with the last element.

Possible implementation:

#include <vector>
#include <utility>
#include <iostream>

template <typename Elem>
class randomaccesstable
{
public:
  randomaccesstable(std::size_t initial_size)
   : data_(initial_size) , count_(0)
  { }

  randomaccesstable &push_back(const Elem &elem)
  {
    if (count_ < data_.size())
      data_[count_++] = elem;
    else {
      data_.push_back(elem);
      ++count_;
    }
    return *this;
  }

  randomaccesstable &remove(const std::size_t index)
  {
    if (index < count_)
    {
      std::swap(data_[index],data_[count_-1]);
      --count_;
    }
    return *this;
  }

  const Elem &operator[](const std::size_t index) const
  { return data_[index]; }

  Elem &operator[](const std::size_t index)
  { return data_[index]; }

  std::size_t size() const
  { return count_; }

private:
  std::vector<Elem>  data_;
  std::size_t        count_;
};

int main()
{
  randomaccesstable<int> table(10);
  table.push_back(3);
  table.push_back(12);
  table.push_back(2);

  for (std::size_t i = 0 ; i < table.size() ; ++i)
    std::cout << table[i] << ' ';
  std::cout << '\n';

  table.remove(1);   // this removes the entry for 12, swapping it for 2

  for (std::size_t i = 0 ; i < table.size() ; ++i)
    std::cout << table[i] << ' ';
  std::cout << '\n';

  return 0;
}

Swivet

Answer 2

I would suggest using hash table. There you can both delete and lookup element with constant complexity. In C++ you may use std::unordered_map(C++11) or boost::unordered_map(pre-C++11) and in java - HashMap.

Shroff

Thanks, could you please give me some more explanations or references about them? I have no idea about them unfortunately. – Cramp

@TomerArazy on average and assuming you have a good enough hash function, true. – Shroff

Thanks a lot. I got a little bit confused as I guess an unordered_map (or for simplicity a map if we neglect the factor of log(n) difference in the operations) stores two values (a key and a value) while I only need to store a bunch of single values. – Cramp

Let's assume I first put 10 elements of 0,1,...,9 in the map<int,int> s; (for example in the order of s[i] = i). Then if I want to choose one in random I can easily generate a random number in {0,1,...,9} r and then access s[r]. But what if I remove a few of them, e.g. 4th and 8th element. Now how can I randomly choose one of the remaining 8th elements? Now I need to generate a random number in {0,1,...,9} \ {3,7} which is not easy. – Cramp

@ManiBastaniParizi maybe I misunderstood the question. For your use case unordered_set – Shroff