std::vector<>.size() 抛出异常

Question

我正在尝试构建一个没有指针的二叉树。 Astd::vector<NODE>nodes持有我的节点。这是我的节点：

struct node {
  int bigger;
  int smaller;
  tuple data;
  std::vector<node> &nodes_ref;

  node(tuple d, std::vector<node> &nodes)
      : data(d), nodes_ref(nodes), smaller(0), bigger(0) {}

  bool insert(tuple in) {
    if (data == in)
      return false;
    else {
      if (data > in) {
        if (smaller == 0) {
          node newNode(in, nodes_ref);
          nodes_ref.push_back(newNode);
          smaller = nodes_ref.size() - 1; // This is where the program is throwing an exception
          return true;
        } else
          return nodes_ref[smaller].insert(in);
      } else {
        if (bigger == 0) {
          node newNode(in, node_ref);
          nodes_ref.push_back(newNode);
          bigger = node_ref.size() - 1;
          return true;
        } else
          return node_ref[bigger].insert(in);

这是树：

struct tree {
  std::vector<node> nodes;

  bool insert(tuple in) {
    if (nodes.size() == 0) {
      nodes.push_back(node(in, &nodes));
      return true;
      else return nodes[0].insert(in);
    }
  }

  tree() { nodes.reserve(1000); }
}

主要功能：

int main() {
  tree t;
  t.insert(tuple(2,3);

调用 node_ref.size() 时抛出异常。然而那里应该一切都好。我做错了什么？

Answer 1

我什么都没改变现在可以使用了：

#include<iostream>
#include<vector>
#include<ctime>
#include<random>

struct tuple
{
    int a, b;
    tuple(int a,int b):a(a),b(b){}
};
inline bool operator< (const tuple& lhs, const tuple& rhs) {
    if (lhs.a < rhs.a) return true;
    else if (lhs.a == rhs.a) {
        if (lhs.b < rhs.b) return true;
        else return false;
    }
}
inline bool operator> (const tuple& lhs, const tuple& rhs) {
    if (lhs.a > rhs.a) return true;
    else if (lhs.a == rhs.a) {
        if (lhs.b > rhs.b) return true;
        else return false;
    }
}
inline bool operator==(const tuple& lhs, const tuple& rhs) {
    if ((lhs.a == rhs.a) && (lhs.b == rhs.b)) return true;
    else return false;
}

struct node
{
    std::vector<node>& repo;
    std::uint64_t smaller;
    std::uint64_t bigger;
    tuple data;
    node(tuple d, std::vector<node>& ns) :data(d), repo(ns),smaller(0),bigger(0) { }
    bool insert(tuple in) {
        if (data == in) return false;
        else {
            if (data > in) {
                if (smaller == 0) {
                    node newNode(in, repo);
                    repo.push_back(newNode);
                    smaller = repo.size()-1;
                    return true;
                }
                else return repo.at(smaller).insert(in);
            }
            else {
                if (bigger == 0) {
                    node newNode(in, repo);
                    repo.push_back(newNode);
                    bigger = repo.size()-1;
                    return true;
                }
                else return repo[bigger].insert(in);
            }
        }
    }
};

struct tree {
    std::vector<node> nodes;
    bool insert(tuple in) {
        if (nodes.size() == 0) {
            nodes.push_back(node(in, nodes));
            return true;
        }
        else return nodes[0].insert(in);
    }
    tree() {
        nodes.reserve(1000);
    }
};

int main()
{
    tree t;
    //std::default_random_engine rng(time(NULL));
    //std::uniform_int_distribution<std::uint32_t> dis(0, 3);

    t.insert(tuple(2, 3));
    t.insert(tuple(2, 1));
    t.insert(tuple(3, 8));
}

昨天我以为我为此疯了。有什么理由会发生这样的事情？昨天我遇到了 windows 防御者从运行阻止我的程序的问题。一大堆无所事事的噪音。好像是。

Answer 2

不考虑这两个函数中的逻辑是否正确:

inline bool operator< (const tuple& lhs, const tuple& rhs) {
    if (lhs.a < rhs.a) return true;
    else if (lhs.a == rhs.a) {
        if (lhs.b < rhs.b) return true;
        else return false;
    }
}
inline bool operator> (const tuple& lhs, const tuple& rhs) {
    if (lhs.a > rhs.a) return true;
    else if (lhs.a == rhs.a) {
        if (lhs.b > rhs.b) return true;
        else return false;
    }
}

但是这两个函数会导致编译器警告，看起来像这样：

warning: non-void function does not return a value in all control paths [-Wreturn-type] [build]

所以在 lhs.a > rhs.a 代表 operator< 或 lhs.a < rhs.a 代表 operator> 的情况下，这两个函数不会 return 来自函数的任何东西，并且这将导致未定义的行为。

一旦代码的一部分导致未定义的行为，任何后续代码都可能导致异常或不可预测的行为（即使它本身是正确的），并且由于它是未定义的行为，它也可能看似工作。

编译器警告不仅仅是您可能想要修复的东西，警告是编译器的一种信息，虽然它在语法上是正确的，但仍可能导致运行时错误，因此您必须修复它们。

那么您的代码失败的原因是：

smaller = nodes_ref.size() - 1; // This is where the program is throwing an exception

肯定不是 smaller = nodes_ref.size() - 1 本身当时是错误的，而是在 if (data > in) { 调用的 operator > 导致了未定义的行为。所以异常可能会在您代码的任何其他指针处抛出，它发生在那里只是巧合。

Answer 3

现在它适用于所有情况：

#include<iostream>
#include<vector>
#include<ctime>
#include<random>

struct tuple
{
    std::uint32_t a, b;
    tuple(int a,int b):a(a),b(b){}
};
inline bool operator< (const tuple& lhs, const tuple& rhs) {
    if (lhs.a < rhs.a) return true;
    else if (lhs.a == rhs.a) {
        if (lhs.b < rhs.b) return true;
        else return false;
    }
    return false;
}
inline bool operator> (const tuple& lhs, const tuple& rhs) {
    if (lhs.a > rhs.a) return true;
    else if (lhs.a == rhs.a) {
        if (lhs.b > rhs.b) return true;
        else return false;
    }
    return false;
}
inline bool operator==(const tuple& lhs, const tuple& rhs) {
    if ((lhs.a == rhs.a) && (lhs.b == rhs.b)) return true;
    else return false;
}

struct node
{
    std::vector<node>& repo;
    std::uint64_t smaller;
    std::uint64_t bigger;
    tuple data;
    node(tuple d, std::vector<node>& ns) :data(d), repo(ns),smaller(0),bigger(0) { }
    bool insert(tuple in) {
        if (data == in) return false;
        else {
            if (data > in) {
                if (smaller == 0) {
                    node newNode(in, repo);
                    repo.push_back(newNode);
                    smaller = repo.size()-1;
                    return true;
                }
                else return repo.at(smaller).insert(in);
            }
            else {
                if (bigger == 0) {
                    node newNode(in, repo);
                    repo.push_back(newNode);
                    bigger = repo.size()-1;
                    return true;
                }
                else return repo[bigger].insert(in);
            }
        }
    }
};

struct tree {
    std::vector<node> nodes;
    bool insert(tuple in) {
        if (nodes.size() == 0) {
            nodes.push_back(node(in, nodes));
            return true;
        }
        else return nodes[0].insert(in);
    }
    tree() {
        nodes.reserve(1000);
    }
};


int main()
{
    tree t;
    std::default_random_engine rng(time(NULL));
    std::uniform_int_distribution<std::uint32_t> dis(0, 9);
    for (int i = 0; i < 100; i++) t.insert(tuple(dis(rng), dis(rng)));

}

感谢@t.niese

std::vector<>.size() 抛出异常

std::vector<>.size() throws exception

c++

binary-tree

stdvector