Ich muss std::vector in std::stack kopieren.

  1. Ist das Überqueren des Vektors und das Einschieben in den Stapel nur der richtige Weg?

  2. Wenn es einen anderen Weg gibt, welche ist aus Sicht der Leistung die bessere Wahl?

Code:

 std::stack<A>   m_stack;
 std::vector<A>  m_vec;

 for (auto& elem : m_vec)
 {
    m_stack.push(elem);
 }
12
T M 24 Dez. 2015 im 15:12

4 Antworten

Beste Antwort

Da ein Stapel ein Containeradapter ist, können Sie den Stapel aus dem zugrunde liegenden Container erstellen:

std::vector<A> m_vec = /* ... */;
std::stack<A, std::vector<A>> m_stack(m_vec);

Oder wenn Sie möchten, dass Ihr Stack deque unterstützt wird:

std::stack<A> m_stack(std::deque<A>(m_vec.begin(), m_vec.end()));
14
Kerrek SB 24 Dez. 2015 im 12:14

Ein bisschen Spaß mit Stapeln, die verschiedene Methoden demonstrieren, um Werte aus einem anderen Container auf den Stapel zu bringen.

Angenommen, wir haben eine angemessene Definition für Folgendes bereitgestellt:

template<class T, class Container>
auto stack_pusher(std::stack<T, Container>& stack);

Wir könnten dann schreiben:

int main()
{
    using namespace std;

    // construct an initial vector
    vector<int> init { 7,6 };

    // construct a stack using a copy of the initial vector's elements
    // note that the stack's storage is automatically deduced
    stack<int> stack1 { { begin(init), end(init) } };

    // construct a stack directly from a container initialised with an initialiser list
    stack<int> stack2 { { 3,4,5 } };

    // another vector
    vector<int> myvector { 1, 2, 3, 4, 5, 6, 7, 8 };

    // copy vector onto stack using a forward iterator
    copy(begin(myvector),
         end(myvector),
         stack_pusher(stack1));

    // copy vector onto stack using a reverse iterator
    copy(rbegin(myvector),
         rend(myvector),
         stack_pusher(stack2));

    // display the stacks
    while (stack1.size() or stack2.size())
    {
        // function to encode an optional T as a string
        auto encode = [](const auto& opt)
        {
            return opt ? std::to_string(opt.value()) : std::string("*");
        };

        // function to pop a value from a stack if it's not empty.
        // return an optional
        auto maybe_pop = [](auto& stack)
        {
            using element_type = std::decay_t<decltype(stack.top())>;
            boost::optional<element_type> result;
            if (stack.size()) {
                result = stack.top();
                stack.pop();
            }
            return result;
        };

        cout
        << encode(maybe_pop(stack1))
        << "\t"
        << encode(maybe_pop(stack2)) << endl;
    }

    return 0;
}

Für die die Ausgabe wäre:

8       1
7       2
6       3
5       4
4       5
3       6
2       7
1       8
6       5
7       4
*       3

Hier ist die vollständige Liste (c ++ 14):

#include <iostream>
#include <stack>
#include <vector>
#include <deque>
#include <iterator>
#include <utility>
#include <boost/optional.hpp>

// an iterator that pushes values onto a stack
template<class Stack>
struct push_iterator
: std::iterator<std::output_iterator_tag,void,void,void,void>
{
    push_iterator(Stack& stack)
    : pstack(std::addressof(stack))
    {}

    template<class T>
    auto& operator=(T&& t)
    {
        pstack->push(std::forward<T>(t));
        return *this;
    }

    auto& operator*() {
        return *this;
    }

    auto& operator++() {
        return *this;
    }

private:
    Stack* pstack;
};

// convenience class to make a push_iterator of the correct type
template<class T, class Container>
auto stack_pusher(std::stack<T, Container>& stack)
{
    return push_iterator<std::stack<T, Container>>(stack);
}

int main()
{
    using namespace std;

    // construct an initial vector
    vector<int> init { 7,6 };

    // construct a stack using a copy of the initial vector's elements
    // note that the stack's storage is automatically deduced
    stack<int> stack1 { { begin(init), end(init) } };

    // construct a stack directly from a container initialises with an initialiser list
    stack<int> stack2 { { 3,4,5 } };

    // another vector
    vector<int> myvector { 1, 2, 3, 4, 5, 6, 7, 8 };

    // copy vector onto stack using a forward iterator
    copy(begin(myvector),
         end(myvector),
         stack_pusher(stack1));

    // copy vector onto stack using a reverse iterator
    copy(rbegin(myvector),
         rend(myvector),
         stack_pusher(stack2));

    // display the stacks
    while (stack1.size() or stack2.size())
    {
        // function to encode an optional T as a string
        auto encode = [](const auto& opt)
        {
            return opt ? std::to_string(opt.value()) : std::string("*");
        };

        // function to pop a value from a stack if it's not empty.
        // return an optional
        auto maybe_pop = [](auto& stack)
        {
            using element_type = std::decay_t<decltype(stack.top())>;
            boost::optional<element_type> result;
            if (stack.size()) {
                result = stack.top();
                stack.pop();
            }
            return result;
        };

        cout
        << encode(maybe_pop(stack1))
        << "\t"
        << encode(maybe_pop(stack2)) << endl;
    }

    return 0;
}
2
Richard Hodges 24 Dez. 2015 im 14:21

std::stack ist ein seltsamer, aber hackbarer Container:

#include<vector>
#include<stack>

struct A{};

template<class T>
struct mystack : std::stack<T>{
    decltype(auto) c(){return std::stack<T>::c;}
};

int main(){
    std::vector<A>  m_vec;

    mystack<A>   m_stack;
    m_stack.c().assign(m_vec.begin(), m_vec.end());

}

Oder

#include<vector>
#include<stack>

struct A{};

template<class... T>
struct mystack : std::stack<T...>{
    decltype(auto) container(){return std::stack<T...>::c;}
};

template<class... T>
decltype(auto) container(std::stack<T...>& s){return static_cast<mystack<T...>&>(s).container();}

int main(){
    std::vector<A>  m_vec;

    std::stack<A>   m_stack;
    container(m_stack).assign(m_vec.begin(), m_vec.end());
}
1
alfC 18 Mai 2018 im 22:27

Unter dieser Frage finden Sie Möglichkeiten, wie std::copy zugelassen werden kann Wird auf einem Stapel verwendet, aber es gibt keinen offensichtlicheren Weg als eine Schleife mit Push-Aufrufen.

Die Leistung lässt sich nur messen. (Code für Klarheit und Korrektheit zuerst und dann Sorge um Geschwindigkeit.)

0
Community 23 Mai 2017 im 11:59