use map in place of vector

Question

I am extending an already existing C++ code. One of the class members is of type vector of another class objects:

class Road
{
  ....
  vector<Link*> links;  //Link is just another class
}

The other modules use this class and its member through a lot of sequence iterators. Now, while extending the code, I need to add a member to Link class called linkID, and use this linkID to find/access my "Link" objects.

Problem: I am not going to search for a Link object(using LinkID) in the vector by iterating through the millions of items, just to find a specific Link object. The best solution is "map"! right?

....
map<linkID,*link> links
....
lnk=links[linkID]
.........

But the problem is that i cannot modify the current source code except very minor modifications lik adding linkID etc.

So my obvious question is: is it possible to use map in place of vector(any how). In the other words, I want to create a map, fill it up, and later treat it as a vector. possible? Thank you for your comments

As long as the code you have is implemented cleverly, i.e: Not relying on random iterator behavior of `std::vector` just changing the type should do the trick.Ofcourse, You would eventually have to revisit all instances where you rely on sequential nature of the container but then you can't help it, if the existing code relys on this behavior it is badlywritten in the first place. — Alok Save, Mar 09 '12 at 07:35
I agree with Als above. It's more than just random iterator behavior though. For example, is the code doing anything like `links.push_back(ptr)`? Also, is the code relying on positionally accessing the links? — Kaz, Mar 09 '12 at 07:43
@KAZ FYI, linkID is a string like "lnk001" coming from XML and going to be used later as a DB table's PK. — rahman, Mar 09 '12 at 07:49
@Als: do you mean I typecast map to vector? (initialy fill out the map and then treat it as a vector?) is it possible? could you give me an example please? — rahman, Mar 09 '12 at 07:50

score 0 · Answer 1 · answered Mar 09 '12 at 07:37

The best solution is "map"! right?

Yes, sounds like the map is the simplest solution to your problem. But instead of using operator[], I'd use find and insert methods.

Initially, you can change the code to use the map of this type std::map< unsigned int, link* >, because that is the most similar to a vector< link* >. Then you can easily switch to std::map< LinkId, link* >.

jogojapan · Answer 2 · 2012-03-09T07:56:03.300

0

Disguising a map as vector is not possible as such.

In theory, you could try to implement a new class that is derived from vector (i.e. uses std::vector as base class). Internally it could use a map, and to the outside it would have the interface of a vector (and it would be accepted as a replacement for the vector because it is derived of it).

In practice you might encounter a number of problems, though. You would obviously inherit the internal data structures of the vector, too, so you would have to ignore them in your implementation, i.e. leave them empty. Deriving from STL classes (except basic_ ones) is also against recommended practice and possibly risky, as @Als points out in the comment below.

If there is a chance to avoid this by rewriting a larger portion of the existing code, you should do that. But if unavoidable, using inheritance might work.

edited Mar 09 '12 at 07:56

answered Mar 09 '12 at 07:37

jogojapan

68,383
11
101
131

2

Standard Library containers are not meant to act as Base classes, they do not have a virtual destructor, So this is a bad advice.If et all best is to use composition and not inheritance when dealing with standard library container classes. – Alok Save Mar 09 '12 at 07:40
@Als Yes, but if you simply replace vector with map, you'd have to change a great part of the source code, e.g. because the iterators map returns are totally different from those returned by vector. That is what the OP wants to avoid (or has to avoid). – jogojapan Mar 09 '12 at 07:42
@Als wouldn't that only be a problem if he had std::vector* vp = new MyDerivedClass? Private inheritance would be safe (I'm not saying it would be the right solution though) – juanchopanza Mar 09 '12 at 09:11
@juanchopanza: Yes, You might want to have a look [here](http://stackoverflow.com/questions/6806173/why-should-not-i-subclass-inherit-standard-containers) though. – Alok Save Mar 09 '12 at 09:16

score 0 · Answer 3 · answered Mar 09 '12 at 07:49

I think what you might be able to do is make an augmented data structure: a vectormap which allows you to have keyed access to the items by linkID and which also supports the operations of std::vector. The [] operator of this object could be overloaded so that links[3] gives you positional access to the vector and links[linkID] looks up a link ID in the map. Things like push_back can be supported, if the code needs them: push_back would have to push the element into the vector, and then also do a map[item->linkID] = item to enter it into the map. You probably get the picture.

wow! I can't figure out how but I will just start giving it a try and come back to you later. — rahman, Mar 09 '12 at 07:53

score 0 · Answer 4 · answered Mar 09 '12 at 09:25

I did this many moons ago for the rail network. The base classes were link and node. The actual rail and eventually routes were based on top of these. IIRC I used std::list to contain links and nodes and used vectors of vectors for containing the actual tracks.

score 0 · Answer 5 · answered Mar 09 '12 at 10:09

0

The proper solution, if linkID is a member of Link, would be std::set<Link*, OrderByLinkID>. The OrderByLinkID predicate would take two Link* and return true iff the first has a smaller linkID member.

The result is that the std::set still contains Link*, and you can iterate over them just like std::vector. In comparison, with std::map you'd end up iterating over std::pair<Link*, LinkID> which is a much bigger change.

answered Mar 09 '12 at 10:09

MSalters

173,980
10
155
350

Hi, I hope you are still following this. I need to know how fast would be a lookup in your "set" solution? The main reason i am doing this is to be able to fast lookup the Link(or any other object) will this solution e faster than map? – rahman Mar 23 '12 at 10:39
Both are `O(log N)`. Vector is `O(N)`, in comparison. – MSalters Mar 23 '12 at 12:26

use map in place of vector

5 Answers5