c++ - Which container should I use to quickly find an element, knowing that by construction it's already ordered? -

i have use container construction ordered , need quick find-function.

my idea use set exploit set.find, should quick enough, constructing set set.insert slow because know elements ordered!

for part, use vector vector.push_back, should write find function myself , slower set::find... suggest me?

edit:

• the container needs modified, ordered, , size same (but don't know priori)
• no repeated values.
• a lot more finds inserts.
• i need know if exists, not position.
• i found std::binary_search. good?

constructing set pair of iterators guaranteed o(n) if input range sorted, use that. (see e.g. http://en.cppreference.com/w/cpp/container/set/set.)

subsequent inserts o(log n).

although if total size not large sorted vector tends beat else because cache friendly. std::binary_search o(log n), same set::find.

std::unordered_set doesn't care ordering, give o(1) lookup (on average, no guarantees).