как использовать find_if с неконтейнером, таким как связанный список? - PullRequest
Новая
       16

как использовать find_if с неконтейнером, таким как связанный список?

0 голосов
/ 28 сентября 2018

Я пытаюсь поддержать алгоритм для статического списка объектов.Я пытался сделать это различными способами, но единственный способ заставить его работать - это написать традиционный цикл для C.

Пример: 

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;
      }
);

Я также попробовал это с помощьюОпределены функции begin() и end().Единственное, что работает, это следующее: 

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

Что мне не хватает?

Ответы [ 3 ]

0 голосов
/ 30 сентября 2018

Проблема в том, что ваши begin / end функции возвращают указатель, поэтому, когда find_if увеличивает указатель на ++, он просто увеличивает указатель, чтобы указывать на мусор после первого узла, и неиспользуйте ваш operator++.

Вам необходимо определить объект класса итератора, который определяет оба (унарный) operator* и operator++, и его начало / конец возвращают.Этот класс итератора, скорее всего, содержит только одно поле указателя.

0 голосов
/ 30 сентября 2018

Глядя на проблему с отладчиком, это то, что я обнаружил.Определяя ListNode * как итератор, STL интерпретирует его как итератор с произвольным доступом, а не как прямой интегратор.В этом случае ожидается, что begin () и end () будут указателями на массив, где они могут быть вычтены для определения отношения.Поскольку end () определяется как nullptr, алгоритм find_if () не выполняет оператор приращения и немедленно прерывает работу, возвращая end ().

Так что мне нужно выяснить, как определить forward_iterator, чтобы списокобход работает правильно.

0 голосов
/ 30 сентября 2018

Спасибо за отзыв.

Я разрабатываю программное обеспечение для критически важных приложений.Использование динамической памяти, как правило, не допускается.Класс связанного списка STL - это независимая структура данных, используемая для ведения списка объектов.У нас есть объекты, и нам просто нужно, чтобы они функционировали как STL-совместимые контейнерные объекты.(вот почему)

Эта ссылка была очень полезна.Проблема заключалась в ошибочном определении оператора приращения.

...