CODEWITHSUNDEEP
c++treec++17stdmap
darune
darune

Reputation: 11000

Can a map be used as a tree?

eg. std::map<Item, std::vector<Item> >.

Would that be able serve as a "quick-and-dirty" tree structure (with some helper functions on top and given that less is implemented for Item), given that theres none in the std/boost ?

Would a std::unordered_map be better suited/more usefull/beneficial ? that requires a hash instead of compare though - which can be harder to implement.

I can see one issue though, finding parent/owner have to brute force go through the entire map (although that might be best stored in seperate structure if needed).

Another thing Im not so fond of is the sort of dual meaning of a map entry with an Item with an empty child list.

Upvotes: 4

Views: 846

Answers (2)

Daniel McLaury
Daniel McLaury

Reputation: 4273

You can absolutely represent a tree in this manner; whether it's a good idea in a given situation depends entirely on which operations you need to be fast, which operations you're okay with being slow, and what your space requirements are.

(And of course in many applications the answer to all of the above may be "I don't care," in which case any implementation is probably fine.)

Upvotes: 0

eerorika
eerorika

Reputation: 238401

Can a map be used as a tree?

Situation is inverse: std::map is internally implemented using a tree. So tree can (is) used as a map.

Neither map nor unordered map are useful for implementing a general tree structure. Only if your intention is to use the tree as a map would it be useful to use these structures (because they are maps which was desirable in this scenario)

Upvotes: 1

Related Questions