1

I need a data structure in which each element has a specific index but can also be retrieved using a key.

I need that data structure for model-view Programming in Qt. On the one hand, the View asks for an element in a specific row. On the other hand, the model wants to insert and modify elements with a given key. Both operations should run in O(1).

Here is an example of what I want:

The View sees the following:

list[0]: "Alice", aged 22
list[1]: "Carol", aged 15
list[2]: "Bob", aged 23

The Model sees:

hash["Alice"]: "Alice", aged 22
hash["Bob"]: "Bob", aged 23
hash["Carol"]: "Carol", aged 15

My idea was the following: I have a QList<Value> and a QHash<Key, Value*>. The hash points to the place in the list, where the corresponding element is stored. This is the code to insert/edit values:

if (hash.contains(key))
    *hash[key] = value;
else
{
    int i = list.size();
    list << value;
    hash[key] = &list[i];
}

The problem is that this code does not always work. Sometimes it works as expected, but it happens that the data structure is not consistent any more.
I suspect, it is because QList moves it's content through memory because it allocates new space or something like that.

Operations which are important (should run in expected O(1)):

  • Insert key/value pair (appends the value to the end of the list)
  • Look up and modify a value using a key
  • Look up and modify a value using an index

Other operations which have to be possible, but don't have to be possible in constant run time:

  • Delete an element by index
  • Delete an element by key
  • Insert in the middle of the array
  • Swap elements in the array / sort array
  • Get the index of a key

My two questions are:

  • Is there any data structure which does what I want?
  • If there is not, how could I fix this or is there a better approach?
2
  • Does the index value have to be a 'true' index (i.e. it changes appropriately when items are added to the list), or does it just have to be unique like the QHash keys?
    – cmannett85
    Jul 30, 2012 at 21:45
  • The index has to be a 'true' index. It represents the position of the item in the view.
    – Misch
    Jul 30, 2012 at 22:05

1 Answer 1

2

Approach 1: Instead of the pointer, you can store the list index in the hash. Then you have one more indirection (from the hash, you get the index, then you retrieve from the list), but it is still O(1). The difference in speed should not be too much.

Approach 2: Both the list and the hash operate with pointers. Then they will stay valid. However, deleting based on index or key will become O(n), as you have to find the object manually in the non-corresponding container.

I also wonder how you want to solve the issue of deletion by index or insertion in the middle anyway. In both cases, the hash will point to wrong entries (both in your approach and Approach 1). Here you would be forced to go with Approach 2.

1
  • I just wanted to comment, that delete does not work with Approach 1, but you are right that it can not work for my solution either... I probably haven't even tested that yet, but my problem already happened while inserting. I don't really like the idea of using pointers, but I might have to consider it as the best solution...
    – Misch
    Jul 31, 2012 at 11:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.