CArray, CStringArray, CMap, ...

[KW]

I have a list of CStrings I would like to add to an array or list.

I would like to be able to:
Return the count of items.
Find a specific item.
Remove all of the items.
Allow the list/array to grow dynamically (could be 100 up to 10000
items).

Of course, I can iterate through the items for each of these functions, but
I would like do this in the fastest way possible. It would also be a plus if
these operations were thread safe.

Are there any suggestions on the best route to take?

Thanks,
KW

[David Lowndes]

>I have a list of CStrings I would like to add to an array or list.
>
>I would like to be able to:
> Return the count of items.
> Find a specific item.
> Remove all of the items.
> Allow the list/array to grow dynamically (could be 100 up to 10000
>items).

These days I'd tend to use the standard C++ library (ex-STL)
collection classes - choose a vector as the collection type unless
your pattern of usage favours one of the others.

>It would also be a plus if
>these operations were thread safe.

If you have a collection shared between different threads it's your
responsibility to keep things safe!

Dave

[Tom Serface]

I use CStringArray or CStringList for this sort of thing. To find the
specific item I just iterate through the list. They are really easy to use
and work pretty fast if your data requirements are not outrageous (10,000
items is certainly not outrageous by any means) I tend to use CObArray
though since they store pointers nicely and I always end up wanting to add
something besides strings, but the CStringArray ahs the same functionality.

For example:

for(int i = 0; i < m_MyDataArray.GetSize(); ++i) {
CMyDataInfo *pInfo = (CDiscoveredSystemInfo
*)m_DiscoveredSystemsArray.GetAt(i);
if(pInfo->m_csString == String) // Found the object
return pInfo;
}

Tom

"KW" <K...@there.com> wrote in message
news:eSaP9Y5t...@TK2MSFTNGP02.phx.gbl...

[Giovanni Dicanio]

"KW" <K...@there.com> ha scritto nel messaggio
news:eSaP9Y5t...@TK2MSFTNGP02.phx.gbl...

I would use std::vector template container class from STL.
std::vector works just fine with CString as contained item.

This code sample shows the points you requested:

<code>

// A list of strings stored in an array
typedef std::vector< CString > StringList;

// Create an empty collection
StringList someStrings;

// Grows the collection dynamically
someStrings.push_back( _T("I'm the first string.") );
someStrings.push_back( _T("I'm the second string.") );
someStrings.push_back( _T("Hello") );

// 3 items in the container.
// Use size() method to get count of items.
ASSERT(someStrings.size() == 3);

// Search the string "Hello"
StringList::iterator it;
it = std::find( someStrings.begin(), someStrings.end(), _T("Hello") );
if ( it == someStrings.end() )
{
// Not found
}
else
{
// Found
}

// Remove all of the items
someStrings.clear();
ASSERT(someStrings.size() == 0);

</code>

HTH,
Giovanni

[Goran]

My guess on the order of best candidates:

1. std::vector<CString>
2, 3 (joint place) CStringArray and CArray<CString>
4. any list

I think, if you won't be inserting/removing items a lot, vector or MFC
Array beat any list easily, especially for fast-copying data like
CString. I also think, compared to std::vector, MFC arrays have an
inferior method of deciding a "grow by" size. MFC method is: grow in
2^10 chunks after 2^10 elements, or use programmer-supplied "grow-by
size". std::vector method is "grow by 50% and provide reserve method
for fast startup".

But... Don't listen to me. If you want to be at least somewhat
confident WRT the "fastest" method, you must measure your code, or a
good representative of it. In my experience, a programmer is a
horrible judge of performance issues. Moreover, __present__ is a
horrible judge of performance issues.

WRT thread-safety: neither MFC nor standard C++ containers give that.
That's your job.

HTH,
Goran.

P.S. Thread safety is overrated ;-), Mr. Sutter says so here:
http://www.ddj.com/hpc-high-performance-computing/215900465

[Jonathan Wood]

My personal preference is to use CArray<CString>.

If you want search to be as fast as possible, then you'll maintain the list
in a sorted order and perform a binary search.

--
Jonathan Wood
SoftCircuits Programming
http://www.softcircuits.com
http://www.softcircuits.com/blog/

"KW" <K...@there.com> wrote in message
news:eSaP9Y5t...@TK2MSFTNGP02.phx.gbl...

[Tom Serface]

I think there is some trade off depending on how often you want to search.
For example, if I seldom search, but add a bunch of items all at once
sorting just takes up a bunch of time when each item is added. In that case
I'd likely use a map instead with a hash. I've also found I can search
through like 100K items in a CObArray in a second or so ... so an occasional
search is not really that objectionable. However, if the program is
constantly searching then a better mechanism is needed of course.

Tom

"Jonathan Wood" <jw...@softcircuits.com> wrote in message
news:%23EFFfRG...@TK2MSFTNGP02.phx.gbl...

[Joseph M. Newcomer]

Do the items have a unique key? std::map is probably your best choice here.

I no longer use MFC classes for these purposes. I still use them, but for your problem, I
wouldn't look beyond std::map (it gives you the quick lookup capability)
joe

Joseph M. Newcomer [MVP]
email: newc...@flounder.com
Web: http://www.flounder.com
MVP Tips: http://www.flounder.com/mvp_tips.htm

[KW]

Yes, each item is unique and will be the only thing stored.

There will be data going into the structure on a fairly steady basis, while
lookups will be few and far between.

KW

"KW" <K...@there.com> wrote in message
news:eSaP9Y5t...@TK2MSFTNGP02.phx.gbl...

[Joseph M. Newcomer]

If lookups are few, CStringArray, CArray<CString> and std::vector<CString> all seem
feasible representations. I have done optimized adaptive structures in the past when
lookups were frequent and insertions frequent, but infrequent lookups are going to cost
you O(N/2) on the average for an unsorted array, but on modern machines that may not be
expensive enough to matter for "infrequent" (whatever that might mean) lookups.

You can preallocate elements to CArray and std::vector<CString> to minimize the cost of
adding elements. For something as tiny as 10,000 strings, I'd just preallocate all 10,000
elements when I created the array, and not worry about it.
joe

[Jonathan Wood]

"Tom Serface" <t...@camaswood.com> wrote in message
news:80B6C567-A7EC-4E0F...@microsoft.com...

>I think there is some trade off depending on how often you want to search.
>For example, if I seldom search, but add a bunch of items all at once
>sorting just takes up a bunch of time when each item is added. In that
>case I'd likely use a map instead with a hash. I've also found I can
>search through like 100K items in a CObArray in a second or so ... so an
>occasional search is not really that objectionable. However, if the
>program is constantly searching then a better mechanism is needed of
>course.

Hashes always seem like a pain to me in that it's not always easy to get a
good hash key, and data tends to use a lot of extra memory to have enough
slots for a good hash key (although this can be mitigated somewhat).

A good sorted array will perform a look up when inserting an item rather
than resorting the entire list and I've found that to be a good approach for
many applications.

Of course, it's always a trade off depending on your particular
requirements.

[Tom Serface]

Can't argue with that :o)

Tom

"Jonathan Wood" <jw...@softcircuits.com> wrote in message

news:%23RXrZ5U...@TK2MSFTNGP04.phx.gbl...