#create an set from vector (time complexity)

28 messages · Page 1 of 1 (latest)

south cove
#

What is the time complexity to create a set from a vector

elder fjordBOT
#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question run !howto ask.

cloud remnant
#

You have to copy the elements element by element one time, thus O(N)

cloud mural
#

so it would be O(N log N)

cloud remnant
#

tfw you forget how sets work

#

wait

cloud mural
#

unordered_set is probably a hash map

cloud remnant
#

wouldnt it still be order N though

#

wait

cloud mural
#

no

cloud remnant
#

let me think about this

cloud mural
#

it's N operations and each is log N

#

that's N log N

cloud remnant
#

yea, what happens to a mf when you never need to think about complexities

cloud mural
#

std::set is a tree, std::unordered_set is a hash map

cloud remnant
#

ohh

#

yup thats it

cloud mural
#

so creating an unordered_set from a vector is potentially O(n) but creating a set is O(n log n)

cloud remnant
#

This still leads to my question, why does the standard comittee give these awful names to this stuff

#

why not just call it std::Tree

cloud mural
#

lots of things are trees ._.

#

heap is a tree

#

std::map is a tree

#

"tree" is a useless name, might as well just call it "structure"

cloud remnant
#

Yea, I'm just wrong here aren't I 😛

elder fjordBOT
#

This question thread is being automatically closed. If your question is not answered feel free to bump the post or re-ask. Take a look at !howto ask for tips on improving your question.