CODEWITHSUNDEEP
c++vector
tmighty
tmighty

Reputation: 11409

C++ index-to-index map

I have a list of IDs (integers). They are sorted in a really efficient way so that my application can easily handle them, for example

9382
297832
92
83723
173934

(this sort is really important in my application).

Now I am facing the problem of having to access certain values of an ID in another vector.

For example certain values for ID 9382 are located on someVectorB[30].

I have been using 

const int UNITS_MAX_SIZE = 400000;

class clsUnitsUnitIDToArrayIndex : public CBaseStructure
{
private:
    int m_content[UNITS_MAX_SIZE];
    long m_size;
protected:
    void ProcessTxtLine(string line);
public:
    clsUnitsUnitIDToArrayIndex();
    int *Content();
    long Size();
};

But now that I raised UNITS_MAX_SIZE to 400.000, I get page stack errors, and that tells me that I am doing something wrong. I think the entire approach is not really good.

What should I use if I want to locate an ID in a different vector if the "position" is different?

ps: I am looking for something simple that can be easily read-in from a file and that can also easily be serialized to a file. That is why I have been using this brute-force approach before.

Upvotes: 0

Views: 1009

Answers (3)

fatihk
fatihk

Reputation: 7929

Probably you are getting stackoverflow error due to int m_content[UNITS_MAX_SIZE]. The array is allocated on the stack and 400000 is a pretty big number for the stack. You can use std::vector instead, it is dynamically allocated and you can return a reference of vector member to avoid copy operation:

std::vector<int> m_content(UNITS_MAX_SIZE);

const std::vector<int> &clsUnitsUnitIDToArrayIndex::Content() const
{
   return m_content;
}

Upvotes: 1

Jake Woods
Jake Woods

Reputation: 1828

If you want a mapping from int's to int's and your index numbers non-consecutive you should consider a std::map. In this case you would define it as such:

std::map<int, int> m_idLocations;

A map represents a mapping between two types. The first type is the "key" and is used for lookup up the second type known as the "value". For each id lookup you can insert it with:

m_idLocations[id] = position;
// or
m_idLocations.insert(std::pair<int,int>(id, position));

And you can look them up using the following syntax:

m_idLocations[id];

Typically a std::map in the stl is implemented using red-black trees which have a worse-cast lookup speed of O(log n). This is slightly slower then O(1) that you'll be getting from the huge array however it's a substantially better use of a space and you're unlikely to notice the difference in practise unless you're storing truly gigantic amounts of numbers or doing an enourmous amount of lookups.

Edit:

In response to some of the comments I think it's important to point out that moving from O(1) to O(log n) can make a significant difference in the speed of your application not to mention practical speed concerns from moving to fixed blocks of memory to tree based structure. However I think that it's important to initially represent what you're trying to say (an int-to-int) mapping and avoid the pitfall of premature optimization.

After you've represented the concept you should then use a profiler to determine if and where the speed issues are. If you find that the map is causing issues then you should look at replacing your mapping with something that you think will be quicker. Make sure to test that the optimization helped and don't forget to include a big comment about what you are representing and why it needed to be changed.

Upvotes: 3

weima
weima

Reputation: 4912

if nothing else works you can just allocate the array dynamically in the constructor. this will move the large array on the heap and avoid your page stack error. you should also remember to release the resource while destroying your clsUnitsUnitIDToArrayIndex

But the recommended usage is as suggested by other members, use a std::vector or std::map

Upvotes: 1

Related Questions