[C++] Custom container

[Shawak]

Hey guys,

so i'm in the search of a container which fulfill following criteria:

- add elements sorted with a complexity of O(Nlog(size+N))
- erasing elements at position N with a complexity of O(1)
- returning elements at a range from to with a complexity of O(1)

so it's likely almost the same as the sdt::set<T> or sdt::multiset<T> just returning their elements with a given offset should be possible, any idea how to aquire this?

regards

[atom0s]

Probably best to roll your own.

For sorted adding, std::sort itself guarantees to be O(N log(N)) according to the C++11/14 standards. (Using N == last - first as the comparison.)


For O(1) removal, you can do similar to how vector removal can be done via:
- std::move -> pop_back


This usually is done on an unordered vector of some sort. You can also look into how std::list::erase works as it's guaranteed to be O(1) according to the standards.

[Shawak]

The problem is that a set::set::insert takes O(Nlog(size+N)) where N = number of elements to insert, so if I only want to inset one elemnt it results in O(log(size)). A std::sort takes O(Nlog(N)) where N = std::distance(first, last) which is in comparison way too much, sine my containers contain around 10 million elements.