James Kuyper wrote:

> awarren@jws.com wrote:
> > My question is simple: how do you get the functionality of a sorted
> vector
> > with the STL?
>
> That depends; if you need random access iterators, then you'll have to
>
> define your own class. Possibly the simplest way is to derive from
> vector<>, adding an optional Compare function object (the same way the
>
> associative containers do) and add code where needed to keep it
> sorted.

It's worth noting that it's probably better to just contain the vector
instead of inheriting from it.  An object of a derived class should be
usable wherever an object of its public base class is.  (The Liskov
Substitution Principle.)  While reading is identical for both sorts of
vector, writing definitely is not.  The operation v[i] = j doesn't
really make any sense on a sorted vector.

Private derivation wouldn't violate the principle, but it's still pretty
questionable -- the STL classes were not designed to be base classes.

Though it's more work, the right way to do it is to contain the vector
in the sorted vector, and then provide a conversation operator to allow
you to convert the sorted vector to a normal vector which is const.

Sol


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

awarren@jws.com wrote:
>
> For starters, I'm an admitted STL newbie.
>
> I've been using RogueWave's libraries (particularly Tools.h++) for years; I'm
> now trying to use the STL for the same sorts of tasks. RW had provided
> implementations for things like sorted vectors - adding new elements into the
> vector inserted them into the appropriate place automatically. This'd be
> equivalent to using sort(...) after each insertion in the STL.
>
> My question is simple: how do you get the functionality of a sorted vector
> with the STL?

That depends; if you need random access iterators, then you'll have to
define your own class. Possibly the simplest way is to derive from
vector<>, adding an optional Compare function object (the same way the
associative containers do) and add code where needed to keep it sorted.
Since the container is sorted, you could use binary_search() to locate
the appropriate insertion point for each element.

However, if bidirectional iterators are acceptable, then set<> does
exactly what you need, and with much less overhead per insert()/erase().
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

For starters, I'm an admitted STL newbie.

I've been using RogueWave's libraries (particularly Tools.h++) for years; I'm
now trying to use the STL for the same sorts of tasks. RW had provided
implementations for things like sorted vectors - adding new elements into the
vector inserted them into the appropriate place automatically. This'd be
equivalent to using sort(...) after each insertion in the STL.

My question is simple: how do you get the functionality of a sorted vector
with the STL?

Thanks,
Herb.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/   Now offering spam-free web-based newsreading
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <6gt42i$nm1$1@nnrp1.dejanews.com>,  <awarren@mint.net> wrote:
>I've been using RogueWave's libraries (particularly Tools.h++) for years; I'm
>now trying to use the STL for the same sorts of tasks. RW had provided
>implementations for things like sorted vectors - adding new elements into the
>vector inserted them into the appropriate place automatically. This'd be
>equivalent to using sort(...) after each insertion in the STL.

The equivalent structure in STL is called multiset<T>.  It maintains
elements in sorted order and there can be multiple copies of the same
element.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]