Ошибка сегмента STL, как реализация списка пропусков

Question

Я реализовывал скип-лист в стиле STL. Тип внутреннего узла выглядит так:

template <class N>
struct __skiplist_node
{
  typedef __skiplist_node<N>* __skiplist_node_pointer;
  N data;
  __skiplist_node_pointer prev;
  std::list<__skiplist_node_pointer> nexts;
};

Во внутреннем узле есть std:: list. Когда я хочу push_back __skiplist_node в списке nexts. Когда список пропусков создается во время выполнения. Это встречает сегментный недостаток. Backstrace отладки показывает:

#0  0x00007ffff63a6acf in std::__detail::_List_node_base::_M_hook(std::__detail::_List_node_base*) () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#1  0x000000000045e0f6 in _M_insert (this=<optimized out>, __x=<optimized out>, 
    __position=...) at /usr/include/c++/4.8/bits/stl_list.h:1554
#2  push_back (__x=<optimized out>, this=<optimized out>)
    at /usr/include/c++/4.8/bits/stl_list.h:1016
#3  repo::SkipList<ndn::Name, repo::tests::DatasetBase::DataSetNameCompare>::empty_initialize (this=<optimized out>)
    at /home/chenatu/workspace/repo-ng/src/storage/skiplist.hpp:118
#4  0x000000000045ed1b in SkipList (this=0x7fffffffcfd0)
    at /home/chenatu/workspace/repo-ng/src/storage/skiplist.hpp:124
#5  repo::tests::SkipList::NdnNameSkipList<repo::tests::BaseTestFixture>::test_method (this=this@entry=0x7fffffffd070) at ../tests/unit/skiplist.cpp:40
#6  0x000000000045efd9 in run<repo::tests::BaseTestFixture> ()
    at ../tests/unit/skiplist.cpp:38
#7  operator() (this=<optimized out>)
    at /usr/include/boost/test/unit_test_suite_impl.hpp:357
#8  invoke<boost::unit_test::ut_detail::test_case_template_invoker<repo::tests::SkipList::NdnNameSkipList_invoker, repo::tests::BaseTestFixture> > (
    this=<optimized out>, f=...)
    at /usr/include/boost/test/utils/callback.hpp:56

То, что я хочу знать, это то, как динамически выделить для этого внутреннего узла？

Следующий это полный код:

#ifndef REPO_STORAGE_SKIPLIST_HPP
#define REPO_STORAGE_SKIPLIST_HPP

#include "common.hpp"

#include <boost/utility.hpp>
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int_distribution.hpp>

namespace repo {

static const size_t SKIPLIST_MAX_LAYERS = 32;
static const double SKIPLIST_PROBABILITY = 0.25; // 25% (p = 1/4)

template<typename T, typename Compare = std::less<T> >
class SkipList
{
public:
  template <class N>
  struct __skiplist_node
  {
    typedef __skiplist_node<N>* __skiplist_node_pointer;
    N data;
    __skiplist_node_pointer prev;
    std::list<__skiplist_node_pointer> nexts;
  };

  class iterator : public std::iterator<std::bidirectional_iterator_tag, T>
  {
  public:
    typedef __skiplist_node<T>* link_type;
    link_type node;
    // constructor
    iterator(link_type x) : node(x) {}
    iterator() {}
    iterator(const iterator& x) : node(x.node) {}
    bool operator == (const iterator& x) const { return node == x.node; }
    bool operator != (const iterator& x) const { return node != x.node; }

    typename std::iterator<std::bidirectional_iterator_tag, T>::reference operator * () const
      { return (*node).data; }
    typename std::iterator<std::bidirectional_iterator_tag, T>::pointer operator -> () const
      { return &(operator*()); }
    iterator& operator ++ () {
      node = (link_type)(*((*node).nexts.begin()));
      return *this;
    }
    iterator& operator -- () {
      node = (link_type)((*node).prev);
      return *this;
    }
  };

protected:
  typedef __skiplist_node<T> skiplist_node;
public:
  typedef skiplist_node* link_type;
protected:
  link_type node;
  std::allocator<skiplist_node> skiplist_allocator;

  link_type
  get_node()
  {
    return skiplist_allocator.allocate(sizeof(skiplist_node));
  }

  void
  put_node(link_type p)
  {
    skiplist_allocator.deallocate(p);
  }

  link_type
  create_node(const T& x)
  {
    link_type p = get_node();
    construct(&p->data, x);
    return p;
  }

  void
  destroy_node(link_type p)
  {
    destroy(&p->data);
    put_node(p);
  }

  void
  empty_initialize()
  {
    node = get_node();
    node->prev = node;
    node->nexts.push_back(node);
  }
public:
  explicit
  SkipList()
  {
    empty_initialize();
  }

  ~SkipList() {}

public:
  iterator begin() const { return (link_type)(*(*node).nexts.begin()); }

  iterator end() const { return node; }

  bool empty() const { return *(node->nexts.begin()) == node; }

  size_t size() const
  {
    size_t result = 0;
    result = std::distance(begin(), end());
    return result;
  }

};
} // namespace repo
#endif // REPO_STORAGE_SKIPLIST_HPP

Answer 1

Ошибка здесь:

  link_type
  get_node()
  {
    return skiplist_allocator.allocate(sizeof(skiplist_node));
  }

  link_type
  create_node(const T& x)
  {
    link_type p = get_node();
    construct(&p->data, x);
    return p;
  }

allocate просто выделяет память, не инициализирует ее Вы должны вызвать construct для его инициализации, но сделать это только для data а не для других частей вашего узла.

Таким образом, вы никогда не строили std::list, просто выделил для него память и, таким образом, ударил неопределенное поведение при попытке использовать эту неинициализированную память.