c++ - how do you insert the value in a sorted vector? -

all,

this question continuation of this one. think stl misses functionality, imho.

now, question.

consider following code:

class foo { public:     foo(); ........... private:     int parama, paramb;     std::string name; };  int main() {     std::vector<foo> foo;     sorter sorter;     sorter.paramsorter = 0;     std::sort( foo.begin(), foo.end(), sorter ); }  struct sorter {     bool operator()(const foo &foo1, const foo &foo2)     {          switch( paramsorter )          {              case 0:                  return foo1.name < foo2.name;              case 1:                  return foo1.parama < foo2.paramb;              case 2:                  return foo1. parama > foo2.paramb;          }     } private:     int paramsorter; } 

at given moment of time vector can re-sorted. class have getter methods used in sorter structure.

what efficient way insert new element in vector?

situation have is:

i have grid (spreadsheet), uses sorted vector of class. @ given time vector can re-sorted , grid display sorted data accordingly.

now need insert new element in vector/grid. can insert, re-sort , re-display whole grid, inefficient big grid.

any appreciated.

the simple answer question:

template< typename t > typename std::vector<t>::iterator     insert_sorted( std::vector<t> & vec, t const& item ) {     return vec.insert         (              std::upper_bound( vec.begin(), vec.end(), item ),             item          ); } 

version predicate.

typedef< typename t, typename pred > typename std::vector<t>::iterator     insert_sorted( std::vector<t> & vec, t const& item, pred pred ) {     return vec.insert         (             std::upper_bound( vec.begin(), vec.end(), item, pred ),            item          ); } 

where pred strictly-ordered predicate on type t. work input vector must sorted on predicate.

the complexity of doing o(log n) upper_bound search (finding insert) o(n) insert itself.

for better complexity use std::set<t> if there not going duplicates or std::multiset<t> if there may duplicates. these retain sorted order automatically , can specify own predicate on these too.

there various other things more complex, e.g. manage vector , set / multiset / sorted vector of newly added items merge these in when there enough of them. kind of iterating through collection need run through both collections.

using second vector has advantage of keeping data compact. here "newly added" items vector relatively small insertion time o(m) m size of vector , might more feasible o(n) of inserting in big vector every time. merge o(n+m) better o(nm) inserting 1 @ time, in total o(n+m) + o(m²) insert m elements merge.

you keep insertion vector @ capacity too, grow not doing reallocations, moving of elements.