Emulating map with a sorted vector
Scott Meyers
because
there is a standards question as well as a workaround question.]
In his column in the April 2000 C++ Report, Matt Austern explains how
a
sorted vector may sometimes be a better choice than a set. I've been
trying to extend his reasoning to argue that a sorted vector<pair<K,V>
>
may sometimes be better than a map<K, V>.
If I have a sorted vector<T> and I want to search it using lower_bound
and
a custom comparison function, the signature of the comparison function
is
expected to be this, more or less:
bool compFunc(const T& lhs, const T& rhs); // return whether lhs
precedes
// rhs in the sort
order
When T is pair<K, V>, that means we expect the comparison function to
look
more or less like this:
bool compFunc(const pair<K, V>& lhs, const pair<K, V>& rhs);
The problem is that if I'm emulating map/multimap semantics, I don't
want
to compare a pair<K, V> and a pair<K, V>, I want to compare a K and a
K,
because maps look only at keys when searching.
While it's running, lower_bound compares a given value with a value it
finds in a range. With a custom comparison function, there is no
reason
why the type of the given value must be the same as the type of the
value
in the range. In my case, I want to compare a type K (a specific key
value) with an object of type pair<K, V> (a value from a
vector<pair<K, V> >). That suggests I should be able to declare my
comparison function as follows:
bool compFunc(const pair<K, V>& p, const K& v);
>From what I can tell, the standard neither explicitly allows nor explicitly
prohibits this, so I wrote the following program to see if it would
compile. (I don't care if it runs, only if it compiles.)
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
using std::vector;
using std::pair;
using std::string;
using std::lower_bound;
typedef vector<pair<int, string> > MapVec;
bool keyCompare(const pair<int, string>& p, int val);
int main()
{
MapVec mv;
lower_bound(mv.begin(), mv.end(), 10, keyCompare); // all I care
about
} // is whether
this
// call
compiles
I was hoping that all my platforms would accept this, because that way
I
could sleep soundly at night after telling people they could consider
doing
this kind of thing. Of the five platforms I tested, four compiled it,
but
one did not. As I said, I believe both results are conforming, but
I'd
appreciate others' readings of the matter.
You may wonder why I care. I want to be able to search the sorted
vector
of pairs using lower_bound and a comparison function. If the
comparision
function must compare two pair objects, that means I have to construct
a
pair, even though I may have only a key value. This is not only
awkward,
it may also engender a performance penalty for the construction of the
superfluous value part of the pair. In my code above, for example,
I'd
have to turn an int into a pair<int, string>, and that would require
that I
construct a string I will never use. I want to avoid the awkwardness
and
the possible performance penalty.
If I can't use my asymmetric comparison function above, is there a
better
alternative to writing my own function to perform binary search? Such
a
function would be almost identical to the algorithms binary_search and
lower_bound, so I'd prefer to avoid that if I can.
Thanks,
Scott
--
I've scheduled more public seminars. Check out
http://www.aristeia.com/seminars/ for details.
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]
Christopher Eltschka
What about replacing this with the "symmetric" comparision object
struct KeyCompare
{
// compare pair with int
bool operator()(const pair<int, string>& p, int val) const;
// compare int with pair
bool operator()(int val, const pair<int, string> const& p) const;
// compare pair with pair (in case the algorithm wants to
// compare two elements of the container - I don't think it will,
// but I also don't think it may not do that)
bool operator()(const pair<int, string>& p1,
const pair<int, string>& p2) const;
// compare int with int (yes, I'm paranoid here ;-))
bool operator()(int, int) const;
};
Then use
lower_bound(mv.begin(), mv.end(), 10, KeyCompare());
I'm not 100% sure this is conforming, but I don't see how this
could fail.
[...]
Alex Oren
} [I'm posting this to both comp.std.c++ and comp.lang.c++.moderated,
} because
} there is a standards question as well as a workaround question.]
}
} In his column in the April 2000 C++ Report, Matt Austern explains how
} a
} sorted vector may sometimes be a better choice than a set. I've been
} trying to extend his reasoning to argue that a sorted vector<pair<K,V>
} >
} may sometimes be better than a map<K, V>.
I noticed that in comp.std.c++ Scott's post looks OK while here it is
mangled. Could we do away with the forced wraparound? It seems to cause
more troubles than it is worth, especially when it wraps at N columns posts
that were already wrapped at N+1. Nobody reads from a VT100 anymore.
BTW, my post looked OK wrapped at 76 columns, it is interesting what it
looks like now...
Have fun,
Alex.
--
My email address is intentionally mangled to foil spambots.
Please remove the "---filter---" from the address for replying.
Sorry for the inconvenience.
David Abrahams
"Christopher Eltschka" <celt...@physik.tu-muenchen.de> wrote in message
news:39D22732...@physik.tu-muenchen.de...
> What about replacing this with the "symmetric" comparision object
>
> struct KeyCompare
> {
> // compare pair with int
> bool operator()(const pair<int, string>& p, int val) const;
>
> // compare int with pair
> bool operator()(int val, const pair<int, string> const& p) const;
>
> // compare pair with pair (in case the algorithm wants to
> // compare two elements of the container - I don't think it will,
> // but I also don't think it may not do that)
> bool operator()(const pair<int, string>& p1,
> const pair<int, string>& p2) const;
>
> // compare int with int (yes, I'm paranoid here ;-))
> bool operator()(int, int) const;
> };
>
> Then use
>
> lower_bound(mv.begin(), mv.end(), 10, KeyCompare());
>
> I'm not 100% sure this is conforming, but I don't see how this
> could fail.
It's more than conforming; it's overkill ;->...probably even if you're
working with Scott's broken library. For Scott's dillemma, you probably only
need the top two functions.
-Dave
Dietmar Kuehl
In article <MPG.143ab9332...@news.supernews.com>,
Scott Meyers <sme...@aristeia.com> wrote:
> #include <vector>
> #include <string>
> #include <utility>
> #include <algorithm>
>
> using std::vector;
> using std::pair;
> using std::string;
> using std::lower_bound;
>
> typedef vector<pair<int, string> > MapVec;
>
>
> int main()
> {
> MapVec mv;
> lower_bound(mv.begin(), mv.end(), 10, keyCompare);
> }
> If I can't use my asymmetric comparison function above, is there a
> better alternative to writing my own function to perform binary
> search? Such a function would be almost identical to the algorithms
> binary_search and lower_bound, so I'd prefer to avoid that if I can.
The only reason I can see why this code might be rejected is the rather
vague statement that the sequence has to be in order according to the
explicit comparison object: What does it mean for a sequence of
'std::pair<int, std::string>' to be in order according to a comparison
object comparing an 'std::pair<int, std::string>' to an 'int'? Of
course, looking at the arguments, this can be immediately answered but
it requires an interpretation which is not covered by the standard.
On the other hand, the description is obviously kept deliberately
informal because in similar contexts things like
comp(it, it + 1) yields true for all it in [beg, end - 1)
are stated. This is not the case here. Thus, I would claim that a
conforming compiler is supposed to accept your code.
That said, there is, of course, an appropriate solution otherwise, too:
Just use a generic wrapper for the iterators which selects 'first' in
it's 'operator*()':
bool keyCompare(int i1, int i2);
template <class It>
class iter1st:
std::iterator<typename std::iterator_traits<It>::iterator_category,
typename std::iterator_traits<It>::value_type::first_type,
typename std::iterator_traits<It>::difference_type>
{
public:
typedef std::iterator_traits<It> traits;
typedef typename traits::iterator_category iterator_category;
typedef typename traits::value_type::first_type value_type;
typedef typename traits::difference_type difference_type;
typedef typename traits::value_type::first_type* pointer_type;
typedef typename traits::value_type::first_type& reference_type;
iter1st(It const& it = It()): b(it) {}
// copy ctor, copy assignment, dtor are just fine
It base() const { return b; };
bool operator== (iter1st const& i) const { return b == i.b; }
bool operator!= (iter1st const& i) const { return b == i.b; }
bool operator<= (iter1st const& i) const { return b <= i.b; }
bool operator>= (iter1st const& i) const { return b >= i.b; }
bool operator< (iter1st const& i) const { return b < i.b; }
bool operator> (iter1st const& i) const { return b > i.b; }
value_type& operator* () const { return b->first; }
value_type* operator->() const { return &(b->first); }
value_type& operator[] (difference_type n) { return b[n].first; }
iter1st& operator++ () { ++b; return *this; }
iter1st operator++ (int) { return b++; }
iter1st& operator-- () { --b; return *this; }
iter1st operator-- (int) { return b--; }
iter1st& operator+= (difference_type n) { b += n; return *this; }
iter1st& operator-= (difference_type n) { b -= n; return *this; }
difference_type operator- (iter1st const& it) { return b - it.b; }
private:
It b;
};
template <class It>
iter1st<It> operator+ (iter1st<It> it,
typename iter1st<It>::difference_type n) {
return it += n;
}
template <class It>
iter1st<It> operator+ (typename iter1st<It>::difference_type n,
iter1st<It> it) {
return it += n;
}
template <class It>
iter1st<It> operator- (iter1st<It> it,
typename iter1st<It>::difference_type n) {
return it -= n;
}
template <class It>
iter1st<It> first_it(It const& it) { return it; }
int main()
{
MapVec mv;
lower_bound(first_it(mv.begin()), first_it(mv.end()),
10, keyCompare);
}
This ain't pretty. ... but it works :-) Also, it shows a third
alternative neither requiring construction of a pair nor implementation
of additional algorithms. In addition, wrappers like these are useful
in other contexts, too.
--
<mailto:dietma...@yahoo.com> <http://www.dietmar-kuehl.de/>
Sent via Deja.com http://www.deja.com/
Before you buy.
Dietmar Kuehl
In article <65m4ts4h2dkhgoi8a...@4ax.com>,
alexo@bigfoot---filter---.com (Alex Oren) wrote:
> On 27 Sep 2000 07:48:34 -0400, Scott Meyers <sme...@aristeia.com>
wrote:
> mangled. Could we do away with the forced wraparound?
Probably not: The process of handling each article involves mailing the
article to one of the moderators who goes over the article, potentially
adds eg. a moderator's comment, and then sents it to the moderation
site where the article gets injected into the news system. The criticle
step is sending the article back to the moderation site: Some mailers
insist on wrapping long lines or can be configured to do this. However,
the wrapping policy is not always under the control of the moderator.
Apparently, the mailer used by the moderator who handled this
particular article does some line wrapping.
> It seems to cause more troubles than it is worth, especially when it
> wraps at N columns posts that were already wrapped at N+1. Nobody
> reads from a VT100 anymore.
First of all, the last statement is not exactly true: I'm reading from
an xterm which is basically [an extended] VT100 emulation, at least I'm
doing this occasionally (and if the news software were correctly set up
at the site I'm working, I would love to use this again...). In
addition, it is not a feature of the moderation software. This just
happens somewhere in the processing. The moderation software does not
do any line wrapping and I think eg. the article I'm moderating are not
line wrapped. This was different when I was forced to use a certain
mailer which I hated to use...
Anders Pytte
abra...@mediaone.net wrote on 9/27/00 6:25 PM:
>
> "Christopher Eltschka" <celt...@physik.tu-muenchen.de> wrote in message
> news:39D22732...@physik.tu-muenchen.de...
>
>> What about replacing this with the "symmetric" comparision object
>>
>> struct KeyCompare
>> {
>> // compare pair with int
>> bool operator()(const pair<int, string>& p, int val) const;
>>
>> // compare int with pair
>> bool operator()(int val, const pair<int, string> const& p) const;
>>
>> // compare pair with pair (in case the algorithm wants to
>> // compare two elements of the container - I don't think it will,
>> // but I also don't think it may not do that)
>> bool operator()(const pair<int, string>& p1,
>> const pair<int, string>& p2) const;
>>
>> // compare int with int (yes, I'm paranoid here ;-))
>> bool operator()(int, int) const;
>> };
>>
>> Then use
>>
>> lower_bound(mv.begin(), mv.end(), 10, KeyCompare());
>>
>> I'm not 100% sure this is conforming, but I don't see how this
>> could fail.
>
> It's more than conforming; it's overkill ;->...probably even if you're
> working with Scott's broken library. For Scott's dillemma, you probably
only
> need the top two functions.
Yes but it is nice because the same functor can be used for sorting the
vector as for searching - and for simply comparing two keys. It provides an
encapsulation that helps ensure all comparisons on the vector and its keys
are consistent.
Thanks Scott Meyers and Christopher Eltschka - I have a use for this!
Anders.
--
Anders Pytte Milkweed Software
PO Box 32 voice: (802) 586-2545
Craftsbury, VT 05826 email: and...@milkweed.com
fzh...@my-deja.com
Anders Pytte <and...@milkweed.com> wrote:
[snip]
> Yes but it is nice because the same functor can be used for sorting
the
> vector as for searching - and for simply comparing two keys. It
provides an
> encapsulation that helps ensure all comparisons on the vector and its
keys
> are consistent.
>
> Thanks Scott Meyers and Christopher Eltschka - I have a use for this!
>
Don't do this.
I believe that the input range to lower_bound
must be ordered by the same comparator, even
Christophe's solution can compile, it's just
semantically wrong.
I prefer Dietmar's solution in other posting.
e.g. using a wrapper iterator to adapt the
vector<pair<int, string> >::iterator.
Regards
Frank
> Anders.
>
> --
> Anders Pytte Milkweed Software
> PO Box 32 voice: (802) 586-2545
> Craftsbury, VT 05826 email: and...@milkweed.com
>
> [ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
> [ about comp.lang.c++.moderated. First time posters: do this! ]
>
>
Sent via Deja.com http://www.deja.com/
Before you buy.
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Tim Butler
for lookups in the container. His iter1st class wouldn't work for sorting
where you have to do both comparisons and swaps through the iterator.
Perhaps I am missing some fancy "compare through one iterator and swap
through another" algorithm (half-seriously :)
Christopher Eltschka's KeyCompare with the overloaded operator()'s
seems a good candidate for templatization on K,T, AND and key equality
function. It seems annoying that a client would have to provide this
all of the time though. At the very most, a client should only have to
provide a key comparison function.
I realize I am setting myself up for some serious criticism but how
about using a replacement for std::pair that has a conversion operator
to the key type, K. (see below)
I argue that mv_pair will never be used for
another purpose so it is unlikely to participate in unintended conversions.
Okay, it is a poor argument. Someone might come along and think they
are comparing the mapped type along with the key type. But then again, they
could forget to supply the KeyCompare argument to whatever algorithm they
are using on the container. Still, the conversion operations are risky, so
I should be embarrased suggesting such a thing.
mv_pair has the same requirements for a pair except that the mapped type, T,
does not participate in any comparisons. A solution must not impose a
comparison requirement on the mapped type.
mv_pair can participate in sorting and lookups. Default comparisions do
what you expect through conversion to the key type.
mv_pair should really be a mv_pair<const K, T> but this won't work because
both the sort and the vector require the value to be assignable
I am trying to imagine a container that could use a vector but still
maintain the concept of a Pair Associative Container. Maybe clients could
see a mv_pair<const K, T> but mutative operations could see a mv_pair<K,T>
-- probably pure fantasy. It seems like I should be able to cast from the
non-const to the const flavor but I probably can't.
I reckon it would be more elaborate and less portable than Scott wants.
Still, it might be worth wrapping the solution up as a Container so the
client wouldn't have to worry about the details of whatever solution
Scott comes up with.
///////////////////////////////////////////////////////////////
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
using std::pair;
using std::vector;
using std::string;
// mv_pair - a clone of std::pair with the following differences
// 1. has a conversion operator to a const reference of type K (first)
// 2. Comparisions do not consider the mapped type T (second)
// Note: this class is *only* intended for use with the MapVec class.
//
template <class K, class T>
struct mv_pair
{
typedef K first_type;
typedef T second_type;
K first;
T second;
mv_pair()
{ }
mv_pair(const K& k, const T& t)
: first(k), second(t)
{ }
template <class U, class V>
mv_pair(const mv_pair<U,V> & src)
: first(src.first), second(src.second)
{}
// copy constructor, copy assignment operator,
// and destructor all ok
operator const K& () const
{ return first; }
};
template <class K, class T>
bool
operator==(const mv_pair<K,T>& lhs, const mv_pair<K,T>& rhs)
{
return lhs.first == rhs.first; // second intentionally ignored
}
template <class K, class T>
bool
operator!=(const mv_pair<K,T>& lhs, const mv_pair<K,T>& rhs)
{ return !(lhs==rhs); }
template <class K, class T>
bool
operator<(const mv_pair<K,T>& lhs, const mv_pair<K,T>& rhs)
{
return lhs.first < rhs.first; // second intentionally ignored
}
typedef vector<mv_pair<int, string> > MapVec;
int
main()
{
MapVec mv;
std::lower_bound(mv.begin(), mv.end(), 10);
}
///////////////////////////////////////////////////////////////
-tim