Inserting an element into an ordered vector/list
-
Is it possible to insert an element directly into it's 'right' place in an ordered vector, instead of using push_back() and then sort()? If not, is it possible with a list? Thanks, Avi.
-
Is it possible to insert an element directly into it's 'right' place in an ordered vector, instead of using push_back() and then sort()? If not, is it possible with a list? Thanks, Avi.
You can use insert, but you have to march through the vector/list to find the correct location to place it. Alternatively, you can use the set template which will always be sorted (but requires uniqueness) or multiset (which will be sorted and stores non-unique items in a vector at each location).
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week Zac
-
You can use insert, but you have to march through the vector/list to find the correct location to place it. Alternatively, you can use the set template which will always be sorted (but requires uniqueness) or multiset (which will be sorted and stores non-unique items in a vector at each location).
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week Zac
Thanks, but maybe it will be better to keep it a vector and use the algorithm find_if() (just foun out about it...) and then insert() Avi.
-
Thanks, but maybe it will be better to keep it a vector and use the algorithm find_if() (just foun out about it...) and then insert() Avi.
That all depends on what you are using it for, so whatever solution that works best for what your project needs is the one you should use (just make sure have a reason for picking a particular solution over another).
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week Zac
-
Is it possible to insert an element directly into it's 'right' place in an ordered vector, instead of using push_back() and then sort()? If not, is it possible with a list? Thanks, Avi.
Use
std::lower_boundfollowed bystd::vector::insert. e.g.using namespace std; vector<int> vec; // Fill vector. It's sorted. int newval = 5; vec.insert(lower_bound(vec.begin(), vec.end(), newval), newval);Steve
-
Thanks, but maybe it will be better to keep it a vector and use the algorithm find_if() (just foun out about it...) and then insert() Avi.
find_ifis a bad choice if thevectoris sorted as you'll get linear performance instead of logarithmic (for the search). Usestd::lower_boundinstead.Steve
-
Is it possible to insert an element directly into it's 'right' place in an ordered vector, instead of using push_back() and then sort()? If not, is it possible with a list? Thanks, Avi.
You often need to add or remove from the end? You need it only occational but in time critical situations? You do need the guarantee that your items are stored in adjacent places? (Double-use of
&vec[0]as a C-Array for example) Then use thevector/lower_boundStephen Hewitt proposed If you only need a sorted storage, you would be better off with set/multiset.
"We trained hard, but it seemed that every time we were beginning to form up into teams we would be reorganised. I was to learn later in life that we tend to meet any new situation by reorganising: and a wonderful method it can be for creating the illusion of progress, while producing confusion, inefficiency and demoralisation." -- Caius Petronius, Roman Consul, 66 A.D.
-
Use
std::lower_boundfollowed bystd::vector::insert. e.g.using namespace std; vector<int> vec; // Fill vector. It's sorted. int newval = 5; vec.insert(lower_bound(vec.begin(), vec.end(), newval), newval);Steve
Thanks Steve, This is exactly what I was looking for. :cool: Avi.