Шаблонный двусвязный список

Я хотел бы пересмотреть то, что знал на шаблонных классах, поэтому подумал, что я напишу дважды связанный список, чтобы практиковать.

Это прекрасно работает, поэтому все хорошо и хорошо на этом фронте, но есть ли что-то, что я пропустил?

Текущие вещи, о которых я знаю:

  • Именование - может быть немного более явным
  • - т. е. указатели на узел узла, чтобы я мог (например) искать и удалять узел, содержащий определенное значение, без сканирования через список дважды.

Я планирую исправить /добавить это позже.

В частности, я смотрю в основном на отзывы о том, как я сделал шаблоны, и какие-либо проблемы с RAII, хотя я буду с радостью принимать дальнейшие отзывы.

Обратите внимание, что я использовал .h как заголовок интерфейса и .hpp для реализации, чтобы отделить интерфейс и реализацию (используя .hpp вместо .imp или аналогичный, как распознанный тип в моей системе). Я понимаю, что для того, чтобы шаблон работал для всех типов, он должен находиться в заголовке, иначе каждый тип, который нужно использовать, должен быть определен, правильно?

Я компилирую с помощью:

  

g ++ -std = c ++ 11 use_dllist.cpp -Wall -Wextra -pedantic -o dll.exe

dlllist.h:

#ifndef __d_l_list__
#define __d_l_list__
#include <string>
template<class T>class d_l_listnode
{
public:
   d_l_listnode* link[2] = {0,0};  //link[0] is headwise //link[1] is tailwise.
   T data;
};

template<class T> class d_l_list
{
    d_l_listnode<T>* end[2] = {0,0};  //end[0] is head end[1] is tail
    int node_count = 0;

    void deep_copy(d_l_list<T>& original,d_l_list<T>& destination);

public:
    d_l_list();
    d_l_list(d_l_list<T>&);
    d_l_list<T>& operator=(d_l_list<T>&);
    ~d_l_list();
    int  add_node(T data, int index);
    int  find_node(T data);
    bool del_node(int index);
    bool is_empty();
    int  get_node_count();
    void print_list(std::string delimiter);
    void print_list_debug();
};

#include "dllist.hpp"
#endif

dllist.hpp:

#include <iostream>

template<class T>
d_l_list<T>::d_l_list()
{
    node_count = 0;
    end[0] = NULL;
    end[1] = NULL;
}

template<class T>
void d_l_list<T>::deep_copy(d_l_list<T>& original, d_l_list<T>& destination)
{
  destination.node_count = 0;
  destination.end[0] = NULL;
  destination.end[1] = NULL;
  d_l_listnode<T>*current_node = original.end[1];
  while(current_node)
  {
    destination.add_node(current_node->data, 0);
    current_node = current_node->link[0];
  }
}

template<class T>
d_l_list<T>::d_l_list(d_l_list<T>& original)
{
  deep_copy(original, *this);
}

template<class T>
d_l_list<T>& d_l_list<T>::operator=(d_l_list<T>& original)
{
  deep_copy(original, *this);
  return *this;
}

template<class T>
d_l_list<T>::~d_l_list()
{    while(node_count){del_node(0);}}

template<class T>
void d_l_list<T>::print_list(std::string delimiter)
{
  d_l_listnode<T>* node = end[0];
  while(node)
  {
    std::cout << node->data << (node->link[1]?delimiter:"");
    node = node->link[1];
  }
  std::cout<<std::endl;
}

template<class T>
void d_l_list<T>::print_list_debug()
{
  std::cout<<"head: "<<end[0]<<":"<<(node_count?end[0]->link[0]:0)<<"\ntail: "<<end[1]<<":"<<(node_count?end[1]->link[1]:0)<<std::endl; //second should always print '0'. If not, problem.
  d_l_listnode<T>* node = end[0];
  while(node)
  {
    std::cout<<node->data<<"\t\t:"<<node<<"\t"<<node->link[0]<<"\t:"<<node->link[1]<<"\n";
    node = node->link[1];
  }
  std::cout<<std::endl;
}

template<class T>
int d_l_list<T>::get_node_count()
{
  return node_count;
}

template<class T>
int d_l_list<T>::find_node(T data)
{
  int index = 0;
  d_l_listnode<T>* current_node = end[0];
  while (current_node)
  {
    if (current_node->data == data)
      return index;
    current_node = current_node->link[1];
    index++;
  }
  return -1;
}

template<class T>
int d_l_list<T>::add_node(T data, int index)
{
  bool traversal_direction = true;

  if (index > node_count/2){
    index = node_count - index;
    traversal_direction = false;}

  if (index < 0)
    {index = 0;}

  d_l_listnode<T>* new_node = new d_l_listnode<T>;
  if (!new_node)
    {return -1;}

  new_node->data=data;

  if (!end[0])
  {
    end[0] = new_node;
    end[1] = new_node;
    node_count = 1;
    return 0;
  }

  d_l_listnode<T>* current_node = end[!traversal_direction];

  for (int i = 0; i < index && i < node_count; i++)
    {current_node = current_node->link[traversal_direction];}

  if (!(current_node->link[0]&&current_node->link[1]))
  {
    end[!traversal_direction] = new_node;
    new_node->link[!traversal_direction] = NULL;
  }
  else
  {
    new_node->link[!traversal_direction] = current_node->link[!traversal_direction];
    new_node->link[!traversal_direction]->link[traversal_direction] = new_node;
  }
  new_node->link[traversal_direction] = current_node;
  current_node->link[!traversal_direction] = new_node;

  node_count++;
  return traversal_direction?index:node_count-index-1;
}

template<class T>
bool d_l_list<T>::del_node(int index)
{
  if (!node_count) 
    {return false;}

  bool traversal_direction = true;

    if (index >= node_count/2)
    {
      index = node_count - index - 1;
      traversal_direction = false;
    }

    d_l_listnode<T>* current_node = end[!traversal_direction];

    if (index < 0)
      {index = 0;}

    for (int i = 0; i < index; i++)
      {current_node = current_node->link[traversal_direction];}

    for (int i = 0; i <= 1; i++)
    {
      if (!current_node->link[!i])
        {end[!i] = current_node->link[i];}
      else
        {current_node->link[!i]->link[i] = current_node->link[i];}
    }
  //}
  delete current_node;
  node_count--;
  return true;
}

use_dllist.cpp (просто что-то для реализации функций):

#include "dllist.h"
#include <iostream>
#include <climits>


void printout(d_l_list<int>& list)
{
    std::cout << "\nnumber of nodes: " << list.get_node_count() << std::endl;
    std::cout << "list contents:" << std::endl;
    list.print_list(", ");
}

int main()
{
    d_l_list<int> list;

    std::cout<<"created list" << std::endl;

    //printout(list);

    for (int i = 0; i<10; i++)
    {
        int j = list.add_node(i, 5);
        std::cout<<"added a node, value: "<<i<<", index: "<< j << std::endl;
    }

    printout(list);

    {
      std::cout<<"\nCopy Constructor:"<<std::endl;
      d_l_list<int> list2(list);
      printout(list2);
    }
    {
      std::cout<<"\nAssignment:"<<std::endl;
      d_l_list<int> list3 = list;
      printout(list3);
    }

    std::cout<<"\nfinding '8'" << std::endl;
    int index = list.find_node(8);
    std::cout<<"deleting '8' (index: "<<index<<")"<< std::endl;

    list.del_node(index);

    printout(list);

    std::cout<<"\ndeleting #1" << std::endl;
    list.del_node(1);

    printout(list);

    std::cout<<"\ndeleting #5" << std::endl;
    list.del_node(5);

    printout(list);

    std::cout<<"\ndeleting #INT_MAX ("<<INT_MAX<<")" << std::endl;
    list.del_node(INT_MAX);

    printout(list);

    while(list.get_node_count())
    {
      std::cout<<"\ndeleting #0" << std::endl;
      list.del_node(0);
      printout(list);
    }
}
11 голосов | спросил Baldrickk 7 +04002014-10-07T15:32:05+04:00312014bEurope/MoscowTue, 07 Oct 2014 15:32:05 +0400 2014, 15:32:05

2 ответа


15

Расширения файлов

Разделение интерфейса от реализации велико. Однако разделение .h /.hpp не очевидно. Наиболее частыми расширениями файлов, которые используются для файлов реализации, которые не могут попасть в файлы .cpp, являются: .inl (для inline) и .tpp (для ---- +: = 1 =: + ---- cpp). Я знаю, что хотя бы некоторые редакторы кода или IDE распознают расширение .inl (по крайней мере Code :: Blocks), но многие из них могут быть настроены так, чтобы распознавать дополнительные расширения. Попробуйте использовать что-то более очевидное, что .hpp для файла реализации.

Имена

Несколько замечаний, связанных с именами вообще:

  • Попробуйте написать имена препроцессоров в template, чтобы их можно было идентифицировать одним взглядом и не путать с обычным функции, имена классов или переменных.

  • Кроме того, имена заголовков заголовков неверны: имена с двойными символами подчеркивания (в любом месте имени) зарезервированы для исполнителей. Имена, начинающиеся с символа подчеркивания, за которым следует буква верхнего регистра, также зарезервированы для разработчиков . Хорошим хорошо сформированным именем для защиты заголовка будет FULL_CAPS_CASE, поскольку одиночные подчеркивания подчеркивания прекрасны.

  • По возможности попробуйте использовать имя введенного класса в шаблоне cass. Он позволяет писать сокращенный код и снижает затраты на обслуживание: если вы измените имя параметра шаблона, вам не придется редактировать строки, в которых вы использовали введенное имя класса. Например, ваш D_L_LIST_ станет следующим:

    operator=
  • d_l_list& operator=(d_l_list&); - это плохое имя для метода, поскольку вы уже знаете, что вы печатаете print_list. Лучшее имя может быть list, но позже мы увидим более идиоматический способ печати вещей.

print -correctness

Вы должны действительно принять во внимание const -correctness , что означает, что вы должны добавить const, чтобы указать, что объект не будут изменены:

  • const должен взять operator= вместо const d_l_list&, чтобы утверждать, что он не будет изменять назначенную переменную.

  • Все методы, которые не изменяют класс, должны быть помечены d_l_list&:

    const

    И таких методов много: bool is_empty() const; , print_list, print_list_debug, get_node_count и is_empty.

Печатные материалы

Идиоматический способ печати материалов на C ++ состоит в том, чтобы перегрузить find_node для operator<< и ваш тип. В вашем случае это должно быть:

std::ostream&

Обратите внимание, что перегруженный оператор является свободной функцией, а не методом класса.

Постоянная константа указателя

В настоящее время вы используете два разных способа представления константы нулевого указателя:

  • template<typename T> std::ostream& operator<<(std::ostream& stream, const d_l_list<T>& list) { // print stuff to stream... return stream; } , как в NULL.
  • end[0] = NULL;, как в 0.

Вы используете C ++ 11. Способ C ++ 11 для представления константы нулевого указателя: d_l_listnode* link[2] = {0,0};. Две строки выше могут быть переписаны как:

    nullptr литий>
  • end[0] = nullptr; литий>

Инициализаторы в классе и построение по умолчанию

Вы использовали инициализаторы в классе для инициализации по умолчанию для членов d_l_listnode* link[2] = {nullptr,nullptr};. Однако вы инициализировали их теми же значениями в конструкторе по умолчанию. Собственно, есливы используете явно установленный по умолчанию конструктор по умолчанию, он будет использовать инициализаторы в классе для инициализации членов. Поэтому вы можете просто определить его как таковой:

d_l_list

Используйте идиому копирования и свопинга

идиома копирования и свопинга - это идиома, которая позволяет писать правильный и короткий код. Короче говоря, копия должна быть записана в конструкторе копирования класса, а template<class T> d_l_list<T>::d_l_list() = default; должна полагаться на конструктор копирования для выполнения копии. Вот как это будет выглядеть для вашего класса:

operator=

Короче говоря, template<class T> d_l_list<T>::d_l_list(const d_l_list<T>& other) { // Uninitialized members use the // in-class initializers here, that's // why I left out the initialization part d_l_listnode<T>* current_node = other.end[1]; while(current_node) { this->add_node(current_node->data, 0); current_node = current_node->link[0]; } } template<class T> d_l_list<T>& d_l_list<T>::operator=(d_l_list<T> other) { swap(*this, other); return *this; } выполняет копию operator= благодаря конструктору копирования и затем меняет содержимое other и *this. Затем other разрушается, а его содержимое (исходное содержимое other). Сообщение, которое я связал, более подробно освещает и действительно стоит прочитать. В любом случае использование идиомы «копирование и своп» безопасно, достаточно эффективно и позволяет удалить метод *this.

ответил Morwenn 7 +04002014-10-07T16:28:03+04:00312014bEurope/MoscowTue, 07 Oct 2014 16:28:03 +0400 2014, 16:28:03
7

Несколько примечаний:

У вас есть этот код:

d_l_listnode* link[2] = {0,0};  //link[0] is headwise //link[1] is tailwise.
[...]
d_l_listnode<T>* end[2] = {0,0};  //end[0] is head end[1] is tail

и код клиента:

destination.end[0] = NULL;

В коде клиента (т. е. где вам нужно это знать) у вас нет очевидного способа узнать, что 0 означает хвост, не глядя в объявлении класса.

Вы можете определить перечисление, чтобы у вас было:

destination.end[left_link] = NULL;
destination.end[right_link] = NULL;

Это обеспечит согласованность кода клиента и улучшенную семантическую информацию.

Рассмотрим возможность внедрения итерационного доступа, совместимого с STL. Это позволит вам использовать класс с большим количеством идиоматических способов (например, выполнить операцию итерации для ввода и вывода потока и алгоритмов std: например, найти и отсортировать).

Рассмотрите возможность использования полных имен для классов (d_l_list по какой-то причине заставляет меня думать о «списке загрузки»). Также подумайте над вызовом класса bidi_list (или что-то подобное): тот факт, что он обеспечивает быстрый доступ для итерации и вставки, важен в клиентском коде; тот факт, что он реализован как связанный список, является просто детальностью реализации.

ответил utnapistim 7 +04002014-10-07T17:40:14+04:00312014bEurope/MoscowTue, 07 Oct 2014 17:40:14 +0400 2014, 17:40:14

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132