c++ - 我需要帮助为这个 vector 类制作一个插入函数

Question

将您的驱动程序命名为“vector_test_driver.cpp”，并将您的类实现文件命名为“VLIST.cpp”。为 VLIST 定义以下行为:

1. 实现默认构造函数。每次调用函数时都包含以下消息“已调用默认构造函数”。

2. 实现复制构造函数以执行 VLIST 对象的深层复制。每次调用该函数时，都包含以下消息“Copy Constructor Invoked”。该函数还应在单独的单独行上打印每个 VLIST 对象的内容。

3. 实现析构函数。每次调用函数时都包含以下消息，“Destructor Invoked”。

4. 实现 Is_Full()，如果已满则返回 true；否则为假；每次调用函数时都包含消息“Is_Full Invoked”。

5. 实现 Is_Empty()，如果为空则返回 true；否则为假；每次调用函数时都包含消息“Is_Empty Invoked”。

6. 实现名为“Search”的成员函数以在 vector 中搜索项目。该函数应打印消息，“Item Found”或“Item Not Found”。打印哪条消息取决于是否在 vector 中找到该项目。打印您要查找的项目(搜索关键字)。每次调用函数时都包含以下消息“Search Invoked”。

7. 实现一个名为“Insert”的函数，以按顺序(字母顺序)将一个项目添加到 vector 中。该函数应在单独的单独行上执行该函数之前和之后打印 VLIST 对象的内容。每次调用函数时都包含以下消息“Insert Invoked”。

8. 实现一个名为“Remove”的函数以从 vector 中删除一个项目。该函数应在单独的单独行上执行该函数之前和之后打印 VLIST 对象的内容。每次调用函数时都包含以下消息“Remove Invoked”。

这里是我的类定义:

class VLIST
{
public:
//VLIST();                //default constructor
//VLIST(const VLIST  &);  //copy constructor
//~VLIST();               //destructor
//bool IsEmpty();         //return true if empty; otherwise false
//bool IsFull();         //return true if full; otherwise false
//vector<string>::iterator Search(const string &); //returns the location of the string in the dynamic array
//void Insert(const string & key); //add key to dynamic array if not full; otherwise prints a message stating dynamic array is full
//void Remove(const string & key); //removes key from dynamic array if it is there; otherwise prints a message stating it was not in dynamic array; the function using an iterator and the erase function to remove an item from the vector.
//void Print(); //Print every string in the array
//other functions may be implemented if necessary
private:
// VLIST<string> DB;  //vector
//additonal state variables you may wish add
};

到目前为止我的插入函数代码；

 void VLIST::Insert(const string & key) {
        cout << "Insert invoked" << endl;

        vector<string>::iterator vec;
        vec = DB[count].begin();
        DB[count].at(1) = key;

        count++;
        }

我只是在黑暗中拍照。我确信友元函数可能会帮助我访问 Db，因为它在私有(private)字段中。但我试图坚持给我的骨架。我不确定如何正确实现 vector 以在一个函数中将字符串插入其中并打印到另一个函数中。 我不想完成整个作业，我只想看看插入功能如何实现

到目前为止我想出的打印功能:

void VLIST::Print() {

    for (int i = 0; i < count;i++) {
        cout << " " << DB[count].at(i) << endl;
    }

Answer 1

您必须为 std::vector“实现”插入排序。不清楚为什么您的教授将此数据结构称为列表，但会强制您使用动态数组(可能是为了模仿一个)。我会做这样的事情。不要介意断言。

  void Insert(const std::string& key)
  {
     std::cout << "Insert Invoked.\n";
     print_db(std::cout);
     assert(std::is_sorted(std::begin(db_), std::end(db_))); // Expects(std::is_sorted(db_));

     db_.push_back(key);
     auto insert_pos = std::upper_bound(std::begin(db_), std::end(db_)-1, key);
     std::rotate(insert_pos, std::end(db_)-1, std::end(db_));

     assert(std::is_sorted(std::begin(db_), std::end(db_))); // Ensures(std::is_sorted(db_));
     print_db(std::cout);
  }

这是一个Demo .

仔细看看我所做的，并尝试将其适合您的模型。而不是 std::upper_bound 尝试使用您的 Search 方法等等。

您通常应该随身携带的一件事是重用标准提供的算法的想法。查看 std::rotate 和 std::upper_bound 做了什么(对于 RandomAccessIterator)。

如果您自己实现二分查找，请查看您到底进行了多少次比较，因为 std::string 比较的开销可能非常大。您可以使用“完全”log(n) 比较(每个循环一个比较，而不是两个或类似)进行 binary_search。