Simple and effective way to store data that can be accessed though key or ordinal c++

Question

I need to create a data structure that can access elements by a string key, or by their ordinal.

the class currently uses an array of nodes that contain the string key and a pointer to whatever element. This allows for O(n) looping through, or O(1) getting an element by ordinal, however the only way I've found to find an element by key is doing an O(n) loop and comparing keys until I find what I want, which is SLOW when there are 1000+ elements. is there a way to use the key to reference the pointer, or am I out of luck?

EDIT: the by ordinal is not so much important as the O(n) looping. This is going to be used as a base structure that will be inherited for use in other ways, for instance, if it was a structure of draw able objects, i'd want to be able to draw all of them in a single loop

score 5 · Answer 1 · edited May 23 '17 at 12:19

You can use std::map for O(log n) searching speed. View this branch for more details. In this branch exactly your situation (fast retrieving values by string or/and ordinal key) is discussed.

Small example (ordinal keys are used, you can do similiar things with strings):

#include <map>
#include <string>

using std::map;
using std::string;

struct dummy {
 unsigned ordinal_key;
 string dummy_body;
};

int main() 
{
 map<unsigned, dummy> lookup_map;
 dummy d1;
 d1.ordinal_key = 10;
 lookup_map[d1.ordinal_key] = d1;
 // ...
 unsigned some_key = 20;
 //determing if element with desired key is presented in map
 if (lookup_map.find(some_key) != lookup_map.end())
  //do stuff
}

score 1 · Answer 2 · answered May 06 '11 at 06:04

1

If you seldom modify your array you can just keep it sorted and use binary_search on it to find the element by key in O(logn) time (technically O(klogn) since you're using strings [where k is the average length of a key string]).
Of course this (just like using a map or unordered_map) will mess up your ordinal retrieval since the elements are going to be stored in sorted order not insertion order.

answered May 06 '11 at 06:04

Eugen Constantin Dinca

8,994
2
34
51

this seems to be the most time and space effective way right now, thanks for your help – Andrew May 06 '11 at 15:09
@Andrew: it's usually worth checking if processing your current container solves the problem before introducing new containers. – Eugen Constantin Dinca May 07 '11 at 00:02

score 1 · Answer 3 · answered May 06 '11 at 06:04

1

Use vector and map:

std::vector<your_struct> elements;
std::map<std::string, int> index;

Map allows you to retrieve the key's index in O(lg n) time, whereas the vector allows O(1) element access by index.

answered May 06 '11 at 06:04

zvrba

24,186
3
55
65

what would the int be in the map, and how much overhead would this create? – Andrew May 06 '11 at 15:04
The int is the index into the elements vector. – zvrba May 08 '11 at 04:51

score -1 · Answer 4 · edited May 23 '17 at 12:19

-1

Use a hashmap

edited May 23 '17 at 12:19

Community

1
1

answered May 06 '11 at 05:53

QuantumMechanic

13,795
4
45
66

Simple and effective way to store data that can be accessed though key or ordinal c++

4 Answers4