What list class to use?

Question

I'd like to create a short lived list, over the life of a function, to collect a list of CPoint objects and then iterate over those objects. I'd like to use CTypedPtrList but I am not sure how to set it up to have it accept objects not derived from CObject; CPoint comes from a struct tagPOINT.

Is it possible to use CTypedPtrList with CPoint?

Otherwise, should I just use std::list<CPoint>? // I have started to use std:list and can successfully build a list, but I cannot find a way to iterate over the list.

std::list<CPoint*> pointList;
// Add to the list with list.push_front(new CPoint(x, y));
std::for_each(pointList.begin(), pointList.end(), [](pointList* cur)
{
    TRACE("APoint: %f, %f\n", cur->x, cur->y);
});

I have tried that, but I keep getting told that for_each is not a member of std. I tried to add #include <for_each> (as I had to do for list) but it still is not recognized.

Any suggestions?

`pointList` is not a type. Also, `for (auto cur : pointList) {/*use cur*/}`. — chris, Aug 19 '14 at 12:49
Favor the stdlib containers over the MFC ones whenever possible. Your code will be more portable and better prepared for use with the different standard algorithms. — dlf, Aug 19 '14 at 12:50
@FredOverflow Sure. Some algorithms that fast on lists are not so on vectors. OP specifically says he needs some implementation of list data structure. — Cthulhu, Aug 19 '14 at 12:53
@Cthulhu What algorithms? OP wants to build a list and then iterate over the elements. Sounds like a perfect job for `std::vector`. — fredoverflow, Aug 19 '14 at 12:57
@Cthulhu: It's not at all apparent that when the OP says "list" he specifically means "linked list". Given the requirements he has stated (collect CPoint objects then iterate over those objects), `std::vector` does sound like a substantially better fit than any sort of linked list. — Jerry Coffin, Aug 19 '14 at 12:57
possible duplicate of [In which scenario do I use a particular STL Container?](http://stackoverflow.com/questions/471432/in-which-scenario-do-i-use-a-particular-stl-container) — MatthiasB, Aug 19 '14 at 12:59
Code shows new points being added to the *front* which, *if required*, is a point in favor of list over vector. — dlf, Aug 19 '14 at 13:01
@dlf Not really. Just add to end and iterate backwards. Plus I don't think there's really specific requirement to add to front. — JarkkoL, Aug 19 '14 at 13:03
@dlf: If he really needed to add to the front (e.g., needs to add to both ends, in which case "add to the end and iterate backwards" isn't sufficient) that would favor `std::deque`, but still not really `std::list`. — Jerry Coffin, Aug 19 '14 at 13:16

fredoverflow · Accepted Answer · 2014-08-19T13:06:49.137

3

I recommend a std::vector. Also, there is no need for pointers here:

std::vector<CPoint> pointList;
// ...
pointList.emplace_back(x, y);
// ...
for (const CPoint& p : pointList)
{
    TRACE("APoint: %f, %f\n", p.x, p.y);
}

You seem to be using a very old C++ compiler. Try the following:

std::vector<CPoint> pointList;
// ...
pointList.push_back(CPoint(x, y));
// ...
for (std::vector<CPoint>::const_iterator it = pointList.begin();
                                        it != pointList.end(); ++it)
{
    TRACE("APoint: %f, %f\n", it->x, it->y);
}

edited Aug 19 '14 at 13:06

answered Aug 19 '14 at 12:55

fredoverflow

256,549
94
388
662

My `std::vector` does not have a method `emplace_back`? Maybe I am using an older version of `std`? – AnotherUser Aug 19 '14 at 12:59
Ok that works, and for the loop I get three errors. `error C2143: missing ',' before ':' error C2530: 'p' : references must be initialized error C2143: missing ';' before '{'` – AnotherUser Aug 19 '14 at 13:04
You might also want to consider updating your compiler. VC++ has supported `emplace_back` for a while now. – Jerry Coffin Aug 19 '14 at 13:05
If you're using a version of VC++ that doesn't support `emplace_back`, then it doesn't support the range-based `for` either. You could go back to your original idea of `std::for_each`, or use Microsoft's `for each(const CPoint& p in pointList)` language extension. – dlf Aug 19 '14 at 13:06
I'd upgrade everything, but alas, but my employer wishes to finish sawing down the tree before sharpening the blade. C# and Wpf? Nah 10+ year old MFC and C++. // Thank you @FredOverflow that worked for me! – AnotherUser Aug 19 '14 at 13:14

score 2 · Answer 2 · edited May 23 '17 at 11:49

2

To fix your compilation error, #include <algorithm> and change to :

std::for_each(pointList.begin(), pointList.end(), [](CPoint* cur)
{                                                   ^^^^^^^^
    TRACE("APoint: %f, %f\n", cur->x, cur->y);
});

Or more simply with a for range loop:

for(auto& p : pointList)
{
    TRACE("APoint: %f, %f\n", p->x, p->y);
}

Note:

As for choosing a container Stick to Standard containers as long as you can, std::list<> is a good choice if you need a doubly linked list, but in your case an std::vector<> might just do it as well.
Also see In which scenario do I use a particular STL Container?

edited May 23 '17 at 11:49

Community

1
1

answered Aug 19 '14 at 12:49

quantdev

23,517
5
55
88

@JerryCoffin how could that be ? Contiguous containers have to shuffle around half of their content, while a doubly-linked list just has four pointers to hook... – Quentin Aug 19 '14 at 12:55
@Quentin Shuffle around half their content when? – fredoverflow Aug 19 '14 at 13:00
@Quentin: In a vector you shuffle (on average) half the content to insert in the middle, so it's O(N). In a linked list, you have to walk through half the list on average to get to the insertion point, so it's *also* O(N) -- but being non-contiguous leads to poorer locality, so it makes poorer use of the cache. – Jerry Coffin Aug 19 '14 at 13:00
@JerryCoffin you're measuring more than just the insertion then. – Quentin Aug 19 '14 at 13:05
What are you guys talking about? Who wants to "insert in the middle"? – fredoverflow Aug 19 '14 at 13:09
@FredOverflow: Probably nobody--he's just grasping at straws trying to justify continued advocacy for `std::list`. – Jerry Coffin Aug 19 '14 at 13:12
@Quentin: I don't think so. I'm simply measuring *all* of the time necessary to do an insertion, and you're ignoring a large part of it in one case. – Jerry Coffin Aug 19 '14 at 13:13
@FredOverflow quantdev originally adviced `std::list` for its insertion speed. Jerry argued against this, and deleted his comment afterwards. – Quentin Aug 19 '14 at 13:14
@JerryCoffin one could argue that the insertion point is often already known (otherwise you're inserting blindly, which still must have its uses, but I can't think of any). Finding an element is another problem. – Quentin Aug 19 '14 at 13:16

What list class to use?

2 Answers2