C++ Smart Poiters na lista simplesmente encadeada

6 de janeiro de 2022

Com a ajuda do pessoal do fórum acabei conhecendo os ponteiros inteligentes, porém não consegui implementa-los nessas funções abaixo, a intenção era sumir com todos esses delete.

void LinkedList::clear() {
    while(m_head != nullptr) {auto *aux = m_head; m_head = m_head->next; delete aux;}
    m_size = 0;
}

void LinkedList::push_back(Item data) {
    auto *newNode = new Node(data, nullptr);
    if(m_head == nullptr) {m_head == newNode; m_size++;} // lista vazia
    else{ // size >= 1
        auto *aux = m_head;
        while(aux->next != nullptr) {aux = aux->next;}
        aux->next = newNode;
        m_size++;
        delete aux;
    }
}

void LinkedList::pop_back() {
    if(empty()) {throw new std::out_of_range("list empty");} 
    else if(m_head->next == nullptr) {delete m_head; m_head = nullptr; m_size--; } // 1 elemento
    else{ // 2 ou + elementos
        auto *aux = m_head;
        while(aux->next->next != nullptr) {aux = aux->next;}
        delete aux->next;
        aux->next = nullptr;
        m_size--;
    }
}

arfneto · 6 de janeiro de 2022

10 horas atrás, Prodigy085 disse:

Com a ajuda do pessoal do fórum acabei conhecendo os ponteiros inteligentes, porém não consegui implementa-los nessas funções abaixo, a intenção era sumir com todos esses delete

O "pessoal do forum" recomenda postar um programa inteiro,. compilável.

O "pessoal do forum" lembra que não é o caso de sumir com os delete mas sim com os new. Rodou o exemplo que te mostrei, @Prodigy085?

Ansi C · 6 de janeiro de 2022

@Prodigy085 Por que quer o sumiço do operador, especificamente, quando não apresenta erro?

Aqui:

11 horas atrás, Prodigy085 disse:

void LinkedList::clear() {
    while(m_head != nullptr) {auto *aux = m_head; m_head = m_head->next; delete aux;}
    m_size = 0;
}

Se não me engano, o endereço em aux é liberado de qualquer forma. E com uso de um dos "Smart Pointers" a destruição acontece, implicitamente, na atribuição do endereço seguinte.

Ou seja, implícito é legal?

[]

6 de janeiro de 2022

@arfneto Tem razão, então acho q não se aplica.

arfneto · 6 de janeiro de 2022

@Prodigy085 você vai retirar os new, justamente para evitar os possíveis erros com os delete.

O que não se aplica? Poste algo compilável.

6 de janeiro de 2022

@arfneto

Node.h:

#ifndef NODE_H
#define NODE_H
#include <string>

typedef std::string Item;

struct Node {
    Item data;
    Node *next;

    Node(Item& d, Node *n) {
        data = d;
        next = n;
    }
};

#endif

LinkedList.h:

#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <iostream>
#include "Node.h"

class LinkedList {
private:
    Node *m_head; 
    int m_size;

public:
    LinkedList(); 
    ~LinkedList();

public:
    bool empty(); 
    void clear(); 
    int size();
    void push_back(Item data);
    void pop_back();
    
    friend std::ostream& operator<<(std::ostream& out, const LinkedList& l);
};

#endif

LinkedList.cpp

#include "LinkedList.h"
#include "Node.h"
#include <iostream>


LinkedList::LinkedList() {
    m_size = 0;
    m_head = nullptr;
    std::cerr << "List created" << "\n";
}

bool LinkedList::empty() {return m_head == nullptr;}

void LinkedList::clear() {
    while(m_head != nullptr) {auto *aux = m_head; m_head = m_head->next; delete aux;}
    m_size = 0;
}

LinkedList::~LinkedList() {clear(); std::cerr << "Destroyed list" << "\n";}

int LinkedList::size() {return m_size;}

void LinkedList::push_back(Item data) {
    auto *newNode = new Node(data, nullptr);
    if(m_head == nullptr) { m_head = newNode; m_size++;} // lista vazia
    else { // 1 ou + nós
        Node *atual = m_head;
        while(atual->next != nullptr) {atual = atual->next;}
        atual->next = newNode;
        m_size++;
    }
}

void LinkedList::pop_back() {
    if(empty()) { throw std::out_of_range("erro: lista vazia");} // Caso 1: lista vazia

    if(m_head->next == nullptr) { // Caso 2: lista com 1 nó apenas
        delete m_head;
        m_head = nullptr;
        m_size--;
        return;
    }
    // Caso 3 : lista com 2 ou + nós
    auto *aux = m_head;
    while(aux->next->next != nullptr) { aux = aux->next;}
    delete aux->next;
    aux->next = nullptr;
    m_size--;
}

std::ostream& operator<<(std::ostream& out, const LinkedList& l) {
    out << "(" << l.m_size << ") ";
    out << "[ ";
    auto *aux = l.m_head;
    while(aux != nullptr) { out << "(" << aux->data << ") "; aux = aux->next;}
    out << "]";
    return out;
}

main.cpp

#include <iostream>
#include "LinkedList.h"
using namespace std;

int main() {    
    LinkedList list;
    cout << boolalpha << list.empty() << endl;

    list.push_back("Joao");
    list.push_back("Maria");
    list.push_back("Ana");
    list.push_back("Rafael");

    cout << "Lista preenchida: " << "\n";
    cout << list << "\n";

    cout << "Lista removendo o ultimo elemento ate que fique vazia:" << "\n";
    while(!list.empty()){ list.pop_back(); cout << list << "\n";}

    return 0;
}

arfneto · 6 de janeiro de 2022

Umas coisas que notei em seu programa

em Node

Não use typedef em C++. Não há razão.

A falta do construtor padrão pode dar problemas.

Exigir uma referência no único construtor pode ser muito limitante porque quem usar a lista não vai poder construir o elemento na hora --- emplace().

O uso de Item vai exigir que a classe seja trivialmente copiável, para você poder escrever

        data = d;

sem se preocupar.

Em geral deve marcar como const o Item no construtor.

Vai usar unique_ptr<Node> em Node ao invés de Node*. E de modo similar em LinkedList.

Para maior flexibilidade o comum é usar uma redefinição de << para Node na implementação da redefinição de << para LinkedList. Encapsulamento.

Pela mesma razão deve usar size em clear(). Mais seguro.

pop_back() deveria retornar Item provavelmente. E gerar uma exceção quando tentar um pop de uma lista vazia é provavelmente exagerado. De ao mens uma opção ao usuário de simplesmente seguir adiante. Retornando optional por exemplo. Ou um ponteiro para um novo Item.

<< poderia retornar o tamanho da lista antes de tudo e assim não precisaria de algo especial como

    LinkedList list;
    cout << boolalpha << list.empty() << endl;

e poderia claro escrever um "\n" ao final da listagem. E assim poderia escrever apenas

    LinkedList list;
    cout << list;
    list.push_back("Rafael");
    cout << list;

De todo modo esse tipo de aplicação --- container --- pode não ser um bom caso para uso de smart pointers. E talvez fosse mais simples usar shared_ptr e não unique_ptr nos nós da lista se for mesmo usar isso (smart pointers), porque shared_ptr conta as referências antes de destruir o node. O caso é que unique_ptr é o único DONO da área para a qual ele aponta. Não pode ser copiado por exemplo. E por isso é tão seguro. Mas quando você tem dentro dele outro unique_ptr precisa pensar muito bem no que está fazendo.

6 de janeiro de 2022

@arfneto Por hora vou continuar usando o método antigo de ir liberando a memória no manual e irei tentar aprender mais sobre smart ptr até me sentir seguro em usa-los, e como você disse, esse n parece um bom lugar pra fazer seu uso, mas valeu pela dica.

arfneto · 6 de janeiro de 2022

13 minutos atrás, Prodigy085 disse:

Por hora vou continuar usando o método antigo de ir liberando a memória no manual e irei tentar aprender mais sobre smart ptr até me sentir seguro em usa-los, e como você disse, esse n parece um bom lugar pra fazer seu uso, mas valeu pela dica.

Acho que uma implementação de lista não é mesmo um bom lugar porque a razão de usar smart pointers é simplificar as coisas e aqui vai complicar um pouco. Se você liberar um deles sem cuidado vai sumir um monte deles na mesma hora, e acho que é até mais difícil seguir assim do que usar new/delete, apesar de que o problema so iria aparecer na hora de apagar algum Node: você usaria move() ou get() para salvar o cara e colocar no Node correto. Em java ou Python ou javascript seria assim de qualquer forma então não pode ser assim difícil.

Entendeu o resto dos problemas de que falei?

Um teste mais automático

Como eu disse, se você mudar um pouco a definição de << pode ficar mais simples. Vou te mostrar uma maneira um pouco mais moderna de fazer isso, em C++20 mas que pode facilmente adaptar para C++11 ou mesmo C++98.

E se para testar usasse a própria classe LinkedList com um método cria_uns()?

    int cria_uns(size_t);

E esse método gentil criasse, fazendo justiça ao nome, um certo número de registros na lista, somente se ela estivesse vazia?

Podia escrever algo assim em main:

#include <iostream>
#include "LinkedList.h"
using namespace std;
int main(void)
{
    LinkedList list;
    cout << list;
    list.cria_uns(4);
    cout << list;
    return 0;
}

E inserir 4 elementos numeradinhos como "Item NNNNNN" na lista, para ficar fácil de conferir. O primeiro cout mostra a lista vazia, o segundo mostra os 4 caras e a vida segue. Muito mais simples e legível. E flexível porque pode testar logo mais com 42.000 elementos, já que é só um parâmetro.

Olha a saída

List created
(0 Elementos)
(4 Elementos)
[
        0001    (Item 000001)
        0002    (Item 000002)
        0003    (Item 000003)
        0004    (Item 000004)
]
Destroyed list

Como esperado. Muito mais simples que

    LinkedList list;
    cout << boolalpha << list.empty() << endl;

    list.push_back("Joao");
    list.push_back("Maria");
    list.push_back("Ana");
    list.push_back("Rafael");

    cout << "Lista preenchida: "
         << "\n";
    cout << list << "\n";

Em especial se quiser testar com meio milhão de itens.

Como seria uma função assim? Muito longa? Pode ser simples como 1 comando, em 6 linhas:

int LinkedList::cria_uns(size_t qtd)
{  // cancela se a lista não estiver vazia ou qtd for zero
    if ((m_size != 0) || (qtd == 0)) return -1;// sem sentido
    for (auto i : std::views::iota(1, 1 + (int)qtd))
        push_back(std::format("Item {:0>6}", i));
    return 0;
}

Claro, pode usar um for tipo C e sprintf() também.

E a implementação de <<?

Essa abaixo faz o serviço mas é melhor porque parte da redefinição de << para Node também. Isso quer dizer que se mudar Node não precisa mudar aqui.

std::ostream& operator<<(std::ostream& out, const LinkedList& l)
{
    out << "(" << l.m_size << " Elementos)\n";
    if (l.m_size == 0) return out;
    out << "[\n";
    Node* p = l.m_head;
    for (int i = 1; i <= l.m_size; i += 1)
        out << "\t" <<
        std::format("{:0>4}\t", i) << *p,
        p = p->next;
    out << "]\n";
    return out;
}

O Exemplo todo

node.h (header-only)

#ifndef NODE_H
#define NODE_H
#include <string>

using Item = std::string;

struct Node
{
    Item  data;
    Node* next;

    Node(Item& d, Node* n)
    {
        data = d;
        next = n;
    }

    friend
    std::ostream& operator<<(std::ostream& out, const Node& node)
    {
        out << "(" << node.data << ")\n";
        return out;
    }
};
#endif

LinkedList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <iostream>
#include "Node.h"

class LinkedList
{
   private:
    Node* m_head;
    int   m_size;

   public:
    LinkedList();
    ~LinkedList();

   public:
    bool empty();
    void clear();
    int  size();
    void push_back(Item data);
    void pop_back();

    int cria_uns(size_t);

    friend std::ostream& operator<<(
        std::ostream& out, const LinkedList& l);
};
#endif

LinkedList.cpp

#include <format>
#include <iostream>
#include <ranges>
#include <sstream>

#include "LinkedList.h"

LinkedList::LinkedList()
{
    m_size = 0;
    m_head = nullptr;
    std::cerr << "List created"
              << "\n";
}

bool LinkedList::empty() { return m_head == nullptr; }

void LinkedList::clear()
{
    while (m_head != nullptr)
    {
        auto* aux = m_head;
        m_head    = m_head->next;
        delete aux;
    }
    m_size = 0;
}

LinkedList::~LinkedList()
{
    clear();
    std::cerr << "Destroyed list"
              << "\n";
}

int LinkedList::size() { return m_size; }

void LinkedList::push_back(Item data)
{
    auto* newNode = new Node(data, nullptr);
    if (m_head == nullptr)
    {
        m_head = newNode;
        m_size++;
    }  // lista vazia
    else
    {  // 1 ou + nós
        Node* atual = m_head;
        while (atual->next != nullptr) { atual = atual->next; }
        atual->next = newNode;
        m_size++;
    }
}

void LinkedList::pop_back()
{
    if (empty())
    {
        throw std::out_of_range("erro: lista vazia");
    }  // Caso 1: lista vazia

    if (m_head->next == nullptr)
    {  // Caso 2: lista com 1 nó apenas
        delete m_head;
        m_head = nullptr;
        m_size--;
        return;
    }
    // Caso 3 : lista com 2 ou + nós
    auto* aux = m_head;
    while (aux->next->next != nullptr) { aux = aux->next; }
    delete aux->next;
    aux->next = nullptr;
    m_size--;
}

std::ostream& operator<<(std::ostream& out, const LinkedList& l)
{
    out << "(" << l.m_size << " Elementos)\n";
    if (l.m_size == 0) return out;
    out << "[\n";
    Node* p = l.m_head;
    for (int i = 1; i <= l.m_size; i += 1)
        out << "\t" <<
        std::format("{:0>4}\t", i) << *p,
        p = p->next;
    out << "]\n";
    return out;
}

int LinkedList::cria_uns(size_t qtd)
{  // cancela se a lista não estiver vazia
    if ((m_size != 0) || (qtd == 0)) return -1;// sem sentido
    for (auto i : std::views::iota(1, 1 + (int)qtd))
        push_back(std::format("Item {:0>6}", i));
    return 0;
}

main.cpp

#include <iostream>
#include "LinkedList.h"
using namespace std;
int main(void)
{
    LinkedList list;
    cout << list;
    list.cria_uns(4);
    cout << list;
    return 0;
}

Não entrei no mérito de como escreveu a classe. Apenas mudei umas poucas linhas para mostrar uma maneira (supostamente) mais ágil de testar.

7 de janeiro de 2022

@arfneto Boa noite, não conseguir incluir a lib <format> e nem a <ranges>, então n pude compilar. Meu GCC é da versão 6.3.0, o C++ acredito ser C++17.

5 horas atrás, arfneto disse:

Claro, pode usar um for tipo C e sprintf() também.

Essa seria a solução para meu caso? Ou posso tentar atualizar meu C++?

arfneto · 7 de janeiro de 2022

@Prodigy085 Você entendeu a ideia da função cria_uns() e a diferença na implementação de << para as classes como eu expliquei e como você tinha escrito?

17 minutos atrás, Prodigy085 disse:

Essa seria a solução para meu caso? Ou posso tentar atualizar meu C++?

As coisas estão bem devagar por causa da pandemia e apenas o compilador da Microsoft tem praticamente todo o C++20 implementado e permite usar <ranges> e <format> direto dos headers. Para os outros como o gcc e clang na Apple em geral ainda é preciso usar outras bibliotecas enquanto não aparece isso.

21 minutos atrás, Prodigy085 disse:

Meu GCC é da versão 6.3.0, o C++ acredito ser C++17.

Isso é muito antigo. Sugiro atualizar para algo como versão 9 ou 10. 11.2 é a versão corrente desde julho/21.

De todo modo C++17 é o mínimo para o exemplo que vou te mostrar

Fiquei curioso pelo lance dos smart pointers em containers. Eu nunca tinha programado um container em C++ até onde eu me lembro, exceto por coisas especializadas e não algo que tenha na biblioteca. Um dia desses postei uma lista bem comum em C++ aqui neste forum para ajudar alguém, mas não me lembro dos detalhes.

E a opinião que te dei antes sobre ser mais complicado usar unique_ptr<> numa lista foi sem pensar muito ou tentar escrever. É a opinião comum e todo mundo diz isso.

Mas fiquei mesmo curioso. Como sua implementação só tem ponteiros para um lado nem é preciso usar shared_ptr(). Porque? porque numa lista comum cada nó é apontado por dois e assim o ponteiro não pode claro ser unique_ptr<>: o anterior e o próximo apontam para ele.

Claro, é muito mais complicado programar uma lista com ponteiros para um lado só e imagino que você tenha uma boa razão para isso e não a simples busca por sofrimento.

Assim, um exemplo de lista usando smart pointers segue abaixo

Minha conclusão é de que ficou mesmo bem mais simples.

Sobre o C++20 e o exemplo

Essa é uma mudança enorme da linguagem e vai de fato mudar a maneira como se programa em C++. Em especial módulos, co-rotinas, ranges e concepts. Como aqui é um forum é um lugar legal para colocar um pouco disso sempre que possível, eu acho, mas por enquanto está difícil de compilar fora da MS.

Vou aproveitar esse e deixar um exemplo mais ou menos profissional anos 70 de tratar isso.

Usando #define e o preprocessador para manter os exemplos compiláveis

// 
// sem o compilador certo não da para
// usar <ranges> nem <format>
//
//#define CPP23__

#ifndef CPP23__
    #include <cstdio>
#else
    #include <format>
    #include <ranges>
#endif

Então se retirar o comentário no #define CPP23__ o compilador vai ver os includes de <ranges> e <format> e se deixar como está vai incluir stdio.h de C para poder usar sprintf().

Acho que deu para entender. Isso é usado para poder compilar em C++17 mudando só uma linha.

Usando unique_ptr na classe Node: node.h

#ifndef NODE_H
#define NODE_H


#include <iostream>
#include <memory>
#include <string>

using Item = std::string;

struct Node
{
    Item                  data;
    std::unique_ptr<Node> next;
    explicit Node(Item& d) : data(d) { next.release(); }
    ~Node()
    {
        std::cerr << "Destruindo Node \"" << data << "\"\n";
    }
    friend std::ostream& operator<<(
        std::ostream& out, const Node& node)
    {
        out << "(" << node.data << ")\n";
        return out;
    }
};
#endif

Ficou mais simples. O construtor não precisa de dois parâmetros porque next não vai apontar para p. nenhuma.

O destrutor poderia ser omitido, Eu deixei o cerr apenas para demonstrar o efeito do smart pointer.

Como expliquei antes a redefinição de << para Node é por uma questão de encapsulamento. Veja o código de << para a lista e vai entender.

Usando unique_ptr na classe LinkedList

No meu exemplo mudei um pouco as coisas:

m_head é agora um smart pointer
os dois using servem apenas para economizar na digitação.
pop_back() retorna um std::optional ao invés de gerar uma exceção como no seu código. Assim se a lista estiver vazia não retorna nada. Isso exige C++17, mas por ser um exemplo acho que vale a pena você entender.
cria_uns() claro é a função que enche a lista com o número pedido de elementos, numerados para simplificar os testes.

LinkedList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <iostream>
#include <optional>
using namespace std;
#include "Node.h"

using Upn = std::unique_ptr<Node>;
using Ost = std::ostream;

class LinkedList
{
   private:
    Upn m_head;
    int m_size;

   public:
    LinkedList();
    ~LinkedList();

   public:
    bool           empty();
    void           clear();
    int            size();
    void           push_back(Item data);
    optional<Item> pop_back();

    int cria_uns(size_t);

    friend Ost& operator<<(
        Ost& out, const LinkedList& l);
};

#endif

Uma implementação da classe LinkedList

Veja o construtor e o destrutor da lista: não tem código porque é tudo automático.

LinkedList::LinkedList() : m_head(nullptr), m_size(0)
{
    std::cerr << "Lista criada\n";
}

LinkedList::~LinkedList()
{
    std::cerr << "Lista destruida."
                 " Os Nodes não tem mais dono\n";
}

clear() é trivial

graças aos amigos criadores da STL em C++11 a lista e os nodes se apagam sozinhos na ordem certa.

void LinkedList::clear()
{
    m_size = 0;
    m_head.reset();
}

push_back() é mais simples

Como novo é um smart pointer ele se vira com os links apenas chamando swap() na ordem certa.

void LinkedList::push_back(Item data)
{  // insere no inicio
    Upn novo(new Node(data));
    if (m_size == 0)
    {
        m_head.swap(novo);
        m_size = 1;
        return;
    }
    novo->next.swap(m_head);
    m_head.swap(novo);
    m_size += 1;
}

pop_back() é bem mais simples também

Basta trocar o ponteiro m_head pelo seu sucessor e -- como em java ---- o Node anterior sai de escopo e é apagado.

optional<Item> LinkedList::pop_back()
{
    if (empty()) return {};
    Item primeiro = m_head->data;
    m_head.swap(m_head->next);
    m_size = m_size - 1;
    return primeiro;
}

E como retorna um optional se a lista está vazia apenas não retorna nada. Assim não precisa retornar um std::pair<bool,Item> que seria o comum.

O << em C++98

Cortesia de C, sprintf() era o <format> em 1980.

    Ost& operator<<(
        Ost& out, const LinkedList& l)
    {
        out << "(" << l.m_size << " Elementos)\n";
        if (l.m_size == 0) return out;
        out << "[\n";
        Node* p = l.m_head.get();
        char  num[10]{};
        for (int i = 1; i <= l.m_size; i += 1)
            sprintf(num, "%04d\t", i),
                out << "\t" << string(num) << *p,
                p = p->next.get();
        out << "]\n";
        return out;
    }

cria_uns() em C+98

Da mesma forma,

    int LinkedList::cria_uns(size_t qtd)
    {  // cancela se a lista não estiver vazia
        if ((m_size != 0) || (qtd == 0))
            return -1;  // sem sentido
        char item[20]{};
        for (size_t i = 0; i < qtd; i += 1)
            sprintf(item, "Item %06d", (qtd - i)),
            push_back(string(item));
        return 0;
    }

O programa de teste

Claro que foi copiado do anterior

    LinkedList list;
    cout << list;
    cout << "Extraido primeiro valor = "
         << list.pop_back().value_or("[Lista Vazia]") << "\n";

Cria a lista e mostra na tela. Claro que está vazia. Depois tenta extrair o primeiro elemento. Como é um optional e a lista está vazia dá pra imaginar o que vai retornar, certo?

    // insere 4 e lista
    auto t = 4;
    cout << "Inserindo " << t << " elementos:\n";
    list.cria_uns(4);
    cout << list;

Como antes, cria 4 ou 400.000 elementos na lista com os nomes "Item NNNNNN". E lista

    // apaga o primeiro
    cout << "Extraido primeiro valor = "
         <<
        list.pop_back().value_or("[Lista Vazia]\n") << "\n";
    cout << list;

Agora para testar pop_back() apaga o primeiro e lista o que sobrou. Como pop_back() retorna nesse caso um Item pode usar direto no cout para ver o valor na tela... Sem frescura.

E o list deve mostrar que apagou o primeiro, claro.

    // clear()
    // tenta apagar todo mundo no automatico
    cout << "\n====> testando clear()\n";
    list.clear();
    cout << "\n====> retornou de clear()\n";
    cout << list;  // vazia claro
    return 0;

E o fim da linha: clear apaga tudo, mas sem código. relembrando:

void LinkedList::clear()
{
    m_size = 0;
    m_head.reset();
}

O reset() em m_head destrói TUDO. E faz sentido. De que serve uma lista sem início? Sem m_head todo mundo fica orfão e a lista se apaga sozinha seguida por todos os Nodes. Sozinho, python-like.

A saída do exemplo

Lista criada
(0 Elementos)
Extraido primeiro valor = [Lista Vazia]
Inserindo 4 elementos:
(4 Elementos)
[
        0001    (Item 000001)
        0002    (Item 000002)
        0003    (Item 000003)
        0004    (Item 000004)
]
Extraido primeiro valor = Item 000001
(3 Elementos)
[
        0001    (Item 000002)
        0002    (Item 000003)
        0003    (Item 000004)
]

====> testando clear()
Destruindo Node "Item 000002"
Destruindo Node "Item 000003"
Destruindo Node "Item 000004"

====> retornou de clear()
(0 Elementos)
Lista destruida. Os Nodes não tem mais dono

main.cpp completo

#include <iostream>
#include "LinkedList.h"
using namespace std;
int main(void)
{
    LinkedList list;
    cout << list;
    cout << "Extraido primeiro valor = "
         << list.pop_back().value_or("[Lista Vazia]") << "\n";


    // insere 4 e lista
    auto t = 4;
    cout << "Inserindo " << t << " elementos:\n";
    list.cria_uns(4);
    cout << list;


    // apaga o primeiro
    cout << "Extraido primeiro valor = "
         <<
        list.pop_back().value_or("[Lista Vazia]\n") << "\n";
    cout << list;

    // clear()
    // tenta apagar todo mundo no automatico
    cout << "\n====> testando clear()\n";
    list.clear();
    cout << "\n====> retornou de clear()\n";
    cout << list;  // vazia claro
    return 0;
}

LinkedList.cpp com o #define

// 
// sem o compilador certo não da para
// usar <ranges> nem <format>
//
//#define CPP23__

#ifndef CPP23__
    #include <cstdio>
#else
    #include <format>
    #include <ranges>
#endif

#include <iostream>
#include "LinkedList.h"

LinkedList::LinkedList() : m_head(nullptr), m_size(0)
{
    std::cerr << "Lista criada\n";
}

LinkedList::~LinkedList()
{
    std::cerr << "Lista destruida."
                 " Os Nodes não tem mais dono\n";
}

bool LinkedList::empty() { return m_size == 0; }

void LinkedList::clear()
{
    m_size = 0;
    m_head.reset();
}


int LinkedList::size() { return m_size; }

void LinkedList::push_back(Item data)
{  // insere no inicio
    Upn novo(new Node(data));
    if (m_size == 0)
    {
        m_head.swap(novo);
        m_size = 1;
        return;
    }
    novo->next.swap(m_head);
    m_head.swap(novo);
    m_size += 1;
}

optional<Item> LinkedList::pop_back()
{
    if (empty()) return {};
    Item primeiro = m_head->data;
    m_head.swap(m_head->next);
    m_size = m_size - 1;
    return primeiro;
}

// essas duas funcoes dependem de <ranges> e <format>
// e se não tiver isso usa C e sprintf()
#ifndef CPP23__

    Ost& operator<<(
        Ost& out, const LinkedList& l)
    {
        out << "(" << l.m_size << " Elementos)\n";
        if (l.m_size == 0) return out;
        out << "[\n";
        Node* p = l.m_head.get();
        char  num[10]{};
        for (int i = 1; i <= l.m_size; i += 1)
            sprintf(num, "%04d\t", i),
                out << "\t" << string(num) << *p,
                p = p->next.get();
        out << "]\n";
        return out;
    }

    int LinkedList::cria_uns(size_t qtd)
    {  // cancela se a lista não estiver vazia
        if ((m_size != 0) || (qtd == 0))
            return -1;  // sem sentido
        char item[20]{};
        for (size_t i = 0; i < qtd; i += 1)
            sprintf(item, "Item %06d", (qtd - i)),
            push_back(string(item));
        return 0;
    }

#else

    Ost& operator<<(
        Ost& out, const LinkedList& l)
    {
        out << "(" << l.m_size << " Elementos)\n";
        if (l.m_size == 0) return out;
        out << "[\n";
        Node* p = l.m_head.get();
        for (int i = 1; i <= l.m_size; i += 1)
            out << "\t" << std::format("{:0>4}\t", i) << *p,
                p = p->next.get();
        out << "]\n";
        return out;
    };

    int LinkedList::cria_uns(size_t qtd)
    {  // cancela se a lista não estiver vazia
        if ((m_size != 0) || (qtd == 0))
            return -1;  // sem sentido
        for (auto i : std::views::iota(0, (int)qtd))
            push_back(std::format("Item {:0>6}", qtd - i));
        return 0;
    }

#endif

7 de janeiro de 2022

@arfneto

16 horas atrás, arfneto disse:

Você entendeu a ideia da função cria_uns() e a diferença na implementação de << para as classes como eu expliquei e como você tinha escrito?

Eu entendi que cria_uns() cria uma lista com o tamanho que eu quiser, desde que esteja vazia, e << imprime a lista bem legível com os elementos e suas posições. Porém eu fiquei em dúvida na implementação dos elementos na lista. Na minha cabeça, ficaria assim:

LinkedList list;
    cout << list;
    cout << "Extraido primeiro valor = "
         << list.pop_back().value_or("[Lista Vazia]") << "\n";


    // insere 3 e lista
    auto t = 3;
    cout << "Inserindo " << t << " elementos:\n";

    list.push_back("Ana");
    list.push_back("Rafael");
    list.push_back("Maria");

    list.cria_uns(3);
    cout << list << "\n";

    // apaga o primeiro
    cout << "Extraido primeiro valor = "
         <<
        list.pop_back().value_or("[Lista Vazia]\n") << "\n";
    cout << list;

    // clear()
    // tenta apagar todo mundo no automatico
    cout << "\n====> testando clear()\n";
    list.clear();
    cout << "\n====> retornou de clear()\n";
    cout << list;  // vazia claro
    
    return 0;

Para imprimir isso:

Lista criada
(0 Elementos)
Extraido primeiro valor = [Lista Vazia]
Inserindo 3 elementos:
(3 Elementos)
[
        0001    (Maria)
        0002    (Rafael)
        0003    (Ana)
]

Extraido primeiro valor = Maria
(2 Elementos)
[
        0001    (Rafael)
        0002    (Ana)
]

====> testando clear()
Destruindo Node "Rafael"
Destruindo Node "Ana"

====> retornou de clear()
(0 Elementos)
Lista destruida. Os Nodes não tem mais dono

.

16 horas atrás, arfneto disse:

Isso é muito antigo. Sugiro atualizar para algo como versão 9 ou 10. 11.2 é a versão corrente desde julho/21.

Consegui instalar o mingw-gcc 11.2.0 e pude compilar o programa, nesse a lib <ranges> estava inclusa então só precisei incluir a <cstdio> e usar aquela implementação com sprintf().

16 horas atrás, arfneto disse:

O reset() em m_head destrói TUDO. E faz sentido. De que serve uma lista sem início? Sem m_head todo mundo fica orfão e a lista se apaga sozinha seguida por todos os Nodes. Sozinho, python-like.

Eu imaginava que destruindo apenas m_head não teríamos mais acesso aos nós, porém eles ainda ficariam ocupando memória enquanto o programa estivesse aberto.

16 horas atrás, arfneto disse:
explicit Node(Item& d) : data(d) { next.release(); }

Na minha implementação antiga eu usava dois argumentos, um para data e outro para indicar para onde o novo Node deve apontar, como no caso de push_back, onde o novoNode->next, por ser o final da lista, deve apontar para nullptr, next.release() faz isso?

Ontem eu criei a função insert para poder inserir elementos em qualquer "posição" i da lista, e note que na condição de index == 0 (código abaixo), eu já criei Node apontado para m_head para economizar uma linha.

Usando sua função explicit Node(arg1, arg2) eu criaria o Node e teria que aponta-lo para m_head em seguida?

A função está gigante porque fiz da primeira forma que veio na cabeça e foi feita para o meu código antigo sem smart ptr, mas acho que você entende minha dúvida. Segue o código:

void LinkedList::insert(int index, const Item& data) {
    //checar se index é valido
    if(index < 0 || index > m_size) {throw std::out_of_range("error");}
    // caso 1: lista vazia
    if(m_head == nullptr) {
        m_head = new Node(data, nullptr);
        m_size++;
        return;
    }
    if(index == 0) { // Index no indice 0
        auto *novo = new Node(data, m_head);
        m_head = novo;
        m_size++;
        return;
    }
    // caso 2: lista com pelo menos 1 elemento
    auto *novo = new Node(data, nullptr);
    int contador = 0;
    auto *aux = m_head;
    while(contador < index-1) {
        aux = aux->next;
        contador++;
    }
    novo->next = aux->next;
    aux->next = novo;
    m_size++;
}

16 horas atrás, arfneto disse:

Como novo é um smart pointer ele se vira com os links apenas chamando swap() na ordem certa.

void LinkedList::push_back(Item data)
{  // insere no inicio
    Upn novo(new Node(data));
    if (m_size == 0)
    {
        m_head.swap(novo);
        m_size = 1;
        return;
    }
    novo->next.swap(m_head);
    m_head.swap(novo);
    m_size += 1;
}

swap() está dizendo "m_head.deve apontar para(novo)" ? Ele diz para onde fulano deve apontar, é isso?

arfneto · 8 de janeiro de 2022

2 horas atrás, Prodigy085 disse:

Eu entendi que cria_uns() cria uma lista com o tamanho que eu quiser, desde que esteja vazia, e << imprime a lista bem legível com os elementos e suas posições. Porém eu fiquei em dúvida na implementação dos elementos na lista. Na minha cabeça, ficaria assim:

Não entendi. Todo o propósito de criar_uns() é você poder testar com valores conhecidos e não ter que ficar inventando nomes. E poder testar 5 ou 5 mill só mudando o número: Os elementos tem o nome com um prefixo e um número, Como "Item 000001" que viu lá.

Se vai usar um por um pra que usar t dizer quantos vai inserir? Não tem nenhum controle assim. E porque chamou cria_uns(3) se sabe que vai retornar direto?

2 horas atrás, Prodigy085 disse:

/ insere 3 e lista
    auto t = 3;
    cout << "Inserindo " << t << " elementos:\n";

    list.push_back("Ana");
    list.push_back("Rafael");
    list.push_back("Maria");

Considere o exemplo

// insere 3 e lista
    auto t = 3;
    cout << "Inserindo " << t << " elementos:\n";

    list.push_back("Ana");
    list.push_back("Ana");
    list.push_back("Ana");
    list.push_back("Ana");
    list.push_back("Rafael");
    list.push_back("Maria");
    list.push_back("Maria");
    list.push_back("Maria");
    list.push_back("Maria");

Vai mostrar 3 e vai criar 9 e se sumir algum ou duplicar não vai saber se foi erro ou de propósito... Essa é a ideia de numerar.

2 horas atrás, Prodigy085 disse:

Eu imaginava que destruindo apenas m_head não teríamos mais acesso aos nós, porém eles ainda ficariam ocupando memória enquanto o programa estivesse aberto

Então não entendeu o propósito de usar smart pointers. A ideia é que quando ficam sem uso o sistema apaga tudo sozinho. Não era por isso que queria tirar os delete de seu programa original? Por isso deixei os cerr com as mensagens, porque assim vê a Lista e os nós sendo destruídos na ordem inversa em que foram criados, bem como esperado. No automático. Como java ou Python mas sem pagar o preço em termos de velocidade ou flexibilidade.

2 horas atrás, Prodigy085 disse:

Na minha implementação antiga eu usava dois argumentos, um para data e outro para indicar para onde o novo Node deve apontar, como no caso de push_back, onde o novoNode->next, por ser o final da lista, deve apontar para nullptr, next.release() faz isso?

Não, não faz. O release() aí só para garantir que o ponteiro está livre, para quem está lendo.

Não precisa do segundo argumento justamente por estar usando unique_ptr. Eles não podem ser copiados. Por isso são seguros. E por isso se apagam por conta.

2 horas atrás, Prodigy085 disse:

Ontem eu criei a função insert para poder inserir elementos em qualquer "posição" i da lista, e note que na condição de index == 0 (código abaixo), eu já criei Node apontado para m_head para economizar uma linha.

2 horas atrás, Prodigy085 disse:

Usando sua função explicit Node(arg1, arg2) eu criaria o Node e teria que aponta-lo para m_head em seguida?

A função está gigante porque fiz da primeira forma que veio na cabeça e foi feita para o meu código antigo sem smart ptr, mas acho que você entende minha dúvida

Esse tópico e toda essa discussão é sobre usar smart pointers na implementação de um container.

insert() não vai funcionar assim. Rode o exemplo e pense com cuidado no mecanismo. Acho que viu que fia tudo mais simples, mas se mudar um ponteiro pode apagar um monte de gente. Tem que pensar de outro jeito.

Veja a implementação de << para LinkedList e de push_back() no exemplo e faça algo parecido. Navegue usando get() e insira usando swap().

2 horas atrás, Prodigy085 disse:

swap() está dizendo "m_head.deve apontar para(novo)" ? Ele diz para onde fulano deve apontar, é isso?

swap() é o clássico como std::swap(). Apenas troca os dois.

arfneto · 8 de janeiro de 2022

Você entendeu que aquele #define e o #ifdef como mostrei resolvem esse problema de usar um compilador antigo, @Prodigy085? E entendeu como funciona? Afinal já tinha vários desses no seu programa.

8 de janeiro de 2022

@arfneto São condições né, se o compilador encontrar as lib <format> e <ranges> ele vai usar o trecho de código que possui os comandos dessas lib, caso contrário vai incluir a <cstdio> e vai usar as funções com o comando sprintf().

No meu caso, joguei a LinkedList.cpp que você mandou, mas sempre ficava dando isso:

LinkedList.cpp:5:14: fatal error: format: No such file or directory
    5 |     #include <format>
      |              ^~~~~~~~
compilation terminated.

Aí eu apaguei todos #ifndef e #define, apaguei as funções << e cria_uns() que usavam comandos das lib <format> e <ranges> e deixei só aquelas que davam pra rodar usando só a <cstdio> e rodou certinho, assim:

#include <cstdio>
#include <iostream>
#include "LinkedList.h"

LinkedList::LinkedList() : m_head(nullptr), m_size(0)
{
    std::cerr << "Lista criada\n";
}

LinkedList::~LinkedList()
{
    std::cerr << "Lista destruida."
                 " Os Nodes não tem mais dono\n";
}

bool LinkedList::empty() { return m_size == 0; }

void LinkedList::clear()
{
    m_size = 0;
    m_head.reset();
}


int LinkedList::size() { return m_size; }

void LinkedList::push_back(Item data)
{  // insere no inicio
    Upn novo(new Node(data));
    if (m_size == 0)
    {
        m_head.swap(novo);
        m_size = 1;
        return;
    }
    novo->next.swap(m_head);
    m_head.swap(novo);
    m_size += 1;
}

optional<Item> LinkedList::pop_back()
{
    if (empty()) return {};
    Item primeiro = m_head->data;
    m_head.swap(m_head->next);
    m_size = m_size - 1;
    return primeiro;
}

Ost& operator<<(
    Ost& out, const LinkedList& l)
{
    out << "(" << l.m_size << " Elementos)\n";
    if (l.m_size == 0) return out;
    out << "[\n";
    Node* p = l.m_head.get();
    char  num[10]{};
    for (int i = 1; i <= l.m_size; i += 1)
        sprintf(num, "%04d\t", i),
            out << "\t" << string(num) << *p,
            p = p->next.get();
    out << "]\n";
    return out;
}

int LinkedList::cria_uns(size_t qtd)
{  // cancela se a lista não estiver vazia
    if ((m_size != 0) || (qtd == 0))
        return -1;  // sem sentido
    char item[20]{};
    for (size_t i = 0; i < qtd; i += 1)
        sprintf(item, "Item %06d", (qtd - i)),
        push_back(string(item));
    return 0;
}

arfneto · 8 de janeiro de 2022

6 minutos atrás, Prodigy085 disse:

Aí eu apaguei todos #ifndef e #define, apaguei as funções << e cria_uns() que usavam comandos das lib <format> e <ranges> e deixei só aquelas que davam pra rodar usando só a <cstdio> e rodou certinho, assim:

Isso quer dizer apenas que você desistiu e apagou tudo. É claro que vai funcionar. Mas não vai aprender nada com isso.

6 minutos atrás, Prodigy085 disse:

LinkedList.cpp:5:14: fatal error: format: No such file or directory
    5 |     #include <format>
      |              ^~~~~~~~
compilation terminated.

Entenda que só vai incluir <format> se CPP23__ estiver definido... É o que está escrito no arquivo que você copiou....

// 
// sem o compilador certo não da para
// usar <ranges> nem <format>
//
//#define CPP23__

#ifndef CPP23__
    #include <cstdio>
#else
    #include <format>
    #include <ranges>
#endif

Se tentou o #include então aquele símbolo estava definido...

8 de janeiro de 2022

10 minutos atrás, arfneto disse:

Entenda que só vai incluir <format> se CPP23__ estiver definido... É o que está escrito no arquivo que você copiou....

Tirei <ranges> porque agora tenho ela, então tô fazendo assim:

#define CPP23__
#ifndef CPP23__
    #include <cstdio>
#else
    #include <format>
#endif
#include <ranges>
#include <iostream>
#include "LinkedList.h"

E na parte das funções tá assim:

#ifndef CPP23__

    Ost& operator<<(
        Ost& out, const LinkedList& l)
    {
        out << "(" << l.m_size << " Elementos)\n";
        if (l.m_size == 0) return out;
        out << "[\n";
        Node* p = l.m_head.get();
        char  num[10]{};
        for (int i = 1; i <= l.m_size; i += 1)
            sprintf(num, "%04d\t", i),
                out << "\t" << string(num) << *p,
                p = p->next.get();
        out << "]\n";
        return out;
    }

    int LinkedList::cria_uns(size_t qtd)
    {  // cancela se a lista não estiver vazia
        if ((m_size != 0) || (qtd == 0))
            return -1;  // sem sentido
        char item[20]{};
        for (size_t i = 0; i < qtd; i += 1)
            sprintf(item, "Item %06d", (qtd - i)),
            push_back(string(item));
        return 0;
    }

#else

    Ost& operator<<(
        Ost& out, const LinkedList& l)
    {
        out << "(" << l.m_size << " Elementos)\n";
        if (l.m_size == 0) return out;
        out << "[\n";
        Node* p = l.m_head.get();
        for (int i = 1; i <= l.m_size; i += 1)
            out << "\t" << std::format("{:0>4}\t", i) << *p,
                p = p->next.get();
        out << "]\n";
        return out;
    };

    int LinkedList::cria_uns(size_t qtd)
    {  // cancela se a lista não estiver vazia
        if ((m_size != 0) || (qtd == 0))
            return -1;  // sem sentido
        for (auto i : std::views::iota(0, (int)qtd))
            push_back(std::format("Item {:0>6}", qtd - i));
        return 0;
    }

#endif

arfneto · 8 de janeiro de 2022

@Prodigy085 Muito bom!

arfneto · 9 de janeiro de 2022

@Prodigy085 Eu escrevi uma versão de insert usando unique_ptr e vou deixar aqui.

No geral acho mesmo que o programa ficou menor e mais fácil de ler. Mas é um outro jeito de pensar, porque se por um lado dá uma paz na mente de não ter que pensar na ordem, dos destrutores, nos delete e em RAII. Por outro lado um erro na lógica e a estrutura toda some

Esse exemplo é mais completo então sugiro marcar esse como resposta até aparecer uma resposta melhor, que pode ser o seu código revisado

Veja a versão de insert()

int LinkedList::insert(Item data, size_t pos)
{  // insere 'data' na posicao pos
    if (pos > (1 + m_size)) return -1;  // não da
    Upn novo(new Node(data));
    if (pos < 2)
    {  // aceita 0 ou 1 para o inicio
        novo->next.swap(m_head);
        m_head.swap(novo);  // novo inicio
        m_size += 1;
        return 0;
    };
    // avanca 'pos'- 2 Nodes
    Node* p = m_head.get();  // comeca aqui
    for (size_t i = 0; i < pos - 2; i += 1)
        p = p->next.get();
    // salva o sucessor desse
    Upn temp = std::move(p->next);
    novo->next.swap(temp);
    p->next.swap(novo);  // novo vem aqui
    m_size += 1;
    return 0;
}

que retorna -1 se a posição pedida é inválida.

Essa versão aceita 0 ou 1 para inserir no início e size()+1 para inserir no fim, porque sempre tem essa ambiguidade. Então se usar insert(,4) o novo registro vai ser o quarto e parece mais intuitivo assim. De todo modo é só um exemplo e é a minha versão.

Se existe insert(,n) então as outras ficam triviais...

Claro que insert(,1) ou insert(,0) inserem no início e insert(,1+size()) insere no fim então dá para escrever push_front() e push_back() para inserir no início e no fim da lista como esperado, usando insert():

int LinkedList::push_back(Item data)
{  // insere no final
    return insert(data, 1 + m_size);
}

int LinkedList::push_front(Item data)
{  // insere no inicio
    return insert(data, 1);
}

O código

node.h

#ifndef NODE_H
#define NODE_H


#include <iostream>
#include <memory>
#include <string>

using Item = std::string;

struct Node
{
    Item data;
    std::unique_ptr<Node> next;
    explicit Node(Item& d) : data(d) { next.release(); }
    ~Node()
    {
        std::cerr << "Destruindo Node \"" << data << "\"\n";
    }
    friend std::ostream& operator<<(
        std::ostream& out, const Node& node)
    {
        out << "(" << node.data << ")\n";
        return out;
    }
};
#endif

LinkedList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <iostream>
#include <optional>
using namespace std;
#include "Node.h"

using Ost = std::ostream;
using Upn = std::unique_ptr<Node>;

class LinkedList
{
   private:
    Upn    m_head;
    size_t m_size;

   public:
    LinkedList();
    ~LinkedList();

   public:
    void clear();
    bool empty();
    int  insert(Item data, size_t pos);
    [[nodiscard]] optional<Item> pop_back();
    [[nodiscard]] optional<Item> pop_front();
    int                          push_back(Item data);
    int                          push_front(Item data);
    int                          size();

    // para teste
    int cria_uns(size_t);

    friend Ost& operator<<(Ost& out, const LinkedList& l);
};

#endif

Inclui os atributos [[nodiscard]] --- C++17 --- em pop_back() e pop_front() para mostrar como a linguagem evolui e a razão das coisas.

Ao retirar um cara da lista se não colocar em algum lugar o compilador vai avisar. Porque isso é bom? Porque vai tirar um cara da lista e ele vai desaparecer. Pode muito bem ser um erro do programa. E erros custam tempo e dinheiro.

Exemplo

    cout << "\nTenta retirar o ultimo duas vezes\n";
    auto ultimo = list.pop_back();
    cout << "Ultimo: \"" << ultimo.value_or("Lista Vazia")
         << "\"\n";
    ultimo = list.pop_back();
    cout << "Ultimo: \"" << ultimo.value_or("Lista Vazia!")
         << "\"\n";

Isso está certo e tira os 2 últimos caras da lista e mostra na tela. Está no exemplo e mostra algo assim

        0014    (F I N A L +2)
        0015    (F I N A L +3)
]

Tenta retirar o ultimo duas vezes
Destruindo Node "F I N A L +3"
Ultimo: "F I N A L +3"
Destruindo Node "F I N A L +2"
Ultimo: "F I N A L +2"

Claro que foi escrito com recortar e colar . Mas e se por engano fosse digitado assim

    cout << "\nTenta retirar o ultimo duas vezes\n";
    auto ultimo = list.pop_back();
    cout << "Ultimo: \"" << ultimo.value_or("Lista Vazia")
         << "\"\n";
    list.pop_back();
    cout << "Ultimo: \"" << ultimo.value_or("Lista Vazia!")
         << "\"\n";

O programa ainda tira os dois caras, mas faltou atribuir o ítem extraido. Era pra ser ultimo = list.pop_back(); ao invés de list.pop_back(); só. E agora vai mostrar

        0014    (F I N A L +2)
        0015    (F I N A L +3)
]

Tenta retirar o ultimo duas vezes
Destruindo Node "F I N A L +3"
Ultimo: "F I N A L +3"
Destruindo Node "F I N A L +2"
Ultimo: "F I N A L +3"

repetindo o último valor errado... Claro que aqui fica óbvio porque o destrutor do Node é chamado automaticamente e mostra que o Node sendo apagado é outro. Mas o normal seria

        0014    (F I N A L +2)
        0015    (F I N A L +3)
]

Tenta retirar o ultimo duas vezes
Ultimo: "F I N A L +3"
Ultimo: "F I N A L +3"

E alguém vai ter que descobrir como acontece uma coisa dessas. E se fosse em outro ponto de um programa enorme podia custar horas até descobrir que na pressa alguém esqueceu de atribuir o valor extraído...

Com o uso desse atributo quando compila o programa aparece C4834:

mainv3.cpp(73,9): warning C4834: discarding return value of function with 'nodiscard' attribute

e pelo menos avisa o programador de que algo POSSA estar errado. E aqui estava.

Em C++20

Em C++20 isso mudou e se pode até escrever a razão no aviso usando uma simples mensagem

    [[nodiscard("não usar o valor extraido pode ser uma grande bobagem. eu avisei")]]
    optional<Item> pop_back();

E ao compilar o compilador avisa

mainv3.cpp(73,9): warning C4858: discarding return value: não usar o valor extraido pode ser uma grande bobagem. eu avisei

E não é que estava errado mesmo?

De volta ao programa exemplo

Eis LinkedList.cpp

//
// sem o compilador certo não da para
// usar <ranges> nem <format>
//
//#define CPP23__

#ifndef CPP23__
#include <cstdio>
#else
#include <format>
#include <ranges>
#endif

#include <iostream>

#include "LinkedList.h"

LinkedList::LinkedList() : m_head(nullptr), m_size(0)
{
    std::cerr << "Lista criada\n";
}

LinkedList::~LinkedList()
{
    std::cerr << "Lista destruida."
                 " Os Nodes não tem mais dono\n";
}


void LinkedList::clear()
{
    m_size = 0;
    m_head.reset();
}

bool LinkedList::empty() { return m_size == 0; }

optional<Item> LinkedList::pop_back()
{                            // retorna e extrai o ultimo
    if (empty()) return {};  // o simples
    if (m_size == 1) return pop_front();
    // avanca ate o ultimo node
    Node* p = m_head.get();  // comeca aqui
    for (size_t i = 0; i < m_size - 2; i += 1)
        p = p->next.get();
    Upn ultimo = std::move(p->next);
    m_size     = m_size - 1;  // ajusta
    return ultimo->data;      // vai ser apagado a seguir
}

[[nodiscard]] optional<Item> LinkedList::pop_front()
{
    if (empty()) return {};
    Item primeiro = m_head->data;
    m_head.swap(m_head->next);
    m_size = m_size - 1;
    return primeiro;
}

int LinkedList::push_back(Item data)
{  // insere no final
    return insert(data, 1 + m_size);
}

int LinkedList::push_front(Item data)
{  // insere no inicio
    return insert(data, 1);
}
int LinkedList::size() { return m_size; }

int LinkedList::insert(Item data, size_t pos)
{  // insere 'data' na posicao pos
    if (pos > (1 + m_size)) return -1;  // não da
    Upn novo(new Node(data));
    if (pos < 2)
    {  // aceita 0 ou 1 para o inicio
        novo->next.swap(m_head);
        m_head.swap(novo);  // novo inicio
        m_size += 1;
        return 0;
    };
    // avanca 'pos'- 2 Nodes
    Node* p = m_head.get();  // comeca aqui
    for (size_t i = 0; i < pos - 2; i += 1)
        p = p->next.get();
    // salva o sucessor desse
    Upn temp = std::move(p->next);
    novo->next.swap(temp);
    p->next.swap(novo);  // novo vem aqui
    m_size += 1;
    return 0;
}

// essas duas funcoes dependem de <ranges> e <format>
// e se não tiver isso usa C e sprintf()
#ifndef CPP23__

Ost& operator<<(Ost& out, const LinkedList& l)
{
    out << "(" << l.m_size << " Elementos)\n";
    if (l.m_size == 0) return out;
    out << "[\n";
    Node* p = l.m_head.get();
    char  num[10]{};
    for (size_t i = 1; i <= l.m_size; i += 1)
        sprintf(num, "%04d\t", i),
            out << "\t" << string(num) << *p,
            p = p->next.get();
    out << "]\n";
    return out;
}

int LinkedList::cria_uns(size_t qtd)
{  // cancela se a lista não estiver vazia
    if ((m_size != 0) || (qtd == 0))
        return -1;  // sem sentido
    char item[20]{};
    for (size_t i = 1; i <= qtd; i += 1)
        sprintf(item, "Item %06d", i),
            push_back(string(item));
    return 0;
}

#else

Ost& operator<<(Ost& out, const LinkedList& l)
{
    out << "(" << l.m_size << " Elementos)\n";
    if (l.m_size == 0) return out;
    out << "[\n";
    Node* p = l.m_head.get();
    for (int i = 1; i <= l.m_size; i += 1)
        out << "\t" << std::format("{:0>4}\t", i) << *p,
            p = p->next.get();
    out << "]\n";
    return out;
};

int LinkedList::cria_uns(size_t qtd)
{  // cancela se a lista não estiver vazia
    if ((m_size != 0) || (qtd == 0))
        return -1;  // sem sentido
    for (auto i : std::views::iota(0, (int)qtd))
        push_back(std::format("Item {:0>6}", qtd - i));
    return 0;
}

#endif

E o código do teste

#include <iostream>
#include "LinkedList.h"
using namespace std;
int main(void)
{
    LinkedList list;
    cout << list;
    cout << "Tentando extrair primeiro valor = "
        << list.pop_back().value_or("[Lista Vazia]") << "\n";

    // chama insert na lista vazia
    cout << "Tenta inserir terceiro elemento\n";
    auto res = list.insert("Item 000000", 3);
    cout << "retornou " << res << "\n";
    cout << list;

    cout << "Tenta inserir na posicao 0\n";
    list.insert("Item 0", 0);
    cout << list;

    cout << "Tenta retirar o primeiro duas vezes\n";
    auto primeiro = list.pop_front();
    cout << "Primeiro: \"" << primeiro.value_or("Lista Vazia")
             << "\"\n";
    primeiro = list.pop_front();
    cout << "Primeiro: \""
         << primeiro.value_or("Lista Vazia!") << "\"\n";

    // insere 4 e lista
    auto t = 7;
    cout << "Inserindo " << t << " elementos:\n";
    list.cria_uns(t);
    cout << list;

    // insere um cara no inicio
    cout << "\nTenta inserir no inicio\n";
    list.insert("No inicio", 0);
    cout << list;

    cout << "\nTenta inserir de novo no inicio\n";
    list.insert("Novo inicio", 1);
    cout << list;

    cout << "\nTenta inserir no final\n";
    list.insert("F I N A L", list.size());
    cout << list;

    cout << "\nTenta inserir +1 no final\n";
    list.insert("F I N A L +1", list.size());
    cout << list;

    cout << "\nTenta inserir depois do final\n";
    list.insert("F I N A L +2", 1 + list.size());
    cout << list;

    cout << "\nTenta inserir depois do final\n";
    list.insert("F I N A L +3", 1 + list.size());
    cout << list;

    cout << "\nTenta inserir um segundo registro\n";
    list.insert("SEGUNDO REGISTRO", 2);
    cout << list;

    cout << "\nTenta inserir um quinto registro\n";
    list.insert("QUINTO REGISTRO", 5);
    cout << list;


    cout << "\nTenta retirar o ultimo duas vezes\n";
    auto ultimo = list.pop_back();
    cout << "Ultimo: \"" << ultimo.value_or("Lista Vazia")
         << "\"\n";
    ultimo = list.pop_back();
    cout << "Ultimo: \"" << ultimo.value_or("Lista Vazia!")
         << "\"\n";

    // clear()
    // tenta apagar todo mundo no automatico
    cout << "\n====> testando clear()\n";
    list.clear();
    cout << "\n====> retornou de clear()\n";
    cout << list;  // vazia claro
    return 0;
}

E a saída do EXEMPLO

Lista criada
(0 Elementos)
Tentando extrair primeiro valor = [Lista Vazia]
Tenta inserir terceiro elemento
retornou -1
(0 Elementos)
Tenta inserir na posicao 0
(1 Elementos)
[
        0001    (Item 0)
]
Tenta retirar o primeiro duas vezes
Primeiro: "Item 0"
Primeiro: "Lista Vazia!"
Inserindo 7 elementos:
(7 Elementos)
[
        0001    (Item 000001)
        0002    (Item 000002)
        0003    (Item 000003)
        0004    (Item 000004)
        0005    (Item 000005)
        0006    (Item 000006)
        0007    (Item 000007)
]

Tenta inserir no inicio
(8 Elementos)
[
        0001    (No inicio)
        0002    (Item 000001)
        0003    (Item 000002)
        0004    (Item 000003)
        0005    (Item 000004)
        0006    (Item 000005)
        0007    (Item 000006)
        0008    (Item 000007)
]

Tenta inserir de novo no inicio
(9 Elementos)
[
        0001    (Novo inicio)
        0002    (No inicio)
        0003    (Item 000001)
        0004    (Item 000002)
        0005    (Item 000003)
        0006    (Item 000004)
        0007    (Item 000005)
        0008    (Item 000006)
        0009    (Item 000007)
]

Tenta inserir no final
(10 Elementos)
[
        0001    (Novo inicio)
        0002    (No inicio)
        0003    (Item 000001)
        0004    (Item 000002)
        0005    (Item 000003)
        0006    (Item 000004)
        0007    (Item 000005)
        0008    (Item 000006)
        0009    (F I N A L)
        0010    (Item 000007)
]

Tenta inserir +1 no final
(11 Elementos)
[
        0001    (Novo inicio)
        0002    (No inicio)
        0003    (Item 000001)
        0004    (Item 000002)
        0005    (Item 000003)
        0006    (Item 000004)
        0007    (Item 000005)
        0008    (Item 000006)
        0009    (F I N A L)
        0010    (F I N A L +1)
        0011    (Item 000007)
]

Tenta inserir depois do final
(12 Elementos)
[
        0001    (Novo inicio)
        0002    (No inicio)
        0003    (Item 000001)
        0004    (Item 000002)
        0005    (Item 000003)
        0006    (Item 000004)
        0007    (Item 000005)
        0008    (Item 000006)
        0009    (F I N A L)
        0010    (F I N A L +1)
        0011    (Item 000007)
        0012    (F I N A L +2)
]

Tenta inserir depois do final
(13 Elementos)
[
        0001    (Novo inicio)
        0002    (No inicio)
        0003    (Item 000001)
        0004    (Item 000002)
        0005    (Item 000003)
        0006    (Item 000004)
        0007    (Item 000005)
        0008    (Item 000006)
        0009    (F I N A L)
        0010    (F I N A L +1)
        0011    (Item 000007)
        0012    (F I N A L +2)
        0013    (F I N A L +3)
]

Tenta inserir um segundo registro
(14 Elementos)
[
        0001    (Novo inicio)
        0002    (SEGUNDO REGISTRO)
        0003    (No inicio)
        0004    (Item 000001)
        0005    (Item 000002)
        0006    (Item 000003)
        0007    (Item 000004)
        0008    (Item 000005)
        0009    (Item 000006)
        0010    (F I N A L)
        0011    (F I N A L +1)
        0012    (Item 000007)
        0013    (F I N A L +2)
        0014    (F I N A L +3)
]

Tenta inserir um quinto registro
(15 Elementos)
[
        0001    (Novo inicio)
        0002    (SEGUNDO REGISTRO)
        0003    (No inicio)
        0004    (Item 000001)
        0005    (QUINTO REGISTRO)
        0006    (Item 000002)
        0007    (Item 000003)
        0008    (Item 000004)
        0009    (Item 000005)
        0010    (Item 000006)
        0011    (F I N A L)
        0012    (F I N A L +1)
        0013    (Item 000007)
        0014    (F I N A L +2)
        0015    (F I N A L +3)
]

Tenta retirar o ultimo duas vezes
Destruindo Node "F I N A L +3"
Ultimo: "F I N A L +3"
Destruindo Node "F I N A L +2"
Ultimo: "F I N A L +2"

====> testando clear()
Destruindo Node "Novo inicio"
Destruindo Node "SEGUNDO REGISTRO"
Destruindo Node "No inicio"
Destruindo Node "Item 000001"
Destruindo Node "QUINTO REGISTRO"
Destruindo Node "Item 000002"
Destruindo Node "Item 000003"
Destruindo Node "Item 000004"
Destruindo Node "Item 000005"
Destruindo Node "Item 000006"
Destruindo Node "F I N A L"
Destruindo Node "F I N A L +1"
Destruindo Node "Item 000007"

====> retornou de clear()
(0 Elementos)
Lista destruida. Os Nodes não tem mais dono

Claro que é só recortar e colar muitas vezes.