howto use find_if with non-container such as linked list?

Question

I am trying to algorithm support for a static list of objects. I have tried to do this various ways but the only way I can get it to work is to write a traditional C for loop.

Example:

class ListNode
{
public:
    ListNode(int id);
    virtual ~ListNode() {}

    // Container support functions
    ListNode* operator++() {return m_nextNode;}
    static ListNode* findNode(int p_id);
    static ListNode* m_nodeList{nullptr};

private:
    int m_id;
    ListNode *m_nextNode;

protected:
    static void addNewNode(ListNode* p_node);

    friend ListNode* begin(void);
};

inline ListNode* begin(void) {return ListNode::m_nodeList;}
inline ListNode* end(void) {return nullptr;}

// Declare the list head
ListNode* ListNode::m_nodeList = nullptr;

// Constructor
ListNode::ListNode (int id): m_id{id}
{
    ListNode::addNewNode(this);
}

// Add node to front of list
void ListNode::addNewNode(ListNode* p_node)
{
    p_node->m_nextService = m_nodeList;
    m_nodeList = p_node;
}

//
// The following are all the find implementation attempts
//

ListNode* ListNode::failedFind1(int id) {
   return std::find_if(ListNode::m_nodeList,
      static_cast<ListNode*>(nullptr),
      [p_serviceNumber](const ListNode& s) {
         return id==s.m_id;
      }
);

I also tried this using the begin() and end() functions defined. The only thing that works is the following:

for (auto *s = m_nodeList; s != nullptr; s = s->m_nextNode)
{
    if (s->m_id == id)
        return s;
}
return nullptr;

What am I missing?

You are missing everything about building a C++ container and iterators. I'm not sure where I read the rules for it but try Stroustrup's C++ book. Also read the code in the C++ Standard Library. — Zan Lynx, Sep 28 '18 at 18:20
Also, there is certainly an existing linked list container already written that you could use. — Zan Lynx, Sep 28 '18 at 18:24
@n.m. It's almost always academic exercises, to learn about data structures. — Barmar, Sep 28 '18 at 18:28
https://stackoverflow.com/questions/8054273/how-to-implement-an-stl-style-iterator-and-avoid-common-pitfalls — Zan Lynx, Sep 28 '18 at 18:34

score 1 · Answer 1 · answered Sep 30 '18 at 19:26

1

Thank you for the feedback.

I develop software for safety critical applications. Using dynamic memory is generally not allowed. The STL linked list class is an independent data structure used to maintain a list of objects. We have objects and just need them to function as STL compatible container objects. (that is the why)

This link was very useful. The problem was an errant definition of the increment operator.

answered Sep 30 '18 at 19:26

Allen Curtis

91
6

There are intrusive linked list implementations in e.g. boost you should probably look into. – Nir Friedman Sep 30 '18 at 20:19

Chris Dodd · Answer 2 · 2018-09-30T20:15:11.630

0

The problem is that your begin/end functions return a pointer, so when find_if increments the pointer with ++, it just increments the pointer to point at garbage after the first node, and does not use your operator++.

You need to define an iterator class object, which defines both (unary) operator* and operator++, and have begin/end return that. This iterator class likely just contains a single pointer field.

edited Sep 30 '18 at 20:15

answered Sep 30 '18 at 20:07

Chris Dodd

119,907
13
134
226

Forgot to mention the operator++() in the original post. This is what I have now. // Container support functions typedef AbstractService* iterator; typedef const AbstractService* const_iterator; static iterator begin() noexcept {return iterator(AbstractService::m_serviceList);} static iterator end() noexcept {return iterator(nullptr);} iterator& operator++() {return m_nextService;} – Allen Curtis Sep 30 '18 at 20:30
That won't work, as `++` is already defined for pointer types and can't be overloaded -- you can only overload operators on class types, not on "builtin" types. So you need your iterator type to be a class type, not a pointer type. Pointers only work as iterators for raw arrays. – Chris Dodd Sep 30 '18 at 20:37

score 0 · Answer 3 · answered Sep 30 '18 at 20:27

Looking into the problem with the debugger, this is what I discovered. Defining ListNode* to be iterator, STL is interpreting this as a random access iterator, not a forward interator. In this case it is expecting begin() and end() to be pointers into an array where they may be subtracted to determine a relationship. Since end() is being defined as nullptr, the find_if() algorithm is not performing the increment operator and aborting immediately, returning end().

So I need to figure out how to define a forward_iterator so the list traversal works properly.

howto use find_if with non-container such as linked list?

3 Answers3