sorting std::vector<string> ignoring case
Ed
That is, if I have a vector containing "Xyz" and "abc" I
want to report "abc" "Xyz". I can think of several inelegant ways,
such as creating a second vector with all upper (or lower)
and sort it while saving the sort order in an integer array, using the
latter to index the while reporting the original vector...
that is, an indirect sort. But I was wondering if there was some why
of accomplishing this more directly with the
STL algorithms.
Any thoughts?
TIA
Ed
![Doug Harrison [MVP]'s profile photo](http://lh3.googleusercontent.com/a-/ALV-UjVvzhOQGbT9K0Re6Qg-OU4VGuHq0tAdTu01YlmIjUGm6t_o8g=s40-c)
Doug Harrison [MVP]
Write a comparison class:
struct LessNoCase
{
bool operator()(const std::string& x, const std::string& y) const
{
// Returns true if x < y; false otherwise.
return less_than(x, y);
}
};
Then pass an instance of it to std::sort:
std::sort(v.begin(), v.end(), LessNoCase());
The only question is how to write less_than. I would probably use the
Windows function CompareString. Whatever you use, pay careful attention to
the comment in LessNoCase::operator(); for more on what it's getting at,
read about "strict weak ordering" here:
http://msdn2.microsoft.com/en-us/library/wh15hsex(VS.80).aspx
--
Doug Harrison
Visual C++ MVP
Ed
I tried something like that but w/o success. Following an example in
Visual Studio Help I wrote:
bool operator<(const std::string& x, const std::string& y)
{
string X, Y;
strToUpper(x, X);
strToUpper(y, Y);
return X < Y;
}
Of course it failed, probably because it's using the < being defined,
creating infinite recursion.
But, if you think there's hope along these lines I'll try again.
Ed
"Doug Harrison [MVP]" <d...@mvps.org> wrote in message
news:ab9143dibv84mqcf4...@4ax.com...
Darko Miletic
Here is the sample that works:
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <iostream>
struct LessNoCase {
bool operator()(const std::string &x, const std::string &y) const {
return (stricmp (x.c_str(), y.c_str()) < 0);
}
};
int main() {
std::vector<std::string> strVec;
strVec.push_back("Xyz");
strVec.push_back("abc");
std::sort( strVec.begin(),
strVec.end() ,
LessNoCase() );
std::copy( strVec.begin(),
strVec.end() ,
std::ostream_iterator<std::string>(std::cout,"\n"));
return 0;
}
Cholo Lennon
backward compatibility)
Regards
--
Cholo Lennon
Bs.As.
ARG
"Darko Miletic" <darko....@globant.com> wrote in message news:#pCOAoak...@TK2MSFTNGP03.phx.gbl...
Igor Tandetnik
> I tried something like that but w/o success. Following an example in
> Visual Studio Help I wrote:
>
> bool operator<(const std::string& x, const std::string& y)
Don't name it operator<. Give the function a regular name, pass it as
the third parameter to std::sort
--
With best wishes,
Igor Tandetnik
With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925
Doug Harrison [MVP]
wrote:
>Warning: 'stricmp' is not portable and should be used like '_stricmp' through 'string.h' header (name without underscore is for
>backward compatibility)
>
>Regards
Neither function is "portable". The underscore-prefaced name for this
function (and many others) was introduced to move them out of the user
namespace and into the reserved namespace, but I'm not aware that any of
the original names has ever been removed. (VC8 has marked them deprecated,
though.) If anything, the underscored ones are *less* portable, at least
when it comes to standard Unix system functions such as open, close, etc.
P.S. The name "stricmp" doesn't even step into the user namespace, because
names beginning with str[a-z] (and mem[a-z] for that matter) are reserved
in the global namespace.
Cholo Lennon
been removed. They exist yet. Still is valid to use them in VC8 but, like you appointed, they are deprecated.
Regards
.
--
Cholo Lennon
Bs.As.
ARG
"Doug Harrison [MVP]" <d...@mvps.org> escribió en el mensaje news:9rs1431nbov0cdeil...@4ax.com...
Darko Miletic
> Warning: 'stricmp' is not portable and should be used like '_stricmp' through 'string.h' header (name without underscore is for
> backward compatibility)
>
> Regards
stricmp is POSIX function and exists on any decent C RTL library. Do not
beleive everything one compiler tells you.
>
> --
> Cholo Lennon
> Bs.As.
> ARG
Che, porteños hay en todos lados ;)
Cholo Lennon
> beleive everything one compiler tells you.
POSIX != ANSI . For me ANSI/ISO is the reference to follow.
> Che, porteños hay en todos lados ;)
Che...I'm living in Bs.As. but I'm 'salteño' (from Salta, in the northwest of Argentina) :-))
Best Regards
--
Cholo Lennon
Bs.As.
ARG
"Darko Miletic" <darko....@globant.com> wrote in message news:#s1uQQjk...@TK2MSFTNGP03.phx.gbl...
Ed
me just say that I
much appreciate all the responses. I am up and flying.
Ed
"Ed" <jag_manR__EM*-0_V_...@sbcglobal.net> wrote in message
news:ub7DCzYk...@TK2MSFTNGP06.phx.gbl...
Doug Harrison [MVP]
wrote:
>I'm sorry for my wrong expression, with 'portable' I wanted to say ANSI compatible. Also I didn't say that the original names has
>been removed. They exist yet. Still is valid to use them in VC8 but, like you appointed, they are deprecated.
This is extremely nitpicking, but I believe stricmp and _stricmp are
equally "ANSI compatible", and I gave the reason in the "P.S." part of my
last message. I think the important point is to realize that while declared
in <string.h>, neither are Standard C functions.
FWIW, I mentioned using the Windows function CompareString in my other
message largely because string comparison seems to get more and more
intricate every day, and Windows goes quite a bit beyond C locales, which
influence the behavior of functions like stricmp. For example, I used to
think that doing a setlocale(LC_ALL, "") at program startup was a necessary
first step without any ramifications, but then I looked at how to compare
English strings when searching a presorted data table. Naively, I thought
stricmp was good enough, but then I came across a case in which words were
separated by underscores. Not knowing how underscores collate with other
characters under all conditions, I came across CompareString, which says:
http://msdn2.microsoft.com/en-us/library/ms647476.aspx
<q>
When the results of the comparison should be consistent regardless of
locale, for example, when comparing retrieved data against a predefined
list or an internal value, use CompareString or CompareStringEx. Either of
the following calls will match even if mystr is "INLAP", whereas the
locale-sensitive call to lstrcmpi fails if the current locale is
Vietnamese.
</q>
So apparently even pure English doesn't sort the same in a case-insensitive
way across all locales when using functions like lstrcmpi and probably by
extension, stricmp. So to use stricmp in this scenario, I'd have to undo
and reset my C-level locale for every comparison. What a mess. I replaced
it with the "invariant" code suggested by the CompareString documentation.
I'd be interested to hear from anyone who knows how to approach this with
C++ locales.
Doug Harrison [MVP]
<darko....@globant.com> wrote:
>stricmp is POSIX function and exists on any decent C RTL library.
I'm not aware that it's defined by POSIX. It's been a long time, but ISTR
GNU C defining strcasecmp and seeing stricmp #defined to it.
Darko Miletic
> On Wed, 09 May 2007 09:21:26 -0300, Darko Miletic
> <darko....@globant.com> wrote:
>
>> stricmp is POSIX function and exists on any decent C RTL library.
>
> I'm not aware that it's defined by POSIX. It's been a long time, but ISTR
> GNU C defining strcasecmp and seeing stricmp #defined to it.
>
Indeed you are right. POSIX defines strcasecmp which is complete
equivalent to the stricmp function.
http://www.opengroup.org/pubs/online/7908799/xsh/strcasecmp.html
Cholo Lennon
--
Cholo Lennon
Bs.As.
ARG
"Doug Harrison [MVP]" <d...@mvps.org> wrote in message news:gp3543tv3hm1a44ih...@4ax.com...
Darko Miletic
There is also C function stricoll that does the same thing. It is just
easier for common use. I used it a lot in VC++ for all kinds of case
insensitive comparisons.
> I'd be interested to hear from anyone who knows how to approach this with
> C++ locales.
There is starting point for this in GOTW #29.
http://www.gotw.ca/gotw/029.htm
Still it is a complicated matter.
Darko
Jerry Coffin
says...
[ ... ]
> So apparently even pure English doesn't sort the same in a case-insensitive
> way across all locales when using functions like lstrcmpi and probably by
> extension, stricmp. So to use stricmp in this scenario, I'd have to undo
> and reset my C-level locale for every comparison. What a mess. I replaced
> it with the "invariant" code suggested by the CompareString documentation.
> I'd be interested to hear from anyone who knows how to approach this with
> C++ locales.
This is one place that C++ does quite a bit better job than C. In C you
have only a single, global locale that applies to everything at any
given time.
C++ has a global locale (inherited from C) that applies to things like
the C string functions, but it also allows you to associate locale
objects with individual items so you can (usually) avoid the scenario
you describe above, having to constantly change the global locale. For
example, each iostream has an associated locale.
Unfortunately, in the case of strings, the locale-like information for
the string is an implicit property of the char_traits class, so it's not
entirely straightforward to do a string comparison using the ordering
from a specific locale. Worse, the char_traits for a string is a
template parameter, so two strings that use different char_traits are
completely separate types and you can't compare one to another, assign
one to another, etc. That's not always a major problem, but sometimes it
becomes a serious pain.
Finally, the simple fact is that most documentation on this part of the
C++ standard library just plain sucks. Josuttis covers it pretty well,
but I haven't seen much else that could even claim mediocre coverage.
This is also an area that's decidedly different from the STL-inspired
parts of the library -- this is a much more object-oriented setup, where
doing almost anything typically involves deriving a new class from one
of the base classes in the library. In quite a few cases, the overhead
can seem a bit ridiculous.
--
Later,
Jerry.
The universe is a figment of its own imagination.
Doug Harrison [MVP]
<cholo...@hotmail.com> wrote:
>"Doug Harrison [MVP]" <d...@mvps.org> wrote in message news:gp3543tv3hm1a44ih...@4ax.com...
>> On Wed, 9 May 2007 00:18:22 -0300, "Cholo Lennon" <cholo...@hotmail.com>
>> wrote:
>>
>> >I'm sorry for my wrong expression, with 'portable' I wanted to say ANSI compatible. Also I didn't say that the original names has
>> >been removed. They exist yet. Still is valid to use them in VC8 but, like you appointed, they are deprecated.
>>
>> This is extremely nitpicking, but I believe stricmp and _stricmp are
>> equally "ANSI compatible", and I gave the reason in the "P.S." part of my
>> last message. I think the important point is to realize that while declared
>> in <string.h>, neither are Standard C functions.
>
>Am I missing something? I don't see stricmp in the C89/C99/C++ 98 standards
I thought you were saying to avoid stricmp because it isn't "ANSI
compatible" and to use _stricmp because it is. Indeed, the latter is "ANSI
compatible" in the sense that it is an implementation-defined non-standard
function that begins with an underscore. But in an "extremely nitpicking"
way, so is stricmp, for the reasons I gave in the "P.S." part of my earlier
message. However, like I said, "neither are Standard C functions". There's
no contradiction, as "ANSI compatible" does not imply "standard library
function"; the former just means "does not violate the standard". So, you
really don't need to choose _stricmp over stricmp for reasons of
"portability" or "ANSI compatibility". The real reason is that MS has made
stricmp deprecated. Also, if you compile with /Za, which #define __STDC__
for .c files, and I don't know anyone who does or ever has <g>, MS has
chosen to make stricmp go away, even though they could have left it alone
and still been "ANSI compatible".
Doug Harrison [MVP]
>This is one place that C++ does quite a bit better job than C. In C you
>have only a single, global locale that applies to everything at any
>given time.
>
>C++ has a global locale (inherited from C) that applies to things like
>the C string functions, but it also allows you to associate locale
>objects with individual items so you can (usually) avoid the scenario
>you describe above, having to constantly change the global locale. For
>example, each iostream has an associated locale.
Right.
>Unfortunately, in the case of strings, the locale-like information for
>the string is an implicit property of the char_traits class, so it's not
>entirely straightforward to do a string comparison using the ordering
>from a specific locale. Worse, the char_traits for a string is a
>template parameter, so two strings that use different char_traits are
>completely separate types and you can't compare one to another, assign
>one to another, etc. That's not always a major problem, but sometimes it
>becomes a serious pain.
Tell me about it. :) Long ago, back in the Wild West days of standardized
C++, I wrote my own string class that supported true COW and modeled it as
closely as possible on the draft basic_string, and to make string types
assignment-compatible, I split my char_traits into "assign_traits" and
"compare_traits" so that my normal, case-insensitive, and filename string
types would all be assignment-compatible but not comparable. (More
generally, "assign_traits" applied to all things that were
comparison-agnostic.) The class header for my basic_string-alike looked
like this:
template<
class CharT,
class TraitsT = my_string_compare_char_traits<CharT>,
class AllocT = my_allocator<charT> >
class my_basic_string
: public my_basic_string_base<CharT, TraitsT::assign_traits, AllocT>
Functions that had "string" parameters and performed comparison-agnostic
operations (including functions like "compare" which don't use the string
parameter's traits) on them would use my_basic_string_base parameters, and
all three of my "standard" string types were assign_traits-compatible,
which was nice. However, you couldn't compare, say, a my_string to a
my_filename without casting one of them to the base class and thus
neutralizing it, because they differed in their compare_traits, which was
also nice. After nearly 10 years of using these classes, I wouldn't want to
use std::string instead of them in any program that made significant use of
strings. Unfortunately, the whole idea behind functions like
char_traits::lt has kind of gone out the window, so to get back on topic,
I'd hope that defining a new char_traits is not the current state of the
art for locale-aware string comparison in C++.
>Finally, the simple fact is that most documentation on this part of the
>C++ standard library just plain sucks. Josuttis covers it pretty well,
>but I haven't seen much else that could even claim mediocre coverage.
>This is also an area that's decidedly different from the STL-inspired
>parts of the library -- this is a much more object-oriented setup, where
>doing almost anything typically involves deriving a new class from one
>of the base classes in the library. In quite a few cases, the overhead
>can seem a bit ridiculous.
Yep, I've always found C++ locales fairly impenetrable. Besides Josuttis,
ISTR Stroustrup published a C++PL appendix concerning C++ locales on his
web site several years ago, which I did read, but I pretty much lost
interest in the subject since then.
Daniel Lidström
> I need to sort a vector of strings ignoring case while preserving it.
Here's an article you might find interesting:
http://lafstern.org/matt/col2_new.pdf
--
Daniel
Cholo Lennon
say that _stricmp is ANSI compatible (I'm sorry again if I wasn't very clear
or very specfic). I suggested the use of _stricmp because (like you said) its
name it's conformant with standard (because it's declared inside string.h).
Best regards
--
Cholo Lennon
Bs.As.
ARG
"Doug Harrison [MVP]" <d...@mvps.org> wrote in message news:rue643996um34ojfj...@4ax.com...
Jerry Coffin
cholo...@hotmail.com says...
> Ok, I understand your "P.S." point. You're right. Only one thing: I didn't
> say that _stricmp is ANSI compatible (I'm sorry again if I wasn't very clear
> or very specfic). I suggested the use of _stricmp because (like you said) its
> name it's conformant with standard (because it's declared inside string.h).
The name stricmp conformed just as well (all names starting with 'str'
are reserved, per section 7.26.11 of the C99 standard, or 7.13.8 of the
original C89/90 standard). Adding the leading underscore accomplished
nothing in this case.
Cholo Lennon
1st: Section 7.26 of the C99 standard refers to "Future Library Directions", this means "future decisions and uses of the Committee"
2nd: Like you appointed, Section 7.26.11 say that all names starting with 'str' are reserved. Are reserved for future use of the
Committee due to section 7.26. They are not reserved for implementors. stricmp is implemented (in this case) by Microsoft (It's not
defined by ANSI) and its name starts with 'str' so they have to use the leading underscore (names starting with underscores are
reserved for implementors).
For more information, take a look to "Rationale for International Standard - Programming Language - C"
http://www.math.utah.edu/computing/compilers/c/n897.pdf
I'll be waiting for opinions or corrections (this discussion now is about C...how about C++?)
Regards
--
Cholo Lennon
Bs.As.
ARG
"Jerry Coffin" <jco...@taeus.com> escribió en el mensaje news:MPG.20aeea74d...@news.sunsite.dk...
Jerry Coffin
cholo...@hotmail.com says...
> I don't agree.
That's fine -- but can you point to a part of the standard that supports
your disagreement?
> 1st: Section 7.26 of the C99 standard refers to "Future Library Directions",
> this means "future decisions and uses of the Committee"
>
> 2nd: Like you appointed, Section 7.26.11 say that all names starting with
> 'str' are reserved. Are reserved for future use of the Committee due to
> section 7.26. They are not reserved for implementors. stricmp is implemented
> (in this case) by Microsoft (It's not defined by ANSI) and its name starts
> with 'str' so they have to use the leading underscore (names starting with
> underscores are reserved for implementors).
Names starting with underscores are simply reserved, just like names
starting with 'str' (e.g. $ 7.1.3 of C99). The sole difference is that a
name starting with an underscore is _always_ reserved, where names
listed in the 'future library directions' clause are only reserved if
you include the associated standard header (e.g. 'str*' is only reserved
if you include <string.h>).
As far as C vs. C++ goes, the C++ standard simply says ($21.4/2):
"contents of these headers are the same as the Standard C library
headers <ctype.h>, <wctype.h>, <string.h>, <wchar.h> and <stdlib.h>
respectively, with the following modifications:" (and then goes on to
list things like const vs. non-const overloads of strchr, but nothing
that affects what names are reserved). Other than the C compatibility
parts, the C++ library puts nearly everything in namespace std, which is
intended to eliminate (or at least drastically ameliorate) this issue.
Inside of namespace std, there are far fewer restrictions on what the
C++ library is allowed to do. For example, in C including <string.h> is
_not_ allowed to declare malloc(), but in C++ including any standard
header can have the same effect as including any or all other standard
headers.
> For more information, take a look to "Rationale for International
> Standard - Programming Language - C"
Or don't -- this is always interesting reading, but it's not normative.
Unless you can find support for your position within the standard, it's
not really supported.
David Wilkinson
> I don't agree.
>
> 1st: Section 7.26 of the C99 standard refers to "Future Library Directions", this means "future decisions and uses of the Committee"
>
> 2nd: Like you appointed, Section 7.26.11 say that all names starting with 'str' are reserved. Are reserved for future use of the
> Committee due to section 7.26. They are not reserved for implementors. stricmp is implemented (in this case) by Microsoft (It's not
> defined by ANSI) and its name starts with 'str' so they have to use the leading underscore (names starting with underscores are
> reserved for implementors).
>
> For more information, take a look to "Rationale for International Standard - Programming Language - C"
> http://www.math.utah.edu/computing/compilers/c/n897.pdf
>
> I'll be waiting for opinions or corrections (this discussion now is about C...how about C++?)
As nit-picking discussions go, this one has been very informative, and I
have learned several things I did not know before. Keep it coming....
--
David Wilkinson
Visual C++ MVP
Doug Harrison [MVP]
>In article <e7kCsV#kHHA...@TK2MSFTNGP03.phx.gbl>,
>cholo...@hotmail.com says...
>> Ok, I understand your "P.S." point. You're right. Only one thing: I didn't
>> say that _stricmp is ANSI compatible (I'm sorry again if I wasn't very clear
>> or very specfic). I suggested the use of _stricmp because (like you said) its
>> name it's conformant with standard (because it's declared inside string.h).
>
>The name stricmp conformed just as well (all names starting with 'str'
>are reserved, per section 7.26.11 of the C99 standard, or 7.13.8 of the
>original C89/90 standard).
Which was my "P.S." point. :)
>Adding the leading underscore accomplished
>nothing in this case.
Well, it did achieve consistency for the non-standard functions MS provides
as part of the CRT, but that's about it. If stricmp were ever to be
standardized, there would be a lot of pressure to be compatible with
existing practice, so I don't think leaving it alone would have hurt
anything.
Doug Harrison [MVP]
<cholo...@hotmail.com> wrote:
>I don't agree.
>
>1st: Section 7.26 of the C99 standard refers to "Future Library Directions", this means "future decisions and uses of the Committee"
>
>2nd: Like you appointed, Section 7.26.11 say that all names starting with 'str' are reserved. Are reserved for future use of the
>Committee due to section 7.26. They are not reserved for implementors. stricmp is implemented (in this case) by Microsoft (It's not
>defined by ANSI) and its name starts with 'str' so they have to use the leading underscore (names starting with underscores are
>reserved for implementors).
>
>For more information, take a look to "Rationale for International Standard - Programming Language - C"
>http://www.math.utah.edu/computing/compilers/c/n897.pdf
>
>I'll be waiting for opinions or corrections (this discussion now is about C...how about C++?)
An implementation is indeed free to use these str names (which was my point
in my "P.S." so long ago). For more, see (you might want to expand the
thread and read the messages leading to this one):
http://groups.google.com/group/comp.lang.c/msg/a3d0daa042ff50ce?hl=en&
While _stricmp is safer in that it's future-proof WRT the standard, stricmp
is sufficient in the absence of a (future) standardized function with that
name.