CODEWITHSUNDEEP
c++sortingvectortypes
node ninja
node ninja

Reputation: 32986

A data type like vector but sorted

Is there a data type like vector or queue where you can easily add items, but when they get added, they are automatically inserted in the right order?

Also is there an easy way to delete an item from a vector or queue if you know what it is, without having to actually search through and find it?

Upvotes: 1

Views: 417

Answers (4)

ereOn
ereOn

Reputation: 55726

I know no such container.

std::sort exists, in which you can specifiy the sorting function, but it is often even more efficient to actually insert items in the right place directly.

If you always do that, the only "problem" you have to solve is to add an item into an already sorted list, which can be done at worst in linear time.

Note that std::vector<T>::insert() takes an iterator as a parameter, to indicate where to do the insertion. You might want to write a findPosition() methods that returns such an iterator. Then, writing an sorted_insert() method is trivial and becomes something like:

std::vector<int>::iterator findPosition(int v);
void sorted_insert(std::vector<int>& vec, int v) { vec.insert(findPosition(v), v); }

void foo()
{
  std::vector<int> vec;
  sorted_insert(vec, 4);
}

Upvotes: 2

Kiril Kirov
Kiril Kirov

Reputation: 38153

Depends on what you need and why do you need it.

No, in the standard lib, there's no "sorted" vector or queue. You have 2 options, if you want to use only the standard library:

  • sort the container(vector or queue) on each insertion/deletion
  • implement your own insert/delete, by implementing the insertion sort

Other option is to use map or set, if they'll be OK for your problem (as we don't know what it is)

The other option is to look for some 3rd party lib - I guess boost will have such container, but I don't really know that.

"Also is there an easy way to delete an item from a vector or queue if you know what it is" - what do you mean by that? You have an iterator to it or ? Or its index? I'll edit my answer when you update (:

Upvotes: 0

edA-qa mort-ora-y
edA-qa mort-ora-y

Reputation: 31851

It sounds like you are looking for a set and not a vector. It will be sorted according to the natural ordering (the < operator). To remove an element by value call erase.

Alternately you can just use sort on a vector to sort the elements. If you need random access to the elements then you will want this approach; the sorted containers do not provide random access.

To find an element in a sorted vector you can use binary_search.

Upvotes: 1

GManNickG
GManNickG

Reputation: 503805

Sounds like you want std::set or std::multi_set.

Upvotes: 2

Related Questions