Tagovan vektor

Napisati strukturu tagged_vector koja predstavlja tagovan vektor elemenata tipa T tagom tipa Tag. Pored toga, definisati tagove unsorted_vector_tag i sorted_vector_tag, kao i sledeće funkcije:

template <typename T, typename Tag>
tagged_vector<T, Tag> from_vector(const std::vector<T> &vec);

template <typename T, typename Tag>
std::vector<T> to_vector(const tagged_vector<T, Tag> &tv);

template <typename T>
tagged_vector<T, sorted_vector_tag> sort(const tagged_vector<T, unsorted_vector_tag> &tv);

template <typename T>
int binary_search(const tagged_vector<T, sorted_vector_tag> &tv, const T &value);

Test

#include <iostream>
#include <vector>
#include <algorithm>

namespace matf {

    // Ovde ide vasa implementacija

	template <typename T, typename Tag>
	tagged_vector<T, Tag> from_vector(const std::vector<T> &vec)
	{
        // Ovde ide vasa implementacija
	}

	template <typename T, typename Tag>
	std::vector<T> to_vector(const tagged_vector<T, Tag> &tv)
	{
        // Ovde ide vasa implementacija
	}

	template <typename T>
	tagged_vector<T, sorted_vector_tag> sort(const tagged_vector<T, unsorted_vector_tag> &tv)
	{
        // Ovde ide vasa implementacija
	}

	template <typename T>
	int binary_search(const tagged_vector<T, sorted_vector_tag> &tv, const T &value)
	{
        // Ovde ide vasa implementacija
    }

} // namespace matf

int main(void)
{
	std::vector<int> vec = { 5, 2, 9, 1, 5, 6 };

	auto unsorted_tv = matf::from_vector<int, matf::unsorted_vector_tag>(vec);

	auto sorted_tv = matf::sort(unsorted_tv);

	std::cout << "Original vector: ";
	for (const auto &val : unsorted_tv.data) {
		std::cout << val << " ";
	}
	std::cout << std::endl;

	int search_value = 5;

	std::cout << "Sorted vector: ";
	for (const auto &val : sorted_tv.data) {
		std::cout << val << " ";
	}
	std::cout << std::endl;

	if (matf::binary_search(sorted_tv, search_value) == 1) {
		std::cout << "Value " << search_value << " found in sorted vector." << std::endl;
	} else {
		std::cout << "Value " << search_value << " not found in sorted vector." << std::endl;
	}

	// Ovo treba da izazove gresku pri kompajliranju
	// matf::binary_search(unsorted_tv, search_value);

	return 0;
}

Rešenje

main.cpp

#include <iostream>
#include <vector>
#include <algorithm>

namespace matf {

	struct unsorted_vector_tag {};
	struct sorted_vector_tag {};


	template <typename T, typename Tag>
	struct tagged_vector {
		std::vector<T> data;
	};

	template <typename T, typename Tag>
	tagged_vector<T, Tag> from_vector(const std::vector<T> &vec)
	{
		tagged_vector<T, Tag> tv;
		tv.data = vec;
		return tv;
	}

	template <typename T, typename Tag>
	std::vector<T> to_vector(const tagged_vector<T, Tag> &tv)
	{
		return tv.data;
	}

	template <typename T>
	tagged_vector<T, sorted_vector_tag> sort(const tagged_vector<T, unsorted_vector_tag> &tv)
	{
		tagged_vector<T, sorted_vector_tag> sorted_tv;
		sorted_tv.data = tv.data;
		std::sort(sorted_tv.data.begin(), sorted_tv.data.end());
		return sorted_tv;
	}

	template <typename T>
	int binary_search(const tagged_vector<T, sorted_vector_tag> &tv, const T &value)
	{
		return std::binary_search(tv.data.begin(), tv.data.end(), value) ? 1 : -1;
	}

} // namespace matf

int main(void)
{
	std::vector<int> vec = { 5, 2, 9, 1, 5, 6 };

	auto unsorted_tv = matf::from_vector<int, matf::unsorted_vector_tag>(vec);

	auto sorted_tv = matf::sort(unsorted_tv);

	std::cout << "Original vector: ";
	for (const auto &val : unsorted_tv.data) {
		std::cout << val << " ";
	}
	std::cout << std::endl;

	int search_value = 5;

	std::cout << "Sorted vector: ";
	for (const auto &val : sorted_tv.data) {
		std::cout << val << " ";
	}
	std::cout << std::endl;

	if (matf::binary_search(sorted_tv, search_value) == 1) {
		std::cout << "Value " << search_value << " found in sorted vector." << std::endl;
	} else {
		std::cout << "Value " << search_value << " not found in sorted vector." << std::endl;
	}

	// Ovo treba da izazove gresku pri kompajliranju
	// matf::binary_search(unsorted_tv, search_value);

	return 0;
}