4. Set

4. Set#

点击查看考点

排序, 去除重复值

Please complete the program while keeping interfaces and implementations seperated.

The program implements a class called Set, which can store any number of std::string objects, and satisfies the following invariants,

  • std::string* data_

    • The member that holds all std::string objects.

  • int size_

    • The member that indicates the amount of std::string objects; if no object exists, size_ == 0.

  • Element uniqueness

    • For any two different objects string1 and string2 holded by data_, string1 == string2 (equality) should not be true.

    • Also, when inserting a new object, the insertion should not happen if there's already an equal object.

You should implement the following functions for it,

  • Constructor Set(std::string* data, int size)

    • Insert all elements inside [data, data + size) into data_.

  • Copy constructor

  • Copy assignment

  • auto operator+=(Set const& other) -> Set&

    • Insert all elements inside other into *this.

  • friend auto operator+(Set const& lhs, Set const& rhs) -> Set

    • Merge two Set as a Set.

  • friend auto operator<<(std::ostream& ostream, Set const& set) -> std::ostream&

    • Output the stored std::string objects with the format [element_1, element_2, ..., element_n].

The following has given part of the Set's implementation and the main() function.

翻译

请保持接口与实现相分离地完成程序.

该程序实现了一个类 Set, 它可以存储任意数量的 std::string 对象, 且满足以下不变式,

  • std::string* data_

    • 保存存储的 std::string 对象.

  • int size_

    • 表示存储的 std::string 数量; 当不存储有 std::string 对象时, size_ == 0.

  • 元素唯一性

    • 对于 data_ 中存储的 std::string 对象, 不存在两个对象 string1 和 string2, 使得 string1 == string2 (称为相等) 成立.

    • 同时, 当插入新对象时, 若 data_ 中已存在相等的对象时, 则不进行插入.

为其实现,

  • 构造函数 Set(std::string* data, int size)

    • 将 [data, data + size) 中的元素加入 data_ 中.

  • 拷贝构造函数

  • 拷贝赋值函数

  • auto operator+=(Set const& other) -> Set&

    • 将 other 中的元素加入 *this 中.

  • friend auto operator+(Set const& lhs, Set const& rhs) -> Set

    • 合并两个 Set 为一个新的 Set.

  • friend auto operator<<(std::ostream& ostream, Set const& set) -> std::ostream&

    • 按 [元素1, 元素2, ..., 元素n] 的格式输出存储的 std::string 对象.

以下已给出 List 的部分实现以及 main() 函数.

set.hpp#
 1#ifndef SET_HPP
 2#define SET_HPP
 3
 4#include <iosfwd>
 5#include <string>
 6/* you can include any standard headers here */
 7
 8class Set {
 9 public:
10  /* please complete the code */
11
12 private:
13  std::string* data_;
14  int size_;
15};
16
17#endif
main.cpp#
 1#include "set.hpp"
 2
 3#include <iostream>
 4#include <string>
 5
 6auto main() -> int {
 7  std::string s1[] = {"John", "Bat-man", "Doctor", "John"};
 8  std::string s2[] = {"Doctor", "Smith", "Komeji", "Smith"};
 9  std::string s3[] = {"Komeji", "Satori", "Momo", "Satori"};
10
11  Set set1(s1, 4);
12  Set set2(s2, 4);
13  Set set3;
14
15  std::cout << set1 << '\n';
16  std::cout << set2 << '\n';
17  std::cout << set3 << '\n';
18
19  set3  = set2;
20  set1 += set2;
21  set1  = set1 + set3;
22
23  std::cout << set1 << '\n';
24  std::cout << set2 << '\n';
25  std::cout << set3 << '\n';
26}

点击查看解答参考

由于题目就给出了 Set, 此处不能使用 std::set. (另见可以使用 std::set 的 计软智 2023 年试题 最后一题.)

你可以用 std::vector 和 STL 算法 std::sort、std::unique 简单实现: [在线代码 nEnKE7q4G].

另可参考我针对别人问的类似问题, 完全自己实现这些的方案: